×

Accurate computation of generalized eigenvalues of regular SR-BP pairs. (English) Zbl 1480.65081

Summary: In this paper, we consider the generalized eigenvalue problem (GEP) for bidiagonal-product (BP) pairs with sign regularity (SR), which include structured pairs associated with ill-conditioned matrices, such as Cauchy and Vandermonde matrices, that arise in many applications. A sufficient and necessary condition is provided for an SR-BP pair to be regular. For regular SR-BP pairs having both matrices singular, we establish sharp relative perturbation bounds to show that all the generalized eigenvalues including infinite and zero ones can be accurately determined by their BP representations. By operating on the BP representations, a new method is developed to accurately compute generalized eigenvalues of such a regular SR-BP pair. Our method first transforms the pair into an equivalent pair with a certain sign regularity. Then a technique is proposed to implicitly deflate all the infinite eigenvalues. After deflating infinite eigenvalues, finite eigenvalues are computed by reducing the deflated GEP into a standard eigenvalue problem. An attractive property of our method is that all the generalized eigenvalues are returned to high relative accuracy especially, all the infinite and zero eigenvalues are computed exactly. Error analysis and numerical experiments are performed to confirm the claimed high relative accuracy.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65G50 Roundoff error
15A18 Eigenvalues, singular values, and eigenvectors
15A22 Matrix pencils
15B05 Toeplitz, Cauchy, and related matrices

Software:

TNTool; JDQZ; JDQR
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A.S. Alfa, J. Xue and Q. Ye, Accurate computation of the smallest eigenvalue of a diagonally dominant M-matrix, Math. Comp., 71 (2002), pp. 217-236. · Zbl 0984.65033
[2] T. Ando, Totally positive matrices, Linear Algebra Appl., 90 (1987), pp. 165-219. · Zbl 0613.15014
[3] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. Van Der Vorst, Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, SIAM, Philadelphia, 2000. · Zbl 0965.65058
[4] J.M. Berg and H.G. Kwatny, A canonical parameterization of the Kronecker form of a matrix pencil, Automatica J. IFAC, 31 (1995), pp. 669-680. · Zbl 0826.93009
[5] D. Bini and F. Di Benedetto, Solving the generalized eigenvalue problem for rational Toeplitz matrices, SIAM J. Matrix Anal. Appl., 11 (1990), pp. 537-552. · Zbl 0724.65037
[6] P. Boito, Y. Eidelman, and L. Gemignani, Implicit QR for companion-like pencils, Math. Comp., 85 (2016), pp. 1753-1774. · Zbl 1335.65041
[7] Z. Bujanović, L. Karlsson, and D. Kressner, A Householder-based algorithm for Hessenberg-triangular reduction, SIAM J. Matrix Anal. Appl., 39 (2018), pp. 1270-1294. · Zbl 1431.65041
[8] D. Camps, K. Meerbergen, and R. Vandebril, A rational QZ method, SIAM J. Matrix Anal. Appl., 40 (2019), pp. 943-972. · Zbl 1420.65044
[9] N. Castro-González, J. Geballos, F.M. Dopico, and J.M. Molera, Accurate solution of structured least squares problems via rank-revealing decompositions, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 1112-1128. · Zbl 1296.65060
[10] S. Chandrasekaran, An efficient and stable algorithm for the symmetric-definite generalized eigenvalue problem, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 1202-1228. · Zbl 1049.65023
[11] D. Chu and G.H. Golub, On a generalized eigenvalue problem for nonsquare pencils, SIAM J. Matrix Anal. Appl., 28 (2006), pp. 770-787. · Zbl 1128.15004
[12] J. Demmel, Accurate singular value decompositions of structured matrices, SIAM J. Matrix Anal. Appl., 21 (1999), pp. 562-580. · Zbl 0951.65036
[13] J. Demmel, M. Gu, S. Eisenstat, I. Slapničar, K. Veselić, and Z. Drmač, Computing the singular value decomposition with high relative accuracy, Linear Algebra Appl., 299 (1999), pp. 21-80. · Zbl 0952.65032
[14] J. Demmel, D. Ioana, O. Holtz, and P. Koev, Accurate and efficient expression evaluation and linear algebra, Acta Numer., 17 (2008), pp. 87-145. · Zbl 1169.65022
[15] J. Demmel and P. Koev, The accurate and efficient solution of a totally positive generalized Vandermonde linear system, SIAM J. Matrix Anal. Appl., 27 (2005), pp. 142-152. · Zbl 1096.65031
[16] F. Dopico and P. Koev, Accurate symmetric rank revealing and eigendecompositions of symmetric structured matrices, SIAM J. Matrix Anal. Appl., 28 (2006), pp. 1126-1156. · Zbl 1124.65039
[17] F. Dopico and P. Koev, Accurate solution of structured linear systems via rank-revealing decompositions, IMA J. Numer. Anal., 32 (2012), pp. 1096-1116. · Zbl 1251.65040
[18] Z. Drmac̆, A tangent algorithm for computing the generalized singular value decomposition, SIAM J. Numer. Anal., 35 (1998), pp. 1804-1832. · Zbl 0914.65033
[19] M. Elad and P. Milanfar, Shape from moments-An estimation theory perspective, IEEE Trans. Signal Process., 52 (2004), pp. 1814-1828. · Zbl 1369.62145
[20] L. Elsner, I. Koltracht, M. Neumann, and D. Xiao, On accurate computations of the Perron root, SIAM J. Matrix Anal. Appl., 14 (1993), pp. 456-467. · Zbl 0774.65016
[21] D. Fokkema, G. Sleijpen, and H. Van Der Vorst, Jacobi-Davidson style QR and QZ algorithms for the reduction of matrix pencils, SIAM J. Sci. Comput., 20 (1998), pp. 94-125. · Zbl 0924.65027
[22] M. Gasca and J.M. Pen͂a, On factorizations of totally positive matrices, in Total Positivity and Its Applications, Kluwer Academic Publishers, Dordrecht, the Netherlands (1996). · Zbl 0891.15017
[23] R. Huang, A periodic qd-type reduction for computing eigenvalues of structured matrix products to high relative accuracy, J. Sci. Comput., 75 (2018), pp. 1129-1261. · Zbl 1391.65084
[24] R. Huang, Accurate solutions of weighted least squares problems associated with rank-structured matrices, Appl. Numer. Math., 146 (2019), pp. 416-435. · Zbl 1437.65018
[25] R. Huang, Accurate solutions of product linear systems associated with rank-structured matrices, J. Comput. Appl. Math., 347 (2019), pp. 108-127. · Zbl 1406.65014
[26] R. Huang, A qd-type method for computing generalized singular values of BF matrix pairs with sign regularity to high relative accuracy, Math. Comp., 89 (2020), pp. 229-252. · Zbl 1436.65037
[27] R. Huang, Accurate eigenvalues of some generalized sign regular matrices via relatively robust representations, J. Sci. Comput. 82, 78 (2020). https://doi.org/10.1007/s10915-020-01182-4 · Zbl 1439.65047
[28] R. Huang, Computing the SVD of a product of rank-deficient NBF matrices to high relative accuracy, to appear.
[29] B. Kȧgström and D. Kressner, Multishift variants of the QZ algorithm with aggressive early deflation, SIAM J. Matrix Anal. Appl., 29 (2006), pp. 199-227. · Zbl 1137.65017
[30] V. Kalantzis, A domain decomposition Rayleigh-Ritz algorithm for symmetric generalized eigenvalue problems, SIAM J. Sci. Comput., 42 (2020), pp. C410-C435. · Zbl 1467.65031
[31] P. Koev, Accurate eigenvalues and SVDs of totally nonnegative matrices, SIAM J. Matrix Anal. Appl., 27 (2005), pp. 1-23. · Zbl 1095.65031
[32] P. Koev, Accurate computations with totally nonnegative matrices, SIAM J. Matrix Anal. Appl., 29 (2007), pp. 731-751. · Zbl 1198.65057
[33] P. Koev, Accurate eigenvalues and exact zero Jordan blocks of totally nonnegative matrices, Numer. Math., 141 (2019), pp. 693-713. · Zbl 1434.65035
[34] P. Koev, Accurate Computations with Totally Nonnegative Matrices, https://math.mit.edu/ plamen/software/TNTool.html, 2019. · Zbl 1198.65057
[35] W. Kohn and L. Sham, Self-consistent equations including exchange and correlation effects, Phys. Rev., 140 (1965), pp. A1133-A1138.
[36] R.-C. Li, On perturbations of matrix pencils with real spectra, a revisit, Math. Comp., 72 (2002), pp. 715-728. · Zbl 1047.15008
[37] R.-C. Li, Y. Nakatsukasa, N. Truhar, and S.-F. Xu, Perturbation of partitioned Hermitian definite generalized eigenvalue problems, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 642-663. · Zbl 1230.15011
[38] A. Marco and J-J. Martínez, Polynomial least squares fitting in the Bernstein basis, Linear Algebra Appl., 433 (2010), pp. 1254-1264. · Zbl 1202.65017
[39] A. Marco, J-J. Martínez, and J.M. Pen͂a, Accurate bidiagonal decomposition of totally positive Cauchy-Vandermonde matrices and applications, Linear Algebra Appl., 517 (2017), pp. 63-84. · Zbl 1355.65048
[40] A. Marco and J.J. Martínez, A fast and accurate algorithm for solving Bernstein-Vandermonde linear systems, Linear Algebra Appl., 422 (2007), pp. 616-628. · Zbl 1116.65038
[41] C. Moler and G.W. Stewart, An algorithm for generalized matrix eigenvalue problems, SIAM J. Numer. Anal., 10 (1973), pp. 241-256. · Zbl 0253.65019
[42] Y. Nakatsukasa, Gerschgorin’s theorem for generalized eigenvalues problems in the Euclidean metric, Math. Comp., 80 (2011), pp. 2127-2142. · Zbl 1230.15012
[43] V.Y. Pan, Structured Matrices and Polynomials: Unified Superfast Algorithms, Birkhäuser, Boston, 2001. · Zbl 0996.65028
[44] J. Rommes, Arnoldi and Jacobi-Davidson methods for generalized eigenvalues problems \(Ax=\lambda Bx\) with singular \(B\), Math. Comp., 77 (2008), pp. 995-1015. · Zbl 1133.65020
[45] C. Roothaan, Modern developments in molecular orbital theory, Rev. Modern Phys., 23 (1951), pp. 69-89. · Zbl 0045.28502
[46] G.W. Stewart and J.-G. Sun, Matrix Perturbation Theory, Academic Press, New York, 1990. · Zbl 0706.65013
[47] R. Vandebril, G. Golub, and M. Van Barel, A quasi-separable approach to solve the symmetric definite tridiagonal generalized eigenvalue problem, SIAM J. Matrix Anal. Appl., 31 (2009), pp. 154-174. · Zbl 1186.65046
[48] Q. Ye, Computing singular values of diagonally dominant matrices to high relative accuracy, Math. Comp., 77 (2008), pp. 2195-2230. · Zbl 1198.65077
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.