Projection methods for large-scale T-Sylvester equations
HTML articles powered by AMS MathViewer
- by Froilán M. Dopico, Javier González, Daniel Kressner and Valeria Simoncini;
- Math. Comp. 85 (2016), 2427-2455
- DOI: https://doi.org/10.1090/mcom/3081
- Published electronically: January 12, 2016
- PDF | Request permission
Abstract:
The matrix Sylvester equation for congruence, or T-Sylvester equation, has recently attracted considerable attention as a consequence of its close relation to palindromic eigenvalue problems. The theory concerning T-Sylvester equations is rather well understood, and there are stable and efficient numerical algorithms which solve these equations for small- to medium-sized matrices. However, developing numerical algorithms for solving large-scale T-Sylvester equations still remains an open problem. In this paper, we present several projection algorithms based on different Krylov spaces for solving this problem when the right-hand side of the T-Sylvester equation is a low-rank matrix. The new algorithms have been extensively tested, and the reported numerical results show that they work very well in practice, offering clear guidance on which algorithm is the most convenient in each situation.References
- Athanasios C. Antoulas, Approximation of large-scale dynamical systems, Advances in Design and Control, vol. 6, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2005. With a foreword by Jan C. Willems. MR 2155615, DOI 10.1137/1.9780898718713
- R. H. Bartels and G. W. Stewart, Algorithm 432: The solution of the matrix equation $AX - BX = C$, Communications of the ACM 8 (1972), 820–826.
- M. Baumann and U. Helmke, Singular value decomposition of time-varying matrices, Future Generation Computer Systems 19 (2003), no. 3, 353–361.
- Bernhard Beckermann, An error analysis for rational Galerkin projection applied to the Sylvester equation, SIAM J. Numer. Anal. 49 (2011), no. 6, 2430–2450. MR 2854603, DOI 10.1137/110824590
- Peter Benner, Jing-Rebecca Li, and Thilo Penzl, Numerical solution of large-scale Lyapunov equations, Riccati equations, and linear-quadratic optimal control problems, Numer. Linear Algebra Appl. 15 (2008), no. 9, 755–777. MR 2464169, DOI 10.1002/nla.622
- Peter Benner, Ren-Cang Li, and Ninoslav Truhar, On the ADI method for Sylvester equations, J. Comput. Appl. Math. 233 (2009), no. 4, 1035–1045. MR 2557293, DOI 10.1016/j.cam.2009.08.108
- H. W. Braden, The equations $A^\mathsf TX\pm X^\mathsf TA=B$, SIAM J. Matrix Anal. Appl. 20 (1999), no. 2, 295–302. MR 1646852, DOI 10.1137/S0895479897323270
- Ralph Byers and Daniel Kressner, Structured condition numbers for invariant subspaces, SIAM J. Matrix Anal. Appl. 28 (2006), no. 2, 326–347. MR 2255332, DOI 10.1137/050637601
- Françoise Chatelin, Simultaneous Newton’s iteration for the eigenproblem, Defect correction methods (Oberwolfach, 1983) Comput. Suppl., vol. 5, Springer, Vienna, 1984, pp. 67–74. MR 782690, DOI 10.1007/978-3-7091-7023-6_{4}
- Chun-Yueh Chiang, A note on the $\mathsf T$-Stein matrix equation, Abstr. Appl. Anal. , posted on (2013), Art. ID 824641, 8. MR 3090283, DOI 10.1155/2013/824641
- Chun-Yueh Chiang, Eric King-Wah Chu, and Wen-Wei Lin, On the $\bigstar$-Sylvester equation $AX\pm X^\bigstar B^\bigstar =C$, Appl. Math. Comput. 218 (2012), no. 17, 8393–8407. MR 2921333, DOI 10.1016/j.amc.2012.01.065
- Delin Chu, Wen-Wei Lin, and Roger C. E. Tan, A numerical method for a generalized algebraic Riccati equation, SIAM J. Control Optim. 45 (2006), no. 4, 1222–1250. MR 2257220, DOI 10.1137/050625035
- Fernando De Terán and Froilán M. Dopico, Consistency and efficient solution of the Sylvester equation for $\star$-congruence, Electron. J. Linear Algebra 22 (2011), 849–863. MR 2836789, DOI 10.13001/1081-3810.1479
- Fernando De Terán and Froilán M. Dopico, The solution of the equation $XA+AX^T=0$ and its application to the theory of orbits, Linear Algebra Appl. 434 (2011), no. 1, 44–67. MR 2737231, DOI 10.1016/j.laa.2010.08.005
- Fernando De Terán, Froilán M. Dopico, Nathan Guillery, Daniel Montealegre, and Nicolás Reyes, The solution of the equation $AX+X^\star B=0$, Linear Algebra Appl. 438 (2013), no. 7, 2817–2860. MR 3018044, DOI 10.1016/j.laa.2012.11.014
- J. W. Demmel, Three methods for refining estimates of invariant subspaces, Computing 38 (1987), no. 1, 43–57 (English, with German summary). MR 881679, DOI 10.1007/BF02253743
- A. El Guennouni, K. Jbilou, and A. J. Riquet, Block Krylov subspace methods for solving large Sylvester equations, Numer. Algorithms 29 (2002), no. 1-3, 75–96. Matrix iterative analysis and biorthogonality (Luminy, 2000). MR 1896947, DOI 10.1023/A:1014807923223
- Stephan Ramon Garcia and Amy L. Shoemaker, On the matrix equation $XA+AX^T=0$, Linear Algebra Appl. 438 (2013), no. 6, 2740–2746. MR 3008530, DOI 10.1016/j.laa.2012.10.041
- Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
- L. Grasedyck, Existence of a low rank or $\scr H$-matrix approximant to the solution of a Sylvester equation, Numer. Linear Algebra Appl. 11 (2004), no. 4, 371–389. MR 2057708, DOI 10.1002/nla.366
- Nicholas J. Higham, Accuracy and stability of numerical algorithms, 2nd ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. MR 1927606, DOI 10.1137/1.9780898718027
- Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985. MR 832183, DOI 10.1017/CBO9780511810817
- Roger A. Horn and Charles R. Johnson, Topics in matrix analysis, Cambridge University Press, Cambridge, 1994. Corrected reprint of the 1991 original. MR 1288752
- D. Y. Hu and L. Reichel, Krylov-subspace methods for the Sylvester equation, Linear Algebra Appl. 172 (1992), 283–313. Second NIU Conference on Linear Algebra, Numerical Linear Algebra and Applications (DeKalb, IL, 1991). MR 1168508, DOI 10.1016/0024-3795(92)90031-5
- Kh. D. Ikramov, On conditions for the unique solvability of the matrix equation $AX+X^TB=C$, Dokl. Akad. Nauk 430 (2010), no. 4, 444–447 (Russian); English transl., Dokl. Math. 81 (2010), no. 1, 63–65. MR 2675417, DOI 10.1134/S1064562410010187
- Imad M. Jaimoukha and Ebrahim M. Kasenally, Krylov subspace methods for solving large Lyapunov equations, SIAM J. Numer. Anal. 31 (1994), no. 1, 227–251. MR 1259974, DOI 10.1137/0731012
- Atsushi Kawamoto and Tohru Katayama, The semi-stabilizing solution of generalized algebraic Riccati equation for descriptor systems, Automatica J. IFAC 38 (2002), no. 10, 1651–1662. MR 2133524, DOI 10.1016/S0005-1098(02)00073-0
- A. Kawamoto, K. Takaba, and T. Katayama, On the generalized algebraic Riccati equation for continuous-time descriptor systems, Linear Algebra Appl. 296 (1999), no. 1-3, 1–14. MR 1713269, DOI 10.1016/S0024-3795(99)00079-8
- Daniel Kressner, Christian Schröder, and David S. Watkins, Implicit QR algorithms for palindromic and even eigenvalue problems, Numer. Algorithms 51 (2009), no. 2, 209–238. MR 2505842, DOI 10.1007/s11075-008-9226-3
- Thilo Penzl, A cyclic low-rank Smith method for large sparse Lyapunov equations, SIAM J. Sci. Comput. 21 (1999/00), no. 4, 1401–1418. MR 1742324, DOI 10.1137/S1064827598347666
- Thilo Penzl, Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case, Systems Control Lett. 40 (2000), no. 2, 139–144. MR 1829181, DOI 10.1016/S0167-6911(00)00010-4
- Youcef Saad, Numerical solution of large Lyapunov equations, Signal processing, scattering and operator theory, and numerical methods (Amsterdam, 1989) Progr. Systems Control Theory, vol. 5, Birkhäuser Boston, Boston, MA, 1990, pp. 503–511. MR 1115480
- Yousef Saad, Iterative methods for sparse linear systems, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003. MR 1990645, DOI 10.1137/1.9780898718003
- Yousef Saad, Numerical methods for large eigenvalue problems, Classics in Applied Mathematics, vol. 66, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2011. Revised edition of the 1992 original [ 1177405]. MR 3396212, DOI 10.1137/1.9781611970739.ch1
- V. Simoncini, Computational methods for linear matrix equations, to appear in SIAM Review (available at http://www.dm.unibo.it/ simoncin/list.html).
- V. Simoncini, On the numerical solution of $AX-XB=C$, BIT 36 (1996), no. 4, 814–830. MR 1420277, DOI 10.1007/BF01733793
- V. Simoncini, A new iterative method for solving large-scale Lyapunov matrix equations, SIAM J. Sci. Comput. 29 (2007), no. 3, 1268–1288. MR 2318706, DOI 10.1137/06066120X
- O. Taussky and H. Wielandt, On the matrix function $AX+X^{\prime } A^{\prime }$, Arch. Rational Mech. Anal. 9 (1962), 93–96. MR 132751, DOI 10.1007/BF00253335
- Yu. O. Vorontsov and Kh. D. Ikramov, A numerical algorithm for solving the matrix equation $AX+X^\textrm {T}B=C$, Zh. Vychisl. Mat. Mat. Fiz. 51 (2011), no. 5, 739–747 (Russian, with Russian summary); English transl., Comput. Math. Math. Phys. 51 (2011), no. 5, 691–698. MR 2859142, DOI 10.1134/S0965542511050058
- H.-S. Wang, C.-F. Yung, and F.-R. Chang, Bounded real lemma and $H_\infty$ control for descriptor systems, Proceedings of the American Control Conference, Albuquerque, New Mexico, June 1997 (1997), 2115–2119.
- Liqi Wang, Moody T. Chu, and Yu Bo, A computational framework of gradient flows for general linear matrix equations, Numer. Algorithms 68 (2015), no. 1, 121–141. MR 3296703, DOI 10.1007/s11075-014-9885-1
- H. K. Wimmer, Roth’s theorems for matrix equations with symmetry constraints, Linear Algebra Appl. 199 (1994), 357–362. MR 1274424, DOI 10.1016/0024-3795(94)90358-1
- Yongxin Yuan and Hua Dai, The direct updating of damping and gyroscopic matrices, J. Comput. Appl. Math. 231 (2009), no. 1, 255–261. MR 2532667, DOI 10.1016/j.cam.2009.02.007
Bibliographic Information
- Froilán M. Dopico
- Affiliation: Departamento de Matemáticas, Universidad Carlos III de Madrid, Avda. Universidad 30, 28911 Leganés, Spain
- MR Author ID: 664010
- Email: dopico@math.uc3m.es
- Javier González
- Affiliation: Departamento de Matemáticas, Universidad Carlos III de Madrid, Avda. Universidad 30, 28911 Leganés, Spain
- Email: jagpizar@math.uc3m.es
- Daniel Kressner
- Affiliation: ANCHP, MATHICSE, EPF Lausanne, Station 8, 1015 Lausanne, Switzerland
- Email: daniel.kressner@epfl.ch
- Valeria Simoncini
- Affiliation: Dipartimento di Matematica, Università di Bologna, Piazza di Porta San Donato 5, I-40127 Bologna, Italy
- Email: valeria.simoncini@unibo.it
- Received by editor(s): April 10, 2014
- Received by editor(s) in revised form: February 20, 2015
- Published electronically: January 12, 2016
- Additional Notes: The first and second authors were partially supported by Ministerio de Economía y Competitividad of Spain through grant MTM2012-32542.
- © Copyright 2016 American Mathematical Society
- Journal: Math. Comp. 85 (2016), 2427-2455
- MSC (2010): Primary 65F10, 65F30, 15A06
- DOI: https://doi.org/10.1090/mcom/3081
- MathSciNet review: 3511287