The Use of Pivoting to Improve the Numerical Performance of Algorithms for Toeplitz Matrices

Abstract

Classical $O( n^2 )$ Toeplitz solvers break down if any leading principal submatrices are singular, and as might be expected, the occurrence of nearly singular leading submatrices can cause a serious loss of accuracy in these solvers. In this paper, a pivoting scheme has been incorporated into the Toeplitz solver of Bareiss which allows near-singularities to be treated without significant loss of accuracy. As special cases, the pivoted Toeplitz solver also handles exact singularities and numerical singularities—the latter appear as near-singularities when finite-precision floating-point arithmetic is used. The Bareiss algorithm can also be used to compute the $LU$ factors of a Toeplitz matrix, and it is shown that a restricted version of the pivoted Toeplitz solver produces an $LU$ factorization of a row- and column-permuted version of the original Toeplitz matrix.Finally, it is shown how the inverter of Trench and Zohar can be derived from the multipliers produced by the Bareiss algorithm, and this connection is used to derive a pivoted version of the Trench–Zohar algorithm from the pivoted Bareiss algorithm.