Fast solution of unsymmetric banded Toeplitz systems by means of spectral factorizations and Woodbury's formula |
| |
Authors: | AN Malyshev M Sadkane |
| |
Institution: | 1. Department of Mathematics, University of Bergen, , Postbox 7800 N‐5020 Bergen, Norway;2. Laboratoire de Mathématiques, Université de Brest, , France |
| |
Abstract: | 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. |
| |
Keywords: | linear system banded Toeplitz matrix spectral polynomial factorization Woodbury formula |
|
|