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.