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

DOI:
https://doi.org/10.1090/S0025-5718-1988-0929545-5

MathSciNet review:
929545

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let *A* be an banded block Toeplitz matrix of bandwidth *k* with blocks having entries in a field **F**. We present algorithms for computing as well as the ratio , where is the first derivative of with respect to , in roughly block multiplications. If the field **F** supports FFT, then the cost is reduced to scalar multiplications. The algorithms generalize an algorithm given by W. Trench for computing in the case in roughly multiplications and rely on powering a companion matrix associated with the linear recurrence relation representing the original problem.

**[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)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65F30

Retrieve articles in all journals with MSC: 65F30

Additional Information

DOI:
https://doi.org/10.1090/S0025-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