HIGH-PERFORMANCE ALGORITHMS FOR TOEPLITZ AND BLOCK TOEPLITZ MATRICES

In this paper, we present several high performance variants of the cla ssical Schur algorithm to factor various Toeplitz matrices. For positi ve definite block Toeplitz matrices, we show how hyperbolic Householde r transformations may be blocked to yield a block Schur algorithm. Thi s algorithm uses BLAS3 primitives and makes efficient use of a memory hierarchy. We present three algorithms for indefinite Toeplitz matrice s. Two of these are based on look-ahead strategies and produce an exac t factorization of the Toeplitz matrix. The third produces an inexact factorization via perturbations of singular principal miners. We also present an analysis of the numerical behavior of the third algorithm a nd derive a bound for the number of iterations to improve the accuracy of the solution. For rank-deficient Toeplitz least-squares problems, we present a variant of the generalized Schur algorithm that avoids br eakdown due to an exact rank-deficiency. In the presence of a near ran k-deficiency, an approximate rank factorization of the Toeplitz matrix is produced. Finally, we suggest an algorithm to solve the normal equ ations resulting from a real Toeplitz least-squares problem based on t ransforming to Cauchy-like matrices. This algorithm exploits both real ness and symmetry in the normal equations.