Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Projection methods for large-scale T-Sylvester equations


Authors: Froilán M. Dopico, Javier González, Daniel Kressner and Valeria Simoncini
Journal: Math. Comp. 85 (2016), 2427-2455
MSC (2010): Primary 65F10, 65F30, 15A06
DOI: https://doi.org/10.1090/mcom/3081
Published electronically: January 12, 2016
MathSciNet review: 3511287
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Athanasios C. Antoulas, Approximation of Large-scale Dynamical Systems, With a foreword by Jan C. Willems, Advances in Design and Control, vol. 6, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2005. MR 2155615 (2006c:93001)
  • [2] 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.
  • [3] M. Baumann and U. Helmke, Singular value decomposition of time-varying matrices, Future Generation Computer Systems 19 (2003), no. 3, 353-361.
  • [4] 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 (2012j:15021), https://doi.org/10.1137/110824590
  • [5] 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 (2009h:65069), https://doi.org/10.1002/nla.622
  • [6] 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 (2010k:15031), https://doi.org/10.1016/j.cam.2009.08.108
  • [7] H. W. Braden, The equations $ A^\mathsf {T}X\pm X^\mathsf {T}A=B$, SIAM J. Matrix Anal. Appl. 20 (1999), no. 2, 295-302 (electronic). MR 1646852 (99h:15014), https://doi.org/10.1137/S0895479897323270
  • [8] Ralph Byers and Daniel Kressner, Structured condition numbers for invariant subspaces, SIAM J. Matrix Anal. Appl. 28 (2006), no. 2, 326-347 (electronic). MR 2255332 (2007i:65036), https://doi.org/10.1137/050637601
  • [9] 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 (86f:65106), https://doi.org/10.1007/978-3-7091-7023-6_4
  • [10] Chun-Yueh Chiang, A note on the $ \mathsf {T}$-Stein matrix equation, Abstr. Appl. Anal. (2013), Art. ID 824641, 8. MR 3090283
  • [11] 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, https://doi.org/10.1016/j.amc.2012.01.065
  • [12] 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 (2007k:93052), https://doi.org/10.1137/050625035
  • [13] 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 (2012j:65110)
  • [14] 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 (2012a:15025), https://doi.org/10.1016/j.laa.2010.08.005
  • [15] 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, https://doi.org/10.1016/j.laa.2012.11.014
  • [16] J. W. Demmel, Three methods for refining estimates of invariant subspaces, Computing 38 (1987), no. 1, 43-57 (English, with German summary). MR 881679 (88d:65072), https://doi.org/10.1007/BF02253743
  • [17] A. El Guennouni, K. Jbilou, and A. J. Riquet, Block Krylov subspace methods for solving large Sylvester equations, Matrix iterative analysis and biorthogonality (Luminy, 2000), Numer. Algorithms 29 (2002), no. 1-3, 75-96. MR 1896947 (2003f:65055), https://doi.org/10.1023/A:1014807923223
  • [18] 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, https://doi.org/10.1016/j.laa.2012.10.041
  • [19] G. H. Golub and C. F. Van Loan, Matrix Computations, third ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720 (97g:65006)
  • [20] L. Grasedyck, Existence of a low rank or $ \mathcal {H}$-matrix approximant to the solution of a Sylvester equation, Numer. Linear Algebra Appl. 11 (2004), no. 4, 371-389. MR 2057708 (2005e:15016), https://doi.org/10.1002/nla.366
  • [21] Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. MR 1927606 (2003g:65064)
  • [22] Roger A. Horn and Charles R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1985. MR 832183 (87e:15001)
  • [23] Roger A. Horn and Charles R. Johnson, Topics in Matrix Analysis, Cambridge University Press, Cambridge, 1994. Corrected reprint of the 1991 original. MR 1288752 (95c:15001)
  • [24] D. Y. Hu and L. Reichel, Krylov-subspace methods for the Sylvester equation, Second NIU Conference on Linear Algebra, Numerical Linear Algebra and Applications (DeKalb, IL, 1991), Linear Algebra Appl. 172 (1992), 283-313. MR 1168508 (93c:65041), https://doi.org/10.1016/0024-3795(92)90031-5
  • [25] 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 (2011d:15026), https://doi.org/10.1134/S1064562410010187
  • [26] 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 (94m:65056), https://doi.org/10.1137/0731012
  • [27] 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, https://doi.org/10.1016/S0005-1098(02)00073-0
  • [28] 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 (2000f:93048), https://doi.org/10.1016/S0024-3795(99)00079-8
  • [29] 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 (2010a:65058), https://doi.org/10.1007/s11075-008-9226-3
  • [30] Thilo Penzl, A cyclic low-rank Smith method for large sparse Lyapunov equations, SIAM J. Sci. Comput. 21 (1999/00), no. 4, 1401-1418 (electronic). MR 1742324 (2001b:65053), https://doi.org/10.1137/S1064827598347666
  • [31] Thilo Penzl, Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case, Systems Control Lett. 40 (2000), no. 2, 139-144. MR 1829181 (2002b:93108), https://doi.org/10.1016/S0167-6911(00)00010-4
  • [32] 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
  • [33] Y. Saad, Iterative Methods for Sparse Linear Systems, second ed., Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003. MR 1990645 (2004h:65002)
  • [34] 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
  • [35] V. Simoncini, Computational methods for linear matrix equations, to appear in SIAM Review (available at http://www.dm.unibo.it/ simoncin/list.html).
  • [36] V. Simoncini, On the numerical solution of $ AX-XB=C$, BIT 36 (1996), no. 4, 814-830. MR 1420277 (97i:65053), https://doi.org/10.1007/BF01733793
  • [37] 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 (2008j:15031), https://doi.org/10.1137/06066120X
  • [38] O. Taussky and H. Wielandt, On the matrix function $ AX+X^{\prime } A^{\prime } $, Arch. Rational Mech. Anal. 9 (1962), 93-96. MR 0132751 (24 #A2588)
  • [39] Yu. O. Vorontsov and Kh. D. Ikramov, A numerical algorithm for solving the matrix equation $ AX+X^{\rm 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 (2012i:65080), https://doi.org/10.1134/S0965542511050058
  • [40] 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.
  • [41] 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, https://doi.org/10.1007/s11075-014-9885-1
  • [42] H. K. Wimmer, Roth's theorems for matrix equations with symmetry constraints, Linear Algebra Appl. 199 (1994), 357-362. MR 1274424 (96a:15013), https://doi.org/10.1016/0024-3795(94)90358-1
  • [43] 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 (2010h:65106), https://doi.org/10.1016/j.cam.2009.02.007

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65F10, 65F30, 15A06

Retrieve articles in all journals with MSC (2010): 65F10, 65F30, 15A06


Additional Information

Froilán M. Dopico
Affiliation: Departamento de Matemáticas, Universidad Carlos III de Madrid, Avda. Universidad 30, 28911 Leganés, Spain
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

DOI: https://doi.org/10.1090/mcom/3081
Keywords: Matrix equations, Krylov subspace, iterative methods, large-scale equations, Sylvester equation, Sylvester equation for congruence.
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.
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society