Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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 Free Access

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

DOI: http://dx.doi.org/10.1090/S0025-5718-1988-0929545-5
PII: S 0025-5718(1988)0929545-5
Keywords: Banded Toeplitz matrices, block matrices, eigenvalues, computational complexity, matrix difference equation, cyclic reduction
Article copyright: © Copyright 1988 American Mathematical Society