×

Low rank solution of data-sparse Sylvester equations. (English) Zbl 1212.65173

Summary: A method for solving large-scale Sylvester equations is presented. The method is based on the sign function iteration and is particularly effective for Sylvester equations with factorized right-hand side. In this case, the solution will be computed in factored form as it is for instance required in model reduction. The hierarchical matrix format and the corresponding formatted arithmetic are integrated in the iteration scheme to make the method feasible for large-scale computations.

MSC:

65F30 Other matrix algorithms (MSC2010)
15A24 Matrix equations and identities
65F50 Computational methods for sparse matrices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Lancaster, The Theory of Matrices (1985) · Zbl 0578.62099
[2] Lancaster, Explicit solutions of linear matrix equation, SIAM Review 12 pp 544– (1970) · Zbl 0209.06502
[3] BennerP, MehrmannV, SorensenD (eds). Dimension Reduction of Large-scale Systems. Lecture Notes in Computational Science and Engineering, vol. 45. Springer: Berlin, Heidelberg, Germany, 2005.
[4] Moore, Principal component analysis in linear systems: controllability, observability, and model reduction, IEEE Transactions on Automatic Control AC-26 pp 17– (1981) · Zbl 0464.93022
[5] Fernando, On the structure of balanced and other principal representations of SISO systems, IEEE Transactions on Automatic Control 28 (2) pp 228– (1983) · Zbl 0507.93021
[6] Bartels, Solution of the matrix equation AX+XB=C: algorithm 432, Communications of the ACM 15 pp 820– (1972) · Zbl 1372.65121
[7] Enright, Improving the efficiency of matrix operations in the numerical solution of stiff ordinary differential equations, ACM Transactions on Mathematical Software 4 pp 127– (1978) · Zbl 0382.65029
[8] Golub, A Hessenberg-Schur method for the problem AX+XB=C, IEEE Transactions on Automatic Control AC-24 pp 909– (1979)
[9] Golub, Matrix Computations (1996)
[10] Grasedyck L, Hackbusch W. A multigrid method to solve large scale Sylvester equations. Preprint 48, Max-Planck Institut für Mathematik in den Naturwissenschaften, Leipzig, Germany, 2004. · Zbl 1154.65024
[11] Hu, Krylov-subspace methods for the Sylvester equation, Linear Algebra and its Applications 172 pp 283– (1992) · Zbl 0777.65028
[12] Wachspress, Iterative solution of the Lyapunov matrix equation, Applied Mathematics Letters 107 pp 87– (1988) · Zbl 0631.65037
[13] Roberts, Linear model reduction and solution of the algebraic Riccati equation by use of the sign function, International Journal of Control 32 pp 677– (1980) · Zbl 0463.93050
[14] Benner P. Factorized solution of Sylvester equations with applications in control. Proceedings of International Symposium on Mathematical Theory of Networks and Systems, MTNS 2004, Leuven, Belgium, 2004. Available from:http://www.mtns2004.be.
[15] Antoulas, On the decay rate of Hankel singular values and related issues, Systems and Control Letters 46 (5) pp 323– (2002) · Zbl 1003.93024
[16] Grasedyck, Existence of a low rank or H-matrix approximant to the solution of a Sylvester equation, Numerical Linear Algebra with Applications 11 pp 371– (2004) · Zbl 1164.65381
[17] Penzl, A cyclic low rank Smith method for large sparse Lyapunov equations, SIAM Journal on Scientific Computing 21 (4) pp 1401– (2000) · Zbl 0958.65052
[18] Grasedyck L. Theorie und Anwendungen Hierarchischer Matrizen. Dissertation, University of Kiel, Kiel, Germany, 2001 (in German). Available from:http://e-diss.uni-kiel.de/diss_454.
[19] Grasedyck, Construction and arithmetics of matrices, Computing 70 (4) pp 295– (2003) · Zbl 1030.65033
[20] Hackbusch, A sparse matrix arithmetic based on matrices. I. Introduction to matrices, Computing 62 (2) pp 89– (1999) · Zbl 0927.65063
[21] Hackbusch, A sparse matrix arithmetic. II. Application to multi-dimensional problems, Computing 64 (1) pp 21– (2000) · Zbl 0962.65029
[22] Grasedyck, Solution of large scale algebraic matrix Riccati equations by use of hierarchical matrices, Computing 70 pp 121– (2003) · Zbl 1239.65026
[23] Baur, Factorized solution of Lyapunov equations based on hierarchical matrix arithmetic, Computing 78 (3) pp 211– (2006) · Zbl 1111.65039
[24] Benner, Solving stable generalized Lyapunov equations with the matrix sign function, Numerical Algorithms 20 (1) pp 75– (1999) · Zbl 0940.65035
[25] Bai, Proceedings of the Sixth SIAM Conference on Parallel Processing for Scientific Computing pp 391– (1993)
[26] Byers, Solving the algebraic Riccati equation with the matrix sign function, Linear Algebra and its Applications 85 pp 267– (1987) · Zbl 0611.65027
[27] Higham, Computing the polar decomposition-with applications, SIAM Journal on Scientific and Statistical Computing 7 pp 1160– (1986) · Zbl 0607.65014
[28] Benner, Solving stable Sylvester equations via rational iterative schemes, Journal of Scientific Computing 28 (1) pp 51– (2006) · Zbl 1098.65041
[29] Anderson, LAPACK Users’ Guide (1999) · Zbl 0934.65030 · doi:10.1137/1.9780898719604
[30] Lawson, Basic linear algebra subprograms for FORTRAN usage, ACM Transactions on Mathematical Software 5 pp 303– (1979) · Zbl 0412.65022
[31] Bischof, Algorithm 782: codes for rank-revealing QR factorizations of dense matrices, ACM Transactions on Mathematical Software 24 (2) pp 254– (1998) · Zbl 0932.65034
[32] Börm S, Grasedyck L, Hackbusch W. HLib 1.2, 2004. Available from:http://www.hlib.org.
[33] Higham, Accuracy and Stability of Numerical Algorithms (1996) · Zbl 0847.65010
[34] Benner, Dimension Reduction of Large-scale Systems pp 5– (2005)
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.