Fast solution of unsymmetric banded Toeplitz systems by means of spectral factorizations and Woodbury's formula

A fast algorithm for solving systems of linear equations with banded Toeplitz matrices is studied. An important step in the algorithm is a novel method for the spectral factorization of the generating function associated with the Toeplitz matrix. The spectral factorization is extracted from the right deflating subspaces corresponding to the eigenvalues inside and outside the open unit disk of a companion matrix pencil constructed from the coefficients of the generating function. The factorization is followed by the Woodbury inversion formula and solution of several banded triangular systems. Stability of the algorithm is discussed and its performance is demonstrated by numerical experiments. Copyright © 2012 John Wiley & Sons, Ltd.     

A direct method for solving block‐Toeplitz with near‐circulant‐block systems with applications to hybrid manufacturing systems

In this paper, we present a direct method for solving linear systems of a block‐Toeplitz matrix with each block being a near‐circulant matrix. The direct method is based on the fast Fourier transform (FFT) and the Sherman–Morrison–Woodbury formula. We give a cost analysis for the proposed method. The method is then applied to solve the steady‐state probability distribution of a hybrid manufacturing system which consists of a manufacturing process and a re‐manufacturing process. Copyright © 2005 John Wiley & Sons, Ltd.     

Asymptotic properties of the QR factorization of banded Hessenberg–Toeplitz matrices

We consider Givens QR factorization of banded Hessenberg–Toeplitz matrices of large order and relatively small bandwidth. We investigate the asymptotic behaviour of the R factor and Givens rotation when the order of the matrix goes to infinity, and present some interesting convergence properties. These properties can lead to savings in the computation of the exact QR factorization and give insight into the approximate QR factorizations of interest in preconditioning. The properties also reveal the relation between the limit of the main diagonal elements of R and the largest absolute root of a polynomial. Copyright © 2005 John Wiley & Sons, Ltd.     

The use of the Sherman–Morrison–Woodbury formula to solve cyclic block tri-diagonal and cyclic block penta-diagonal linear systems of equations

The article presents a new theoretical viewpoint of Batista’s algorithms for solving cyclic tri-diagonal (and penta-diagonal) linear systems. The theory is based on the Sherman–Morrison–Woodbury formula.