Efficient algorithms for the evaluation of the eigenvalues of (block) banded Toeplitz matrices
Authors:
D. Bini and V. Pan
Journal:
Math. Comp. 50 (1988), 431448
MSC:
Primary 65F30
MathSciNet review:
929545
Fulltext 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
(86e:65055), http://dx.doi.org/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 (85k:15008), http://dx.doi.org/10.1016/00243795(83)800093
 [3]
Dario
Bini and Victor
Pan, Polynomial division and its computational complexity, J.
Complexity 2 (1986), no. 3, 179–203. MR 922812
(89k:68060), http://dx.doi.org/10.1016/0885064X(86)900014
 [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
(87a:15001)
 [5]
V.
Pan, Sequential and parallel complexity of approximate evaluation
of polynomial zeros, Comput. Math. Appl. 14 (1987),
no. 8, 591–622. MR 920483
(88j:65101), http://dx.doi.org/10.1016/08981221(87)901866
 [6]
J.
Stoer and R.
Bulirsch, Introduction to numerical analysis, SpringerVerlag,
New YorkHeidelberg, 1980. Translated from the German by R. Bartels, W.
Gautschi and C. Witzgall. MR 557543
(83d:65002)
 [7]
M.
Tismenetsky, Determinant of blockToeplitz band matrices,
Linear Algebra Appl. 85 (1987), 165–184. MR 869351
(87m:15025), http://dx.doi.org/10.1016/00243795(87)90214X
 [8]
William
F. Trench, On the eigenvalue problem for Toeplitz band
matrices, Linear Algebra Appl. 64 (1985),
199–214. MR
776527 (86d:15005), http://dx.doi.org/10.1016/00243795(85)902770
 [1]
 D. Bini & M. Capovani, "Fast parallel and sequential computations and spectral properties concerning band Toeplitz matrices," Calcolo, v. 22, 1983, pp. 176189. 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. 99126. MR 709346 (85k:15008)
 [3]
 D. Bini & V. Pan, "Polynomial division and its computational complexity," J. Complexity, v. 2, 1986, pp. 179203. 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. 8714, 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, SpringerVerlag, Berlin, 1980. MR 557543 (83d:65002)
 [7]
 M. Tismenetsky, "Determinant of blockToeplitz band matrices," Linear Algebra Appl., v. 85, 1987, pp. 165187. MR 869351 (87m:15025)
 [8]
 W. F. Trench, "On the eigenvalue problem for Toeplitz band Matrices," Linear Algebra Appl., v. 64, 1985, pp. 199214. 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
DOI:
http://dx.doi.org/10.1090/S00255718198809295455
PII:
S 00255718(1988)09295455
Keywords:
Banded Toeplitz matrices,
block matrices,
eigenvalues,
computational complexity,
matrix difference equation,
cyclic reduction
Article copyright:
© Copyright 1988
American Mathematical Society
