A Projection Method Based on Extended Krylov Subspaces for Solving Sylvester Equations
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.
[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.
[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.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:64701", author = "Yiqin Lin and Liang Bao and Yimin Wei", title = "A Projection Method Based on Extended Krylov Subspaces for Solving Sylvester Equations", 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.", volume = "5", number = "7", pages = "1099-7", }
