Computing symplectic eigenpairs of symmetric positive-definite matrices via trace minimization and Riemannian optimization. (English) Zbl 1480.15011
Summary: We address the problem of computing the smallest symplectic eigenvalues and the corresponding eigenvectors of symmetric positive-definite matrices in the sense of Williamson’s theorem. It is formulated as minimizing a trace cost function over the symplectic Stiefel manifold. We first investigate various theoretical aspects of this optimization problem such as characterizing the sets of critical points, saddle points, and global minimizers as well as proving that nonglobal local minimizers do not exist. Based on our recent results on constructing Riemannian structures on the symplectic Stiefel manifold and the associated optimization algorithms, we then propose a numerical procedure for computing symplectic eigenpairs in the framework of Riemannian optimization. Moreover, a connection of the sought solution with the eigenvalues of a special class of Hamiltonian matrices is discussed. Numerical examples are presented.
MSC:
| 15A15 | Determinants, permanents, traces, other special matrix functions |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 49Q99 | Manifolds and measure-geometric topics |
Keywords:
symplectic eigenpairs; Williamson’s diagonal form; trace minimization; Riemannian optimization; symplectic Stiefel manifold; symmetric positive-definite matrices; positive-definite Hamiltonian matrixReferences:
| [1] | P.-A. Absil, C. Baker, and K. Gallivan, A truncated-CG style method for symmetric generalized eigenvalue problems, J. Comput. Appl. Math., 189 (2006), pp. 274-285, https://doi.org/10.1016/j.cam.2005.10.006. · Zbl 1090.65042 |
| [2] | P.-A. Absil, C. Baker, K. Gallivan, and A. Sameh, Adaptive model trust region methods for generalized eigenvalue problems, in Proceedings of ICCS, Springer, Berlin, 2005, pp. 33-41, https://doi.org/10.1007/11428831_5. · Zbl 1129.65307 |
| [3] | P.-A. Absil, R. Mahony, and R. Sepulchre, Riemannian geometry of Grassmann manifolds with a view on algorithmic computations, Acta Appl. Math, 8 (2004), pp. 199-220, https://doi.org/10.1023/B:ACAP.0000013855.14971.91. · Zbl 1052.65048 |
| [4] | P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton University Press, Princeton, NJ, 2008. · Zbl 1147.65043 |
| [5] | P. Amodio, A symplectic Lanczos-type algorithm to compute the eigenvalues of positive definite Hamiltonian matrices, in Proceedings of ICCS, P. Sloot, D. Abramson, A. Bogdanov, J. Dongarra, A. Zomaya, and Y. Gorbachev, eds., Lecture Notes in Comput. Sci. 2657 (Part II), Springer, 2003, pp. 139-148, https://doi.org/10.1007/3-540-44862-4_16. · Zbl 1147.65305 |
| [6] | P. Amodio, On the computation of few eigenvalues of positive definite Hamiltonian matrices, Future Generation Comput. Syst., 22 (2006), pp. 403-411, https://doi.org/10.1016/j.future.2004.11.027. |
| [7] | P. Amodio, F. Iavernaro, and D. Trigiante, Conservative perturbations of positive definite Hamiltonian matrices, Numer. Linear Algebra Appl, 12 (2005), pp. 117-125, https://doi.org/10.1002/nla.409. · Zbl 1164.15338 |
| [8] | Z. Bai and R.-C. Li, Minimization principles for the linear response eigenvalue problem I: Theory, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 1075-1100, https://doi.org/10.1137/110838960. · Zbl 1263.65078 |
| [9] | Z. Bai and R.-C. Li, Minimization principles for the linear response eigenvalue problem II: Computation, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 392-416, https://doi.org/10.1137/110838972. · Zbl 1311.65102 |
| [10] | Z. Bai and R.-C. Li, Minimization principles and computation for the generalized linear response eigenvalue problem, BIT, 54 (2014), pp. 31-54, https://doi.org/10.1007/s10543-014-0472-6. · Zbl 1293.65053 |
| [11] | C. Baker, P.-A. Absil, and K. Gallivan, An implicit Riemannian trust-region method for the symmetric generalized eigenproblem, in Proceedings of ICCS, Springer, Berlin, 2006, pp. 210-217, https://doi.org/10.1007/11758501_32. · Zbl 1155.65325 |
| [12] | P. Benner and H. Fassbender, An implicitly restarted symplectic Lanczos method for the Hamiltonian eigenvalue problem, Linear Algebra Appl., 263 (1997), pp. 75-111, https://doi.org/10.1016/S0024-3795(96)00524-1. · Zbl 0884.65028 |
| [13] | P. Benner, H. Fassbender, and M. Stoll, Solving large-scale quadratic eigenvalue problems with Hamiltonian eigenstructure using a structure-preserving Krylov subspace method, Electron. Trans. Numer. Anal., 29 (2008), pp. 212-229. · Zbl 1171.65374 |
| [14] | P. Benner, H. Faßbender, and M. Stoll, A Hamiltonian Krylov-Schur-type method based on the symplectic Lanczos process, Linear Algebra Appl., 435 (2011), pp. 578-600, https://doi.org/10.1016/j.laa.2010.04.048. · Zbl 1219.65040 |
| [15] | P. Benner, D. Kressner, and V. Mehrmann, Skew-Hamiltonian and Hamiltonian eigenvalue problems: Theory, algorithms and applications, in Proceedings of the Conference on Applied Mathematics and Scientific Computing, 2005, pp. 3-39, https://doi.org/10.1007/1-4020-3197-1_1. · Zbl 1069.65034 |
| [16] | R. Bhatia and T. Jain, On the symplectic eigenvalues of positive definite matrices, J. Math. Phys., 56 (2015), 112201, https://doi.org/10.1063/1.4935852. · Zbl 1329.15048 |
| [17] | P. Birtea, I. Caşu, and D. Comǎnescu, Optimization on the real symplectic group, Monatsh. Math., 191 (2020), pp. 465-485, https://doi.org/10.1007/s00605-020-01369-9. · Zbl 1434.49026 |
| [18] | V. Bovdia, R. A. Horn, M. Salim, and V. Sergeichuk, Symplectic spaces and pairs of symmetric and nonsingular skew-symmetric matrices under congruence, Linear Algebra Appl., 537 (2018), pp. 84-99, https://doi.org/10.1016/j.laa.2017.09.026. · Zbl 1376.15005 |
| [19] | M. de Gosson, Symplectic Geometry and Quantum Mechanics, Adv. Partial Differ. Equ. (Basel), Birkhäuser, Basel, 2006. · Zbl 1098.81004 |
| [20] | A. Edelman, T. Arias, and S. Smith, The geometry of algorithms with orthogonality constraints, SIAM J. Matrix Anal. Appl., 20 (1998), pp. 303-353, https://doi.org/10.1137/S0895479895290954. · Zbl 0928.65050 |
| [21] | J. Eisert, T. Tyc, T. Rudolph, and B. Sanders, Gaussian quantum marginal problem, Commun. Math. Phys., 280 (2008), pp. 263-280, https://doi.org/10.1007/s00220-008-0442-4. · Zbl 1145.81019 |
| [22] | H. Fassbender, The parameterized SR algorithm for symplectic (butterfly) matrices, Math. Comp., 70 (2000), pp. 1515-1541, https://doi.org/10.1090/S0025-5718-00-01265-5. · Zbl 0986.65032 |
| [23] | H. Fassbender, Symplectic Methods for the Symplectic Eigenproblem, Springer, Berlin, 2002. · Zbl 0972.65026 |
| [24] | J. Fehr, D. Grunert, P. Holzwarth, B. Fröhlich, N. Walker, and P. Eberhard, MOREMBS-A model order reduction package for elastic multibody systems and beyond, in Reduced-Order Modeling (ROM) for Simulation and Optimization, W. Keiper, A. Milde, and S. Volkwein, eds., Springer, Berlin, 2018, pp. 141-166, https://doi.org/10.1007/978-3-319-75319-5_7. · Zbl 1433.74004 |
| [25] | S. Fiori, A Riemannian steepest descent approach over the inhomogeneous symplectic group: Application to the averaging of linear optical systems, Appl. Math. Comput., 283 (2016), pp. 251-264, https://doi.org/10.1016/j.amc.2016.02.018. · Zbl 1410.65062 |
| [26] | A. Fomenko, Symplectic Geometry, Adv. Stud. Contemp. Math., Gordon and Breach Science Publishers, Amsterdam, 1995. · Zbl 0873.58031 |
| [27] | B. Francis, A Course in \(H_\infty\) Control Theory, Lecture Notes in Control and Inform. Sci., Springer, Berlin, 1987. · Zbl 0624.93003 |
| [28] | B. Gao, N. Son, P.-A. Absil, and T. Stykel, Riemannian optimization on the symplectic Stiefel manifold, SIAM J. Optim., 31 (2021), pp. 1546-1575, https://doi.org/10.1137/20M1348522. · Zbl 1507.65100 |
| [29] | G. Golub and C. V. Loan, Matrix Computations, 4th ed., The Johns Hopkins University Press, Baltimore, MD, 2013. · Zbl 1268.65037 |
| [30] | M. Grüning, A. Marini, and X. Gonze, Implementation and testing of Lanczos-based algorithms for random-phase approximation eigenproblems, Comput. Mat. Sci., 50 (2011), pp. 2148-2156, https://doi.org/10.1016/j.commatsci.2011.02.021. |
| [31] | N. Higham, Functions of Matrices: Theory and Computation, SIAM, Philadelphia, 2008, https://doi.org/10.1137/1.9780898717778. · Zbl 1167.15001 |
| [32] | D. Hinrichsen and N. Son, Stability radii of linear discrete-time systems and symplectic pencils, Internat. J. Robust Nonlinear Control, 1 (1991), pp. 79-97, https://doi.org/10.1002/rnc.4590010204. · Zbl 0754.93060 |
| [33] | T. Hiroshima, Additivity and multiplicativity properties of some Gaussian channels for Gaussian inputs, Phys. Rev. A, 73 (2006), 012330, https://doi.org/10.1103/PhysRevA.73.012330. |
| [34] | H. Hofer and E. Zehnder, Symplectic Invariants and Hamiltonian Dynamics, Birkhäuser, Basel, 2011, https://doi.org/10.1007/978-3-0348-0104-1. · Zbl 1223.37001 |
| [35] | R. Horn and C. Johnson, Matrix Analysis, 2nd ed., Cambridge University Press, New York, 2013. · Zbl 1267.15001 |
| [36] | M. Idel, S. Gaona, and M. Wolf, Perturbation bounds for Williamson’s symplectic normal form, Linear Algebra Appl., 525 (2017), pp. 45-58, https://doi.org/10.1016/j.laa.2017.03.013. · Zbl 1365.15015 |
| [37] | K. D. Ikramov, The conditions for the reducibility and canonical forms of Hamiltonian matrices with pure imaginary eigenvalues, Zh. Vychisl. Mat. Mat. Fiz., 31 (1991), pp. 1123-1130. · Zbl 0735.15009 |
| [38] | K. D. Ikramov, On the symplectic eigenvalues of positive definite matrices, Moscow Univ. Comput. Math. Cybernet., 42 (2018), pp. 1-4, https://doi.org/10.3103/S0278641918010041. · Zbl 1397.15007 |
| [39] | T. Jain and H. Mishra, Derivatives of symplectic eigenvalues and a Lidskii type theorem, Canad. J. Math., 2020, https://doi.org/10.4153/S0008414X2000084X. · Zbl 1489.15018 |
| [40] | J. Kovač-Striko and K. Veselić, Trace minimization and definiteness of symmetric pencils, Linear Algebra Appl., 216 (1995), pp. 139-158, https://doi.org/10.1016/0024-3795(93)00126-K. · Zbl 0821.15008 |
| [41] | M. Krbek, T. Tyc, and J. Vlach, Inequalities for quantum marginal problems with continuous variables, J. Math. Phys., 55 (2014), 062201, https://doi.org/10.1063/1.4880198. · Zbl 1292.81139 |
| [42] | D. Kressner, Numerical Methods for General and Structured Eigenvalue Problems, Lect. Notes Comput. Sci. Eng., 46, Springer, Berlin, 2005, https://doi.org/10.1007/3-540-28502-4. · Zbl 1079.65041 |
| [43] | D. Kressner, M. Pandur, and M. Shao, An indefinite variant of LOBPCG for definite matrix pencils, Numer. Algorithms, 66 (2014), pp. 681-703, https://doi.org/10.1007/s11075-013-9754-3. · Zbl 1297.65040 |
| [44] | P. Lancaster and L. Rodman, The Algebraic Riccati Equation, Oxford University Press, Oxford, 1995. · Zbl 0836.15005 |
| [45] | P. Lancaster and R. Rodman, Canonical forms for symmetric/skew-symmetric real matrix pairs under strict equivalence and congruence, Linear Algebra Appl., 406 (2005), pp. 1-76, https://doi.org/10.1016/j.laa.2005.03.035. · Zbl 1081.15007 |
| [46] | P. Lancaster and R. Rodman, Canonical forms for Hermitian matrix pairs under strict equivalence and congruence, SIAM Rev., 47 (2006), pp. 407-443, https://doi.org/10.1137/S003614450444556X. · Zbl 1087.15014 |
| [47] | J. Lee, I. Panageas, G. Piliouras, M. Simchowitz, M. Jordan, and B. Recht, First-order methods almost always avoid strict saddle points, Math. Program., 176 (2019), pp. 311-337, https://doi.org/110.1007/s10107-019-01374-3. · Zbl 1415.90089 |
| [48] | R. C. Li and L. H. Zhang, Convergence of the block Lanczos method for eigenvalue clusters, Numer. Math., 131 (2015), pp. 83-113, https://doi.org/10.1007/s00211-014-0681-6. · Zbl 1334.65073 |
| [49] | X. Liang, R.-C. Li, and Z. Bai, Trace minimization principles for positive semi-definite pencils, Linear Algebra Appl., 438 (2013), pp. 3085-3106, https://doi.org/10.1016/j.laa.2012.12.003. · Zbl 1262.15010 |
| [50] | C. V. Loan, A symplectic method for approximating all the eigenvalues of a Hamiltonian matrix, Linear Algebra Appl., 61 (1984), pp. 233-251, https://doi.org/10.1016/0024-3795(84)90034-X. · Zbl 0565.65018 |
| [51] | R. B. Morgan and M. Zeng, A harmonic restarted Arnoldi algorithm for calculating eigenvalues and determining multiplicity, Linear Algebra Appl., 415 (2006), pp. 96-113, https://doi.org/10.1016/j.laa.2005.07.024. · Zbl 1088.65033 |
| [52] | I. Nakić and K. Veselić, Wielandt and Ky-Fan theorem for matrix pairs, Linear Algebra Appl., 369 (2003), pp. 77-93, https://doi.org/10.1016/S0024-3795(02)00733-4. · Zbl 1035.15021 |
| [53] | J. Nocedal and S. Wright, Numerical Optimization, Springer Ser. Oper. Res. Financ. Eng., Springer, Berlin, 2006, https://doi.org/10.1007/978-0-387-40065-5. · Zbl 1104.65059 |
| [54] | M. Pandur, Preconditioned gradient iterations for the eigenproblem of definite matrix pairs, Electron. Trans. Numer. Anal., 51 (2019), pp. 331-362, https://doi.org/10.1553/etna_vol51s331. · Zbl 1431.65046 |
| [55] | K. Parthasarathy, The symmetry group of Gaussian states in \(L^2(\mathbb{R}^n)\), in Prokhorov and Contemporary Probability Theory, Springer Proc. Math. Stat. 33, Springer, Berlin, 2013, pp. 349-369, https://doi.org/10.1007/978-3-642-33549-5_21. · Zbl 1275.81059 |
| [56] | L. Peng and K. Mohseni, Symplectic model reduction of Hamiltonian systems, SIAM J. Sci. Comput., 38 (2016), pp. A1-A27, https://doi.org/10.1137/140978922. · Zbl 1330.65193 |
| [57] | 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. |
| [58] | Y. Saad, Numerical Methods for Large Eigenvalue Problems, SIAM, Philadelphia, 2011, https://doi.org/10.1137/1.9781611970739. · Zbl 1242.65068 |
| [59] | A. Sameh and Z. Tong, The trace minimization method for the symmetric generalized eigenvalue problem, J. Comput. Appl. Math., 123 (2000), pp. 155-175, https://doi.org/10.1016/S0377-0427(00)00391-5. · Zbl 0964.65038 |
| [60] | A. Sameh and J. Wisniewski, A trace minimization algorithm for the generalized eigenvalue problem, SIAM J. Numer. Anal., 19 (1982), pp. 1243-1259, https://doi.org/10.1137/0719089. · Zbl 0493.65017 |
| [61] | R. Simon, S. Chaturvedi, and V. Srinivasan, Congruences and canonical forms for a positive matrix: Application to the Schweinler-Wigner extremum principle, J. Math. Phys., 40 (1999), pp. 3632-3642, https://doi.org/10.1063/1.532913. · Zbl 0951.15011 |
| [62] | A. van der Schaft and D. Jeltsema, Port-Hamiltonian systems theory: An introductory overview, Found. Trends Syst. Control, 1 (2014), pp. 173-378, https://doi.org/10.1561/2600000002. · Zbl 1496.93055 |
| [63] | R. Ward and L. Gray, Eigensystem computation for skew-symmetric matrices and a class of symmetric matrices, ACM Trans. Math. Software, 4 (1978), pp. 278-285, https://doi.org/10.1145/355791.355798. · Zbl 0384.65014 |
| [64] | D. Watkins, On Hamiltonian and symplectic Lanczos processes, Linear Algebra Appl., 385 (2004), pp. 23-45, https://doi.org/10.1016/j.laa.2002.11.001. · Zbl 1062.65047 |
| [65] | D. Watkins, The Matrix Eigenvalue Problem, SIAM, Philadelphia, 2007, https://doi.org/10.1137/1.9780898717808. · Zbl 1142.65038 |
| [66] | S. Wei and I. Kao, Vibration analysis of wire and frequency response in the modern wiresaw manufacturing process, J. Sound Vib., 231 (2000), pp. 1383-1395, https://doi.org/10.1006/jsvi.1999.2471. |
| [67] | J. Williamson, On the algebraic problem concerning the normal forms of linear dynamical systems, Amer. J. Math., 58 (1936), pp. 141-163, https://doi.org/10.2307/2371062. · JFM 62.1795.10 |
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.
