×
Eidelman, Yuli; Haimovici, Iulian

Improved bisection eigenvalue method for band symmetric Toeplitz matrices. (English) Zbl 1524.65166

ETNA, Electron. Trans. Numer. Anal. 58, 316-347 (2023).
Summary: We apply a general bisection eigenvalue algorithm, developed for Hermitian matrices with quasiseparable representations, to the particular case of real band symmetric Toeplitz matrices. We show that every band symmetric Toeplitz matrix \(T_q\) with bandwidth \(q\) admits the representation \(T_q=A_q+H_q\), where the eigendata of \(A_q\) are obtained explicitly and the matrix \(H_q\) has nonzero entries only in two diagonal blocks of size \((q-1)\times (q-1)\). Based on this representation, one obtains an interlacing property of the eigenvalues of the matrix \(T_q\) and the known eigenvalues of the matrix \(A_q\). This allows us to essentially improve the performance of the bisection eigenvalue algorithm. We also present an algorithm to compute the corresponding eigenvectors.

Cited in 1 Document

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15B05 Toeplitz, Cauchy, and related matrices

Keywords:

Toeplitz; quasiseparable; banded matrices; eigenstructure; inequalities; Sturm with bisection
Cite Review PDF
Full Text: DOI Link

References:

[1] W. BARTH, R. S. MARTIN,ANDJ. H. WILKINSON,Calculations of the eigenvalues of a symmetric tridiagonal matrix by the method of bisection, Numer. Math., 9 (1967), pp. 386-393. · Zbl 0189.47803
[2] D. BINI ANDM. CAPOVANI,Spectral and computational properties of band symmetric Toeplitz matrices, Linear Algebra Appl., 52/53 (1983), pp. 99-126. · Zbl 0549.15005
[3] D. BINI ANDV. PAN,On the evaluation of the eigenvalues of banded block Toeplitz block matrices, J. Complexity, 7 (1991), pp. 408-424. · Zbl 0767.65027
[4] ,Polynomial and Matrix Computations. Vol I., Birkhäuser, Boston, 1994. · Zbl 0809.65012
[5] A. CANTONI ANDP. BUTLER,Eigenvalues and eigenvectors of symmetric centrosymmetric matrices, Linear Algebra Appl., 13 (1976), pp. 275-288. · Zbl 0326.15007
[6] Y. EIDELMAN ANDI. GOHBERG,On a new class of structured matrices, Integral Equations Operator Theory, 34 (1999), pp. 293-324. · Zbl 0934.15002
[7] Y. EIDELMAN, I. GOHBERG,ANDI. HAIMOVICI,Separable Type Representations of Matrices and Fast Algorithms. Vol. 1, Oper. Theory Adv. Appl. 234, Birkhäuser, Basel, 2014. · Zbl 1280.65034
[8] ,Separable Type Representations of Matrices and Fast Algorithms. Vol. 2., Oper. Theory Adv. Appl. 235, Birkhäuser, Basel, 2014. · Zbl 1280.65027
[9] Y. EIDELMAN, I. GOHBERG,ANDV. OLSHEVSKY,Eigenstructure of order-one-quasiseparable matrices. Three-term and two-term recurrence relations, Linear Algebra Appl., 405 (2005), pp. 1-40. · Zbl 1079.65037
[10] Y. EIDELMAN ANDI. HAIMOVICI,The fast bisection eigenvalue method for Hermitian order one quasiseparable matrices and computations of norms, Electron. Trans. Numer. Anal., 44 (2015), pp. 342-366. https://etna.ricam.oeaw.ac.at/vol.44.2015/pp342-366.dir/pp342-366.pdf · Zbl 1332.65049
[11] ,Bisection eigenvalue method for Hermitian matrices with quasiseparable representation and a related inverse problem, in Operator Theory, Analysis and the State Space Approach, H. Bart, S. ter Horst, A. C. M. Ran, and H. J. Woerdeman, eds., vol. 271 of Oper. Theory Adv. Appl., Birkhäuser/Springer, Cham, 2018, pp. 181-200. · Zbl 1431.65043
[12] S. E. EKSTRÖM, C. GARONI,ANDS. SERRACAPIZZANO,Are the eigenvalues of banded symmetric Toeplitz matrices known in almost closed form?, Exp. Math., 27 (2018), pp. 478-487. · Zbl 1405.15037
[13] S.-E. EKSTRÖM ANDS. SERRA-CAPIZZANO,Eigenvalues and eigenvectors of banded Toeplitz matrices and the related symbols, Numer. Linear Algebra Appl., 25 (2018), Paper No. e2137, 17 pages. · Zbl 1513.65095
[14] D. J. EVANS,A recursive algorithm for determining the eigenvalues of a quindiagonal matrix, Comput. J., 18 (1975), pp. 70-73. · Zbl 0296.65015
[15] G. H. GOLUB ANDC. F. V. LOAN,Matrix Computations, 4th ed., Johns Hopkins University Press, Baltimore, 2013. · Zbl 1268.65037
[16] A. J. HOFFMAN ANDH. W. WIELANDT,The variation of the spectrum of a normal matrix, Duke Math. J., 20 (1953), pp. 37-39. · Zbl 0051.00903
[17] A. HORN,Eigenvalues of sums of Hermitian matrices, Pacific J. Math., 12 (1962), pp. 225-241. · Zbl 0112.01501
[18] R. A. HORN ANDC. R. JOHNSON,Matrix Analysis, 2nd ed., Cambridge University Press, Cambridge, 2013. · Zbl 1267.15001
[19] G. D. SMITH,Numerical Solution of Partial Differential Equations, 2nd ed., Oxford University Press, New York, 1978. · Zbl 0389.65040
[20] J. STOER ANDR. BULIRSCH,Introduction to Numerical Analysis, 3rd ed., Springer, New York, 2002. · Zbl 1004.65001
[21] W. A. SENTANCE ANDI. P. CLIFF,The determination of eigenvalues of symmetric quindiagonal matrices, Comput. J., 24 (1981), pp. 177-179. · Zbl 0462.65020
[22] S. SERRACAPIZZANO ANDD. SESANA,A note on the eigenvalues ofg-circulants (and ofg-Toeplitz, g-Hankel matrices), Calcolo, 51 (2014), pp. 639-659. · Zbl 1312.15013
[23] W. F. TRENCH,On the eigenvalue problem for Toeplitz band matrices, Linear Algebra Appl., 64 (1985), pp. 199-214. · Zbl 0568.15005
[24] R. VANDEBRIL, M. VANBAREL,ANDN. MASTRONARDI,Matrix Computations and Semiseparable Matrices. Vol. I, Johns Hopkins University Press, Baltimore, 2008. · Zbl 1141.65019
[25] ,Matrix Computations and Semiseparable Matrices. Vol. II, Johns Hopkins University Press, Baltimore, 2008. · Zbl 1141.65019
[26] H. WEYL,Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumstrahlung), Math. Ann., 71 (1912), pp. 441-479. · JFM 43.0436.01
[27] J. H. WILKINSON,Calculation of the eigenvalue of a symmetric tridiagonal matrix by the method of bisection, Numer. Math., 4 (1962), pp. 362-367. · Zbl 0107.34306
[28] ,The Algebraic Eigenvalue Problem, Claredon Press, Oxford, 1965 · Zbl 0258.65037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.