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 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 and M. Capovani,*Fast parallel and sequential computations and spectral properties concerning band Toeplitz matrices*, Calcolo**20**(1983), no. 2, 177–189 (1984). MR**746352**, 10.1007/BF02575591**[2]**Dario Bini and Milvio Capovani,*Spectral and computational properties of band symmetric Toeplitz matrices*, Linear Algebra Appl.**52/53**(1983), 99–126. MR**709346**, 10.1016/0024-3795(83)80009-3**[3]**Dario Bini and Victor Pan,*Polynomial division and its computational complexity*, J. Complexity**2**(1986), no. 3, 179–203. MR**922812**, 10.1016/0885-064X(86)90001-4**[4]**Peter Lancaster and Miron Tismenetsky,*The theory of matrices*, 2nd ed., Computer Science and Applied Mathematics, Academic Press, Inc., Orlando, FL, 1985. MR**792300****[5]**V. Pan,*Sequential and parallel complexity of approximate evaluation of polynomial zeros*, Comput. Math. Appl.**14**(1987), no. 8, 591–622. MR**920483**, 10.1016/0898-1221(87)90186-6**[6]**J. Stoer and R. Bulirsch,*Introduction to numerical analysis*, Springer-Verlag, New York-Heidelberg, 1980. Translated from the German by R. Bartels, W. Gautschi and C. Witzgall. MR**557543****[7]**M. Tismenetsky,*Determinant of block-Toeplitz band matrices*, Linear Algebra Appl.**85**(1987), 165–184. MR**869351**, 10.1016/0024-3795(87)90214-X**[8]**William F. Trench,*On the eigenvalue problem for Toeplitz band matrices*, Linear Algebra Appl.**64**(1985), 199–214. MR**776527**, 10.1016/0024-3795(85)90277-0

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

Keywords:
Banded Toeplitz matrices,
block matrices,
eigenvalues,
computational complexity,
matrix difference equation,
cyclic reduction

Article copyright:
© Copyright 1988
American Mathematical Society