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?)

  • [1] D. Bini & M. Capovani, "Fast parallel and sequential computations and spectral properties concerning band Toeplitz matrices," Calcolo, v. 22, 1983, pp. 176-189. MR 746352 (86e:65055)
  • [2] D. Bini & M. Capovani, "Spectral and computational properties of band symmetric Toeplitz matrices," Linear Algebra Appl., v. 52/53, 1983, pp. 99-126. MR 709346 (85k:15008)
  • [3] D. Bini & V. Pan, "Polynomial division and its computational complexity," J. Complexity, v. 2, 1986, pp. 179-203. MR 922812 (89k:68060)
  • [4] P. Lancaster & M. Tismenetsky, The Theory of Matrices, Academic Press, New York, 1985. MR 792300 (87a:15001)
  • [5] V. Pan, On the Sequential and Parallel Approximate Evaluation of Polynomial Zeros, Tech. Rep. 87-14, Computer Science Dept., SUNYA, Albany, N. Y., 1987, to appear in Comput. Math. Appl. MR 920483 (88j:65101)
  • [6] J. Stoer & R. Bulirsch, Introduction to Numerical Analysis, Springer-Verlag, Berlin, 1980. MR 557543 (83d:65002)
  • [7] M. Tismenetsky, "Determinant of block-Toeplitz band matrices," Linear Algebra Appl., v. 85, 1987, pp. 165-187. MR 869351 (87m:15025)
  • [8] W. F. Trench, "On the eigenvalue problem for Toeplitz band Matrices," Linear Algebra Appl., v. 64, 1985, pp. 199-214. MR 776527 (86d:15005)

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