Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Efficient algorithms for the evaluation of the eigenvalues of (block) banded Toeplitz matrices

Authors: D. Bini and V. Pan
Journal: Math. Comp. 50 (1988), 431-448
MSC: Primary 65F30
MathSciNet review: 929545
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let A be an $ n \times n$ banded block Toeplitz matrix of bandwidth k with $ m \times m$ blocks having entries in a field F. We present algorithms for computing $ p(\lambda ) = \det (A - \lambda I)$ as well as the ratio $ p(\lambda )/p'(\lambda )$, where $ p'(\lambda )$ is the first derivative of $ p(\lambda )$ with respect to $ \lambda $, in roughly $ (3/2){k^2}\log n + O({k^3})$ block multiplications. If the field F supports FFT, then the cost is reduced to $ O(({m^2}k\log k + {m^3}k)\log n + {k^3}{m^3})$ scalar multiplications. The algorithms generalize an algorithm given by W. Trench for computing $ p(\lambda )$ in the case $ m = 1$ in roughly $ k\log n + O({k^3})$ multiplications and rely on powering a companion matrix associated with the linear recurrence relation representing the original problem.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F30

Retrieve articles in all journals with MSC: 65F30

Additional Information

Keywords: Banded Toeplitz matrices, block matrices, eigenvalues, computational complexity, matrix difference equation, cyclic reduction
Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society