A Projection Method Based on Extended Krylov Subspaces for Solving Sylvester Equations

Authors: Yiqin Lin, Liang Bao, Yimin Wei

Abstract:

In this paper we study numerical methods for solving Sylvester matrix equations of the form AX +XBT +CDT = 0. A new projection method is proposed. The union of Krylov subspaces in A and its inverse and the union of Krylov subspaces in B and its inverse are used as the right and left projection subspaces, respectively. The Arnoldi-like process for constructing the orthonormal basis of the projection subspaces is outlined. We show that the approximate solution is an exact solution of a perturbed Sylvester matrix equation. Moreover, exact expression for the norm of residual is derived and results on finite termination and convergence are presented. Some numerical examples are presented to illustrate the effectiveness of the proposed method.

Keywords: Arnoldi process, Krylov subspace, Iterative method, Sylvester equation, Dissipative matrix.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1085555

References:

[1] A. C. Antoulas, Approximation of Large-scale Dynamical Systems, SIAM, Philadelphia, PA, 2005.
[2] Z. Bai, D. Day, J. Demmel and J. Dongarra, A Test Matrix Collection for Non-Hermitian Eigenvalue Problems (Release 1.0), Available at http://www.cs.ucdavis.edu/ bai/NEP/document/collection.ps, 1996.
[3] L. Bao, Y. Lin and Y. Wei, A new projection method for solving large Sylvester equations, Appl. Numer. Math., 57(2007), 521-532.
[4] R. H. Bartels and G. W. Stewart, Algorithm 432: Solution of the matrix equation AX + XB = C, Comm. ACM, 15(1972), 820-826.
[5] U. Baur and P. Benner, Factorized solution of Lyapunov equations based on hierarchical matrix arithmetic, Computing, 78(2006), 211-234.
[6] U. Baur and P. Benner, Cross-gramian based model reduction for datasparse systems, Tech. rep., Fakult¨at f¨ur mathematik, TU Chemnitz, 09107 Chemnitz, FRG, submitted for publication, 2007.
[7] P. Benner, E. S. Quintana-Ort'─▒ and G. Quintana-Ort'─▒, Solving stable Sylvester equations via rational iterative schemes, J. Sci. Comput., 28(2006), 51-83.
[8] P. Benner, R.-C. Li, and N. Truhar, On the ADI method for Sylvester equations, preprint.
[9] R. Bhatia and P. Rosenthal, How and why to solve the operator equation AX − XB = Y , Bull. London Math. Soc., 29(1997), 1-21.
[10] A. Bouhamidi, K. Jbilou, Sylvester Tikhonov-regularization methods in image restoration, J. Comput. Appl. Math., 206(2007), 86-98.
[11] B. N. Datta, Numerical Methods for Linear Control Systems: Design and Analysis, Elsevier Academic Press, Amsterdam, 2004.
[12] J. W. Demmel, Applied Numerical Linear Algebra, SIAM, Philadelphia, 1997.
[13] V. Druskin and L. Knizhnerman, Extended Krylov subspaces: Approximation of the matrix square root and related functions, SIAM J. Matrix Anal. Appl., 19(1998), 755-771.
[14] E. de Souza and S. P. Bhattacharyya, Contollability, observability and solution of AX −XB = C, Linear Algebra Appl., 39(1981), 167-188.
[15] S. C. Eisenstat, H. C. Elman, and M. H. Schultz, Variational iterative methods for nonsymmetric systems of linear equations, SIAM J. Numer. Anal., 20(1983), 345-357.
[16] A. El Guennouni, K. Jbilou and J. Riquet, Krylov subspace methods for solving large Sylvester equations, Numer. Algorithms, 29(2002), 75-96.
[17] G. H. Golub, S. Nash and C. Van Loan, A Hessenberg-Schur method for the problem AX+XB = C, IEEE Trans. Automat. Control, 24(1979), 909-913.
[18] G. H. Golub and C. F. Van Loan, Matrix Computations, 3rd edition, John Hopkins University Press, Baltimore, 1996.
[19] S. Gugercin, D. C. Sorensen, and A. C. Antoulas, A modified low-rank Smith method for large-scale Lyapunov equations, Numer. Algorithms, 32(2003), 27-55.
[20] S. J. Hammarling, Numerical solution of the stable non-negative definite Lyapunov equation, IMA J. Numer. Anal., 2(1982), 303-323.
[21] J. Z. Hearon, Nonsingular solutions of TA−BT = C, Linear Algebra Appl., 16(1997), 57-63.
[22] N. J. Higham, Accuracy and Stability of Numerical Algorithms, SIAM, Second Edition, 2002.
[23] D. Y. Hu and L. Reichel, Krylov-subspace methods for the Sylvester equation, Linear Algebra Appl., 172(1992), 283-313.
[24] I. M. Jaimoukha and E. M. Kasenally, Krylov subspace methods for solving large Lyapunov equations, SIAM J. Numer. Anal., 31(1994), 227-251.
[25] K. Jbilou, A. Messaoudi and H. Sadok, Global FOM and GMRES algorithms for matrix equations, Appl. Numer. Math., 31(1999), 49-63.
[26] K. Jbilou and A. J. Riquet, Projection methods for large Lyapunov matrix equations, Linear Algebra Appl., 415(2006), 344-358.
[27] D. Kressner, Block variants of Hammarling-s method for solving Lyapunov equations, ACM Trans. Math. Software, 34(2008), 1-15.
[28] A. J. Laub, M. T. Heath, C. C. Paige and R. C.Ward, Computation of system balancing transformations and other applications of simultaneous diagonalization algorithms, IEEE Trans. Automat. Control, 32(1987), 115-122.
[29] P. Lancaster and M. Tismenetsky, The Theory of Matrices, 2nd edition, Academic Press, Orlando, 1985.
[30] J.-R. Li and J. White, Low rank solution of Lyapunov equations, SIAM J. Matrix Anal. Appl., 24(2002), 260-280.
[31] A. Lu and E. Wachspress, Solution of Lyapunov equations by alternating direction implicit iteration, Comput. Math. Appl., 21(1991), 43-58.
[32] The MathWorks, Inc., MATLAB 7, September 2004.
[33] T. Penzl, A cyclic low-rank Smith method for large sparse Lyapunov equations, SIAM J. Sci. Comput., 21(2000), 1401-1418.
[34] M. Robbe and M. Sadkane, A convergence analysis of GMRES and FOM methods for Sylvester equations, Numer. Algorithms, 30(2002), 71-84.
[35] A. Ruhe, Numerical aspects of Gramm-Schmidt orthogonalization of vectors, Linear Algebra Appl., 52(1983), 591-601.
[36] Y. Saad and M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7(1986), 856-869.
[37] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd edition., SIAM, Philadelphia, 2003.
[38] V. Simoncini, A new iterative method for solving large-scale Lyapunov matrix equations, SIAM J. Sci. Comput., 29(2007), 1268-1288.
[39] V. Simoncini and D. B. Szyld, Theory of inexact Krylov subspace methods and applications to scientific computing, SIAM J. Sci. Comput., 25(2003), 454-477.
[40] V. Simoncini and D. B. Szyld, New conditions for non-stagnation of minimal residual methods, Numer. Math., 109(2008), 477-487.
[41] R. Smith, Matrix equation XA + BX = C, SIAM J. Appl. Math., 16(1968), pp. 198-201.
[42] D. C. Sorensen and A. C. Antoulas, The Sylvester equation and approximate balanced reduction, Linear Algebra Appl., 352(2002), 671- 700.
[43] D. C. Sorensen and Y. Zhou, Direct methods for matrix Sylvester and Lyapunov equations, J. Appl. Math., 6(2003), 277-303.
[44] E. Wachspress, Iterative solution of the Lyapunov matrix equation, Appl. Math. Lett., 107(1988), 87-90.