Stable and efficient computation of generalized polar decompositions. (English) Zbl 1492.65116
Summary: We present methods for computing the generalized polar decomposition of a matrix based on the dynamically weighted Halley iteration. This method is well established for computing the standard polar decomposition. A stable implementation is available, where matrix inversion is avoided and QR decompositions are used instead. We establish a natural generalization of this approach for computing generalized polar decompositions with respect to signature matrices. Again the inverse can be avoided by using a generalized QR decomposition called hyperbolic QR decomposition. However, this decomposition does not show the same favorable stability properties as its orthogonal counterpart. We overcome the numerical difficulties by generalizing the CholeskyQR2 method. This method computes the standard QR factorization in a stable way via two successive Cholesky factorizations. An even better numerical stability is achieved by employing permuted graph bases, yielding residuals of order \(10^{-14}\) even for badly conditioned matrices, where other methods fail.
MSC:
| 65F60 | Numerical computation of matrix exponential and similar matrix functions |
| 65F55 | Numerical methods for low-rank matrix approximation; matrix compression |
Keywords:
generalized polar decomposition; dynamically weighted Halley iteration; matrix sign function; \(LDL^T\) factorization; hyperbolic QR decomposition; indefinite QR decomposition; permuted graph basisReferences:
| [1] | E. Anderson, Discontinuous Plane Rotations and the Symmetric Eigenvalue Problem, LAPACK Working Note 150, 2000, http://www.netlib.org/lapack/lawnspdf/lawn150.pdf. |
| [2] | C. Ashcraft, R. G. Grimes, and J. G. Lewis, Accurate symmetric indefinite linear equation solvers, SIAM J. Matrix Anal. Appl., 20 (1999), pp. 513-561, https://doi.org/10.1137/S0895479896296921. · Zbl 0923.65010 |
| [3] | Z. Bai and J. W. Demmel, Design of a Parallel Nonsymmetric Eigenroutine Toolbox, Part I, Tech. Report UCB/CSD-92-718, EECS Department, University of California, Berkeley, 1993, http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/6014.html. |
| [4] | P. Benner, Symplectic balancing of Hamiltonian matrices, SIAM J. Sci. Comput., 22 (2001), pp. 1885-1904, https://doi.org/10.1137/S1064827500367993. · Zbl 0985.65025 |
| [5] | P. Benner, V. Khoromskaia, and B. N. Khoromskij, A reduced basis approach for calculation of the Bethe-Salpeter excitation energies using low-rank tensor factorizations, Mol. Phys., 114 (2016), pp. 1148-1161, https://doi.org/10.1080/00268976.2016.1149241. |
| [6] | P. Benner and C. Penke, Efficient and accurate algorithms for solving the Bethe-Salpeter eigenvalue problem for crystalline systems, J. Comput. Appl. Math., 400 (2022), 113650. · Zbl 1473.65044 |
| [7] | P. Benner and C. Penke, GR decompositions and their relations to Cholesky-like factorizations, Proc. Appl. Math. Mech., 20 (2021), e202000065, https://doi.org/10.1002/pamm.202000065. |
| [8] | P. Benner and E. S. Quintana-Ortí, Solving stable generalized Lyapunov equations with the matrix sign function, Numer. Algorithms, 20 (1999), pp. 75-100, https://doi.org/10.1023/A:1019191431273. · Zbl 0940.65035 |
| [9] | X. Blase, I. Duchemin, D. Jacquemin, and P.-F. Loos, The Bethe-Salpeter equation formalism: From physics to chemistry, J. Phys. Chem. Lett., 11 (2020), pp. 7371-7382, https://doi.org/10.1021/acs.jpclett.0c01875. |
| [10] | A. Bojanczyk, N. J. Higham, and H. Patel, Solving the indefinite least squares problem by hyperbolic QR factorization, SIAM J. Matrix Anal. Appl., 24 (2003), pp. 914-931, https://doi.org/10.1137/S0895479802401497. · Zbl 1036.65035 |
| [11] | Y. Bolshakov and B. Reichstein, Unitary equivalence in an indefinite scalar product: An analogue of singular-value decomposition, Linear Algebra Appl., 222 (1995), pp. 155-226, https://doi.org/10.1016/0024-3795(93)00295-B. · Zbl 0828.15009 |
| [12] | Y. Bolshakov, C. V. M. van der Mee, A. C. M. Ran, B. Reichstein, and L. Rodman, Polar decompositions in finite-dimensional indefinite scalar product spaces: General theory, Linear Algebra Appl., 261 (1997), pp. 91-141, https://doi.org/10.1016/S0024-3795(96)00317-5. · Zbl 0881.15013 |
| [13] | I. Borg and P. J. F. Groenen, Modern Multidimensional Scaling: Theory and Applications, Springer-Verlag, Berlin, 2005, https://doi.org/10.1007/0-387-28981-X. · Zbl 1085.62079 |
| [14] | J. R. Bunch and L. Kaufman, Some stable methods for calculating inertia and solving symmetric linear systems, Math. Comp., 31 (1977), pp. 163-179, https://doi.org/10.1090/S0025-5718-1977-0428694-0. · Zbl 0355.65023 |
| [15] | J. R. Bunch, L. Kaufman, and B. Parlett, Decomposition of a symmetric matrix, Numer. Math., 27 (1976), pp. 95-109, https://doi.org/10.1007/BF01399088. · Zbl 0342.65026 |
| [16] | J. R. Bunch and B. N. Parlett, Direct methods for solving symmetric indefinite systems of linear equations, SIAM J. Numer. Anal., 8 (1971), pp. 639-655, https://doi.org/10.1137/0708060. · Zbl 0199.49802 |
| [17] | W. Bunse and A. Bunse-Gerstner, Numerische Lineare Algebra, Teubner, Stuttgart, 1985. · Zbl 0547.65018 |
| [18] | R. Byers, Solving the algebraic Riccati equation with the matrix sign function, Linear Algebra Appl., 85 (1987), pp. 267-279. · Zbl 0611.65027 |
| [19] | R. Byers and H. Xu, A new scaling for Newton’s iteration for the polar decomposition and its backward stability, SIAM J. Matrix Anal. Appl., 30 (2008), pp. 822-843, https://doi.org/10.1137/070699895. · Zbl 1170.65019 |
| [20] | M. Casida, Time-dependent density functional response theory for molecules, in Recent Advances in Density Functional Methods, World Scientific, Englewood Cliffs, NJ, 1995, pp. 155-192, https://doi.org/10.1142/9789812830586_0005. |
| [21] | S. Chandrasekaran and A. H. Sayed, Stabilizing the generalized Schur algorithm, SIAM J. Matrix Anal. Appl., 17 (1996), pp. 950-983, https://doi.org/10.1137/S0895479895287419. · Zbl 0860.65016 |
| [22] | J. J. Dongarra, J. R. Gabriel, D. D. Koelling, and J. H. Wilkinson, The eigenvalue problem for Hermitian matrices with time reversal symmetry, Linear Algebra Appl., 60 (1984), pp. 27-42, https://doi.org/10.1016/0024-3795(84)90068-5. · Zbl 0559.65019 |
| [23] | I. S. Duff, MA57-A code for the solution of sparse symmetric definite and indefinite systems, ACM Trans. Math. Software, 30 (2004), pp. 118-144, https://doi.org/10.1145/992200.992202. · Zbl 1070.65525 |
| [24] | A. Edelman and S. Jeong, Fifty Three Matrix Factorizations: A Systematic Approach, https://arxiv.org/abs/2104.08669, 2021. |
| [25] | G. H. Golub and C. F. Van Loan, Matrix Computations, Johns Hopkins Stud. Math. Sci., 4th ed., Johns Hopkins University Press, Baltimore, 2013. · Zbl 1268.65037 |
| [26] | D. Henrion and P. Hippe, Hyperbolic QR factorization for J-spectral factorization of polynomial matrices, in Proceedings of the 42nd IEEE International Conference on Decision and Control, Vol. 4, 2003, pp. 3479-3484, https://doi.org/10.1109/CDC.2003.1271685. |
| [27] | N. J. Higham, \(J\)-orthogonal matrices: Properties and generation, SIAM Rev., 45 (2003), pp. 504-519, https://doi.org/10.1137/S0036144502414930. · Zbl 1034.65026 |
| [28] | N. J. Higham, Functions of Matrices: Theory and Computation, SIAM, Philadelphia, 2008, https://doi.org/10.1137/1.9780898717778. · Zbl 1167.15001 |
| [29] | N. J. Higham, D. Mackey, N. Mackey, and F. Tisseur, Functions preserving matrix groups and iterations for the matrix square root, SIAM J. Matrix Anal. Appl., 26 (2005), pp. 849-877, https://doi.org/10.1137/S0895479804442218. · Zbl 1079.65053 |
| [30] | N. J. Higham, C. Mehl, and F. Tisseur, The canonical generalized polar decomposition, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 2163-2180, https://doi.org/10.1137/090765018. · Zbl 1222.15018 |
| [31] | I. Houtzager, JQR/JRQ/JQL/JLQ factorizations, MATLAB Central File Exchange, https://www.mathworks.com/matlabcentral/fileexchange/50329- jqr-jrq-jql-jlq-factorizations, 2015. |
| [32] | C. Kenney and A. J. Laub, Rational iterative methods for the matrix sign function, SIAM J. Matrix Anal. Appl., 12 (1991), pp. 273-291, https://doi.org/10.1137/0612020. · Zbl 0725.65048 |
| [33] | C. Kenney and A. J. Laub, On scaling Newton’s method for polar decomposition and the matrix sign function, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 688-706, https://doi.org/10.1137/0613044. · Zbl 0754.65043 |
| [34] | U. Kintzel, Procrustes problems in finite dimensional indefinite scalar product spaces, Linear Algebra Appl., 402 (2005), pp. 1-28, https://doi.org/10.1016/j.laa.2005.01.004. · Zbl 1072.15035 |
| [35] | H. Li, H. Yang, and H. Shao, Perturbation analysis for the hyperbolic QR factorization, Comput. Math. Appl., 63 (2012), pp. 1607-1620, https://doi.org/10.1016/j.camwa.2012.03.036. · Zbl 1252.65080 |
| [36] | H. Ltaief, D. Sukkari, A. Esposito, Y. Nakatsukasa, and D. Keyes, Massively parallel polar decomposition on distributed-memory systems, ACM Trans. Parallel Comput., 6 (2019), https://doi.org/10.1145/3328723. · Zbl 1471.65023 |
| [37] | D. S. Mackey, N. Mackey, and F. Tisseur, Structured factorizations in scalar product spaces, SIAM J. Matrix Anal. Appl., 27 (2005), pp. 821-850, https://doi.org/10.1137/040619363. · Zbl 1098.15005 |
| [38] | C. Mehl, V. Mehrmann, and H. Xu, On doubly structured matrices and pencils that arise in linear response theory, Linear Algebra Appl., 380 (2004), pp. 3-51, https://doi.org/10.1016/S0024-3795(02)00455-X. · Zbl 1083.65038 |
| [39] | C. Mehl, A. C. M. Ran, and L. Rodman, Polar decompositions of normal operators in indefinite inner product spaces, in Operator Theory in Krein Spaces and Nonlinear Eigenvalue Problems, Oper. Theory Adv. Appl. 162, Birkhäuser, Basel, 2006, pp. 277-292, https://doi.org/10.1007/3-7643-7453-5_15. · Zbl 1108.47034 |
| [40] | V. Mehrmann and F. Poloni, Doubling algorithms with permuted Lagrangian graph bases, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 780-805, https://doi.org/10.1137/110850773. · Zbl 1260.65059 |
| [41] | Y. Nakatsukasa, Z. Bai, and F. Gygi, Optimizing Halley’s iteration for computing the matrix polar decomposition, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 2700-2720, https://doi.org/10.1137/090774999. · Zbl 1215.65081 |
| [42] | Y. Nakatsukasa and R. W. Freund, Computing fundamental matrix decompositions accurately via the matrix sign function in two iterations: The power of Zolotarev’s functions, SIAM Rev., 58 (2016), pp. 461-493, https://doi.org/10.1137/140990334. · Zbl 1383.15012 |
| [43] | Y. Nakatsukasa and N. J. Higham, Backward stability of iterations for computing the polar decomposition, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 460-479, https://doi.org/10.1137/110857544. · Zbl 1252.65083 |
| [44] | G. Onida, L. Reining, and A. Rubio, Electronic excitations: Density-functional versus many-body Green’s-function approaches, Rev. Mod. Phys., 74 (2002), pp. 601-659, https://doi.org/10.1103/RevModPhys.74.601. |
| [45] | C. Penke, A. Marek, C. Vorwerk, C. Draxl, and P. Benner, High performance solution of skew-symmetric eigenvalue problems with applications in solving the Bethe-Salpeter eigenvalue problem, Parallel Comput., 96 (2020), 102639, https://doi.org/10.1016/j.parco.2020.102639. |
| [46] | F. Poloni, Permuted Graph Matrices and Their Applications, Springer, Cham, 2015, pp. 107-129, https://doi.org/10.1007/978-3-319-15260-8_5. · Zbl 1327.65083 |
| [47] | J. D. Roberts, Linear model reduction and solution of the algebraic Riccati equation by use of the sign function, Internat. J. Control, 32 (1980), pp. 677-687, https://doi.org/10.1080/00207178008922881. · Zbl 0463.93050 |
| [48] | M. Shao, F. H. da Jornada, C. Yang, J. Deslippe, and S. G. Louie, Structure preserving parallel algorithms for solving the Bethe-Salpeter eigenvalue problem, Linear Algebra Appl., 488 (2016), pp. 148-167, https://doi.org/10.1016/j.laa.2015.09.036. · Zbl 1330.65059 |
| [49] | S. Singer, Indefinite QR factorization, BIT, 46 (2006), pp. 141-161, https://doi.org/10.1007/s10543-006-0044-5. · Zbl 1093.65029 |
| [50] | S. Singer and S. Singer, Rounding-error and perturbation bounds for the indefinite \(QR\) factorization, Linear Algebra Appl., 309 (2000), pp. 103-119, https://doi.org/10.1016/S0024-3795(99)00156-1. · Zbl 0948.65042 |
| [51] | D. Sukkari, H. Ltaief, A. Esposito, and D. Keyes, A QDWH-based SVD software framework on distributed-memory manycore systems, ACM Trans. Math. Software, 45 (2019), 18, https://doi.org/10.1145/3309548. · Zbl 1471.65023 |
| [52] | X. Sun and E. S. Quintana-Ortí, Spectral division methods for block generalized Schur decompositions, Math. Comp., 73 (2004), pp. 1827-1847, https://doi.org/10.1090/S0025-5718-04-01667-9. · Zbl 1054.65034 |
| [53] | K. Veselić, Damped Oscillations of Linear Systems, Lecture Notes in Math., Springer-Verlag, Berlin, 2011, https://doi.org/10.1007/978-3-642-21335-9. · Zbl 1232.37004 |
| [54] | D. Watkins, The Matrix Eigenvalue Problem, SIAM, Philadelphia, 2007, https://doi.org/10.1137/1.9780898717808. · Zbl 1142.65038 |
| [55] | Y. Yamamoto, Y. Nakatsukasa, Y. Yanagisawa, and T. Fukaya, Roundoff error analysis of the Cholesky QR2 algorithm, Electron. Trans. Numer. Anal., 44 (2015), pp. 306-326. · Zbl 1330.65049 |
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.
