Projection methods for large-scale T-Sylvester equations

Dopico, Froilán; González, Javier; Kressner, Daniel; Simoncini, Valeria

doi:10.1090/mcom/3081

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 PDF

Math. Comp. 85 (2016), 2427-2455 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