On the ADI method for Sylvester equations. (English) Zbl 1176.65050
Summary: This paper is concerned with the numerical solution of large scale Sylvester equations \(AX - XB=C\), Lyapunov equations as a special case in particular included, with \(C\) having very small rank. For stable Lyapunov equations, T. Penzl [SIAM J. Sci. Comput. 21, No. 4, 1401–1418 (1999; Zbl 0958.65052)] and J.-R. Li and J. White [SIAM J. Matrix Anal. Appl. 24, No. 1, 260–280 (2002; Zbl 1016.65024)] demonstrated that the so-called Cholesky factor ADI method with decent shift parameters can be very effective.
In this paper, we present a generalization of the Cholesky factor ADI method for Sylvester equations. An easily implementable extension of Penz’s shift strategy for the Lyapunov equation is presented for the current case. It is demonstrated that Galerkin projection via ADI subspaces often produces much more accurate solutions than ADI solutions.
In this paper, we present a generalization of the Cholesky factor ADI method for Sylvester equations. An easily implementable extension of Penz’s shift strategy for the Lyapunov equation is presented for the current case. It is demonstrated that Galerkin projection via ADI subspaces often produces much more accurate solutions than ADI solutions.
MSC:
| 65F30 | Other matrix algorithms (MSC2010) |
| 15A24 | Matrix equations and identities |
| 40C05 | Matrix methods for summability |
| 37L99 | Infinite-dimensional dissipative dynamical systems |
References:
| [1] | Lancaster, P.; Tismenetsky, M., The Theory of Matrices (1985), Academic Press: Academic Press Orlando · Zbl 0516.15018 |
| [2] | Bhatia, R.; Rosenthal, P., How and why to solve the operator equation \(A X - X B = Y\), Bull. Lond. Math. Soc., 29, 1-21 (1997) · Zbl 0909.47011 |
| [3] | Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, Maryland · Zbl 0865.65009 |
| [4] | Datta, B., Numerical Methods for Linear Control Systems (2004), Elsevier Academic Press · Zbl 1079.65072 |
| [5] | Antoulas, A. C., Approximation of Large-Scale Dynamical Systems, Advances in Design and Control (2005), SIAM: SIAM Philadelphia, PA · Zbl 1112.93002 |
| [6] | Baur, U.; Benner, P., Cross-gramian based model reduction for data-sparse systems, Electr. Trans. Num. Anal., 31, 256-270 (2008) · Zbl 1170.93315 |
| [7] | Sorensen, D.; Antoulas, A., The Sylvester equation and approximate balanced reduction, Linear Algebra Appl., 351-352, 671-700 (2002) · Zbl 1023.93012 |
| [8] | Enright, W., Improving the efficiency of matrix operations in the numerical solution of stiff ordinary differential equations, ACM Trans. Math. Softw., 4, 127-136 (1978) · Zbl 0382.65029 |
| [9] | Calvetti, D.; Reichel, L., Application of ADI iterative methods to the restoration of noisy images, SIAM J. Matrix Anal. Appl., 17, 165-186 (1996) · Zbl 0849.65101 |
| [10] | Bartels, R. H.; Stewart, G. W., Algorithm 432: The solution of the matrix equation \(A X - B X = C\), Commun. ACM, 8, 820-826 (1972) · Zbl 1372.65121 |
| [11] | Golub, G. H.; Nash, S.; Van Loan, C. F., Hessenberg-Schur method for the problem \(A X + X B = C\), IEEE Trans. Automat. Control, AC-24, 909-913 (1979) · Zbl 0421.65022 |
| [12] | Benner, P., Solving large-scale control problems, IEEE Control Syst. Mag., 14, 1, 44-59 (2004) |
| [13] | Bao, L.; Lin, Y.; Wei, Y., A new projection method for solving large Sylvester equations, Appl. Numer. Math., 57, 5-7, 521-532 (2007) · Zbl 1118.65028 |
| [14] | El Guennouni, A.; Jbilou, K.; Riquet, J., Block Krylov subspace methods for solving large Sylvester equations, Numer. Algorithms, 29, 75-96 (2002) · Zbl 0992.65040 |
| [15] | Hu, D. Y.; Reichel, L., Krylov-subspace methods for the Sylvester equation, Linear Algebra Appl., 172, 283-313 (1992) · Zbl 0777.65028 |
| [16] | Jbilou, K., Low rank approximate solutions to large Sylvester matrix equations, Appl. Math. Comput., 177, 365-376 (2006) · Zbl 1095.65041 |
| [17] | Simoncini, V., A new iterative method for solving large-scale Lyapunov matrix equations, SIAM J. Sci. Comput., 29, 1268-1288 (2007) · Zbl 1146.65038 |
| [18] | Benner, P.; Li, J.-R.; Penzl, T., Numerical solution of large Lyapunov equations, Riccati equations, and linear-quadratic control problems, Numer. Linear Algebra Appl., 15, 9, 755-777 (2008) · Zbl 1212.65245 |
| [19] | Gugercin, S.; Sorensen, D.; Antoulas, A., A modified low-rank Smith method for large-scale, Numer. Algorithms, 32, 27-55 (2003) · Zbl 1034.93020 |
| [20] | Li, J.-R.; White, J., Low-rank solution of Lyapunov equations, SIAM J. Matrix Anal. Appl., 24, 260-280 (2002) · Zbl 1016.65024 |
| [21] | Lu, A.; Wachspress, E., Solution of Lyapunov equations by ADI iteration, Comput. Math. Appl., 21, 43-58 (1991) · Zbl 0724.65041 |
| [22] | Penzl, T., A cyclic low-rank smith method for large sparse Lyapunov equations, SIAM J. Sci. Comput., 21, 1401-1418 (2000) · Zbl 0958.65052 |
| [23] | T. Penzl, LYAPACK: A MATLAB toolbox for large Lyapunov and Riccati equations, model reduction problems, and linear-quadratic optimal control problems, users’ guide (ver. 1.0), 2000. Available at: www.tu-chemnitz.de/sfb393/lyapack/; T. Penzl, LYAPACK: A MATLAB toolbox for large Lyapunov and Riccati equations, model reduction problems, and linear-quadratic optimal control problems, users’ guide (ver. 1.0), 2000. Available at: www.tu-chemnitz.de/sfb393/lyapack/ |
| [24] | Wachspress, E. L., Iterative solution of the Lyapunov matrix equation, Appl. Math. Lett., 1, 87-90 (1988) · Zbl 0631.65037 |
| [25] | Ding, F.; Chen, T., On iterative solutions of general coupled matrix equations, SIAM J. Control Optim., 44, 6, 2269-2284 (2005) · Zbl 1115.65035 |
| [26] | Ding, F.; Chen, T., Gradient based iterative algorithms for solving a class of matrix equations, IEEE Trans. Automat. Control, 50, 8, 1216-1221 (2005) · Zbl 1365.65083 |
| [27] | Ding, F.; Chen, T., Iterative least squares solutions of coupled Sylvester matrix equations, Systems Control Lett., 54, 2, 95-107 (2005) · Zbl 1129.65306 |
| [28] | Ding, F.; Liub, P. X.; Ding, J., Iterative solutions of the generalized Sylvester matrix equations by using the hierarchical identification principle, Appl. Math. Comput., 197, 41-50 (2008) · Zbl 1143.65035 |
| [29] | P. Benner, The matrix factorization paradigm in solving matrix equations, Householder Symposium XVI, Seven Springs, PA, May 2005. Available electronically at: http://www.tu-chemnitz.de/ benner/talks/hh05.pdf; P. Benner, The matrix factorization paradigm in solving matrix equations, Householder Symposium XVI, Seven Springs, PA, May 2005. Available electronically at: http://www.tu-chemnitz.de/ benner/talks/hh05.pdf |
| [30] | N. Truhar, R.-C. Li, On ADI method for Sylvester equations, Technical Report 2008-02, Department of Mathematics, University of Texas at Arlington, 2008. Available at: http://www.uta.edu/math/preprint/rep2008_02.pdf; N. Truhar, R.-C. Li, On ADI method for Sylvester equations, Technical Report 2008-02, Department of Mathematics, University of Texas at Arlington, 2008. Available at: http://www.uta.edu/math/preprint/rep2008_02.pdf · Zbl 1176.65050 |
| [31] | Wachspress, E., Trail to a Lyapunov equation solver, Comput. Math. Appl., 55, 1653-1659 (2008) · Zbl 1139.65033 |
| [32] | Benner, P.; Mena, H.; Saak, J., On the parameter selection problem in the Newton-ADI iteration for large-scale Riccati equations, Electron. Trans. Numer. Anal., 29, 136-149 (2008) · Zbl 1171.65402 |
| [33] | Ellner, N. S.; Wachspress, E. L., Alternating direction implicit iteration for systems with complex spectra, SIAM J. Numer. Anal., 3, 859-870 (1991) · Zbl 0737.65027 |
| [34] | Wachspress, E. L., The ADI Model Problem (1995), Windsor: Windsor CA · Zbl 0191.45301 |
| [35] | Li, J.-R.; White, J., Low-rank solution of Lyapunov equations, SIAM Rev., 46, 693-713 (2004) · Zbl 1068.65053 |
| [36] | J. Sabino, Solution of large-scale Lyapunov equations via the block modified Smith method, Ph.D. Thesis, Rice University, Houston, Texas, 2006; J. Sabino, Solution of large-scale Lyapunov equations via the block modified Smith method, Ph.D. Thesis, Rice University, Houston, Texas, 2006 |
| [37] | Demmel, J., Applied Numerical Linear Algebra (1997), SIAM: SIAM Phildelphia · Zbl 0879.65017 |
| [38] | E. Wachspress, Adi iteration parameters for solving Lyapunov and Sylvester equations, Technical Report, March, 2009; E. Wachspress, Adi iteration parameters for solving Lyapunov and Sylvester equations, Technical Report, March, 2009 |
| [39] | Simoncini, V., On the numerical solution of \(A X - X B = C\), BIT, 36, 814-830 (1996) · Zbl 0863.65022 |
| [40] | Benner, P.; Quintana-Ortí, E.; Quintana-Ortí, G., Solving stable Sylvester equations via rational iterative schemes, J. Sci. Comput., 28, 51-83 (2006) · Zbl 1098.65041 |
| [41] | Y. Chahlaoui, P. Van Dooren, A collection of benchmark examples for model reduction of linear time invariant dynamical systems, SLICOT Working Notes 2002-2, February 2002. Available at: www.win.tue.nl/niconet/NIC2/benchmodred.html; Y. Chahlaoui, P. Van Dooren, A collection of benchmark examples for model reduction of linear time invariant dynamical systems, SLICOT Working Notes 2002-2, February 2002. Available at: www.win.tue.nl/niconet/NIC2/benchmodred.html |
| [42] | Ding, F.; Chen, T., Hierarchical gradient-based identification of multivariable discrete-time systems, Automatica, 41, 2, 315-325 (2005) · Zbl 1073.93012 |
| [43] | Ding, F.; Chen, T., Hierarchical least squares identification methods for multivariable systems, IEEE Trans. Automat. Control, 50, 3, 397-402 (2005) · Zbl 1365.93551 |
| [44] | Penzl, T., Eigenvalue decay bounds for solutions of Lyapunov equations: The symmetric case, Systems Control Lett., 40, 139-144 (2000) · Zbl 0977.93034 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
