×

A computational framework of gradient flows for general linear matrix equations. (English) Zbl 1308.65065

Summary: Linear matrix equations such as the Sylvester equation, Lyapunov equation, Stein equation, and a variate of their generalizations are of significant importance in many applications. A conversion to a classical linear system \(\mathcal A\mathbf {x}=\mathbf {b}\) via the Kronecker product is generally regarded as the last resort because it significantly increases the size of the problem and disrespects any underlying structure. Convention Krylov subspace methods such as the generalized minimal residual (GMRES) method or the conjugate gradient method on the normal equation with minimal residual (CGNR) might not need the vectorization explicitly, but an otherwise well established preconditioner for \(\mathcal A\) encounters the difficulty that it must be disassembled and redistributed over the original matrix coefficients in order to complete evade the Kronecker vectorization. Thus many other techniques for solving linear matrix equations have been developed, which are usually problem dependent and can hardly be generalized when the equation is changed. In contrast, motivated by the notion of order-4 tensor equations, this paper proposes the idea of casting any linear matrix equation under the same framework of generalized normal equation and using low-precision gradient dynamics to achieve high-precision solution. A single computational paradigm therefore serves to handle all types of linear matrix equations. The flow approach has the advantages of being straightforward for implementation, uniform in theory, versatile in application, working directly with the original sizes without Kronecker vectorization, avoiding inversion or factorization, and being easy for convergence analysis. This paper outlines the theory, exemplifies a collection of applications, suggests a simple implementation, and reports some numerical evidences.

MSC:

65F30 Other matrix algorithms (MSC2010)
65F10 Iterative numerical methods for linear systems
15A24 Matrix equations and identities

Software:

mftoolbox
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P.-A. Absil, R. Mahony, B. Andrews: Convergence of the iterates of descent methods for analytic cost functions. SIAM. J. Optim. 16, 531-547 (2005) · Zbl 1092.90036
[2] P.-A. Absil, R. Mahony, R. Sepulchre: Optimization algorithms on matrix manifolds, Princeton University Press. NJ, Princeton (2008) · Zbl 1147.65043
[3] L. Ambrosio, N. Gigli, G. Savaré: Gradient flows in metric spaces and in the space of probability measures, Lectures in Mathematics ETH Zürich. Basel, second ed., Birkhäuser Verlag (2008) · Zbl 1145.35001
[4] A. C. Antoulas: Approximation of large-scale dynamical systems, vol. 6 of Advances in Design and Control, Society for Industrial and Applied Mathematics (SIAM), Philadelphia. With a foreword by Jan C. Willems, PA (2005)
[5] J. K. Baksalary, R. Kala: The matrix equation AX−YB=C. Linear Algebra Appl. 25, 41-43 (1979) · Zbl 0403.15010
[6] W. Behrman: An efficient gradient flow method for unconstrained optimization. Stanford University, PhD thesis (1998)
[7] R. Bhatia, P. Rosenthal: How and why to solve the operator equation AX−XB=Y. Bull. London Math. Soc. 29, 1-21 (1997) · Zbl 0909.47011
[8] H. W. Braden: The equations ATX±XTA=B. SIAM J. Matrix Anal. Appl. 20, 295-302 (1999). electronic
[9] J. Carr: Applications of centre manifold theory, vol. 35 of Applied Mathematical Sciences. Springer-Verlag, New York (1981) · Zbl 0464.58001
[10] R. Chill: On the Łojasiewicz-Simon gradient inequality. J.Funct. Anal. 201, 572-601 (2003) · Zbl 1036.26015
[11] M. T. Chu: Linear algebra algorithms as dynamical systems. Acta Numerica 17, 1-86 (2008) · Zbl 1165.65021
[12] H. Dai, P. Lancaster: Linear matrix equations from an inverse problem of vibration theory. Linear Algebra Appl. 246, 31-47 (1996) · Zbl 0861.15014
[13] F. De Terán, F. M. Dopico, N. Guillery, D. Montealegre, N. Reyes: The solution of the equation AX+X⋆B=0. Linear Algebra Appl. 438, 2817-2860 (2013) · Zbl 1264.15016
[14] M. Dehghan, M. Hajarian: An efficient algorithm for solving general coupled matrix equations and its application. Math. Comput. Modelling 51, 1118-1134 (2010) · Zbl 1208.65054
[15] F. Ding, T. Chen: On iterative solutions of general coupled matrix equations. SIAM J. Control Optim. 44, 2269-2284 (electronic). (2006) · Zbl 1115.65035
[16] P. A. Fuhrmann: A functional approach to the Stein equation. Linear Algebra Appl. 432, 3031-3071 (2010) · Zbl 1226.15009
[17] Z. Gajic, M. T. J. Qureshi: Lyapunov matrix equation in system stability and control, vol. 195 of Mathematics in Science and Engineering, Academic Press Inc. CA, San Diego (1995) · Zbl 1153.93300
[18] S. R. Garcia, A. L. Shoemaker: On the matrix equation XA+AXT=0. Linear Algebra Appl. 438, 2740-2746 (2013) · Zbl 1266.15023
[19] J. D. Gardiner, A. J. Laub, J. J. Amato, C. B. Moler: Solution of the Sylvester matrix equation AXB⊤+CXD⊤=E. ACM Trans. Math. Software 18, 223-231 (1992) · Zbl 0893.65026
[20] N. J. Higham: Functions of matrices, Society for Industrial and Applied Mathematics (SIAM). Philadelphia PA, Theory and computation (2008) · Zbl 1167.15001
[21] R. A. Horn, C. R. Johnson: Topics in matrix analysis. Cambridge University Press, Cambridge (1991) · Zbl 0729.15001
[22] D. Y. Hu, L. Reichel: Krylov-subspace methods for the sylvester equation. · Zbl 0777.65028
[23] K. D. Ikramov: On conditions for the unique solvability of the matrix equation AX+XTB=C. Dokl Akad. Nauk 430, 444-447 (2010)
[24] B. Kågström: A perturbation analysis of the generalized Sylvester equation (AR−LB,DR−LE)=(C,F). SIAM J. Matrix Anal. Appl. 15, 1045-1060 (1994) · Zbl 0805.65045
[25] C. T. Kelley , D. E. Keyes: Convergence analysis of pseudo-transient continuation. SIAM J. Numer. Anal. 35, 508-523 (electronic). (1998) · Zbl 0911.65080
[26] C. T. Kelley, L.-Z. Liao, L. Qi, M. T. Chu, J. P. Reese, C. Winton: Projected pseudotransient continuation. SIAM J. Numer. Anal. 46, 3071-3083 (2008) · Zbl 1180.65060
[27] A. Klein, P. Spreij: On Stein’s equation, Vandermonde matrices and Fisher’s information matrix of time series processes. I. The autoregressive moving average process. Linear Algebra Appl. 329, 9-47 (2001) · Zbl 0999.62069
[28] O. Koch, C. Lubich: Dynamical low-rank approximation. SIAM J. Matrix Anal. Appl. 29, 434-454 (2007) · Zbl 1145.65031
[29] M. Konstantinov , D.-W. Gu, V. Mehrmann, P. Petkov: Perturbation theory for matrix equations, vol. 9 of Studies in Computational Mathematics. North-Holland Publishing Co., Amsterdam (2003) · Zbl 1025.15017
[30] P. Lancaster: Explicit solutions of linear matrix equations. SIAM Rev. 12, 544-566 (1970) · Zbl 0209.06502
[31] L. Lerer, A. C. M. Ran: A new inertia theorem for Stein equations, inertia of invertible Hermitian block Toeplitz matrices and matrix orthogonal polynomials. Integral Equations Operator Theory 47, 339-360 (2003) · Zbl 1035.15016
[32] S. Li, Y. Li: Nonlinearly activated neural network for solving time-varying complex sylvester equation, p 285166. IEEE Transactions on Cybernetics (2013)
[33] A.-P. Liao, Z.-Z. Bai: Least squares symmetric and skew-symmetric solutions of the matrix equation AXAT+BYBT=C with the least norm. Math. Numer. Sin. 27, 81-95 (2005)
[34] A.-P. Liao, Z.-Z. Bai, Y. Lei: Best approximate solution of matrix equation AXB+CYD=E, SIAM. J. Matrix Anal. Appl. 27, 675-688 (2005) · Zbl 1096.15004
[35] A.-P. Liao, Y. Lei, X.-Y. Hu: Least-squares solution with the minimum-norm for the matrix equation ATXB+BTXTA=D and its applications. Acta Math. Appl. Sin Engl. Ser. 23, 269-280 (2007) · Zbl 1177.15018
[36] S. Łojasiewicz: Une propriété topologique des sous-ensembles analytiques réels, in Les Équations aux Dérivées Partielles (Paris, 1962), pp 87-89. Éditions du Centre National de la Recherche Scientifique, Paris (1963)
[37] S. Łojasiewicz, M.-A. Zurro: On the gradient inequality. Bull. Polish Acad. Sci. Math. 47, 143-145 (1999) · Zbl 0932.32009
[38] C. Lubich, I. V. Oseledets: A projector-splitting integrator for dynamical low-rank approximation. BIT 54, 171-188 (2014) · Zbl 1314.65095
[39] A. G. Mazko: Matrix equations, spectral problems and stability of dynamic systems, vol. 2 of Stability, Oscillations and Optimization of Systems. Cambridge Scientific Publishers, Cambridge (2008) · Zbl 1152.93300
[40] C. C. K. Mikkelsen: Numerical Methods for Large Lyapunov Equation, PhD thesis, Purdue University. West Lafayette, Indianna (2009)
[41] J. Nocedal, S. J. Wright: Numerical optimization, Springer Series in Operations Research and Financial Engineering. Springer, New York, second ed. (2006)
[42] A. B. Özgüler: The equation AXB+CYD=E over a principal ideal domain. SIAM. J. Matrix Anal. Appl. 12, 581-591 (1991) · Zbl 0742.15006
[43] N. Parikh, S. Boyd: Proximal algorithms. Foundation and Trends in Optimization 1, 123-231 (2013)
[44] Z.-Y. Peng, Y.-X. Peng: An efficient iterative method for solving the matrix equation AXB+CYD=E. Numer Linear Algebra Appl. 13, 473-485 (2006) · Zbl 1174.65389
[45] M. Pierre: Quelques applications de l’inégalit´e de Lojasiewicz à des discrétisations d’EDP. SMAI (2011). URL http://smai.emath.fr/smai2011/slides/mpierre/Slides.pdf.
[46] M. Robb, M. Sadkane: A convergence analysis of GMRES and FOM methods for Sylvester equations. Numerical Algorithms 30, 71-89 (2002) · Zbl 1005.65030
[47] W. E. Sadkane: The equations AX−YB=C and AX−XB=C in matrices. Proc. Amer. Math. Soc. 3, 392-396 (1952) · Zbl 0047.01901
[48] F. C. Silva, R. Simões: On the Lyapunov and Stein equations. II. Linear Algebra Appl. 426, 305-311 (2007) · Zbl 1141.15015
[49] V. Simocini: Computational methods for linear matrix equation, survey article, Università di Bologna. Bologna, Italy (2013). URL http://www.dm.unibo.it/simoncin/matrixeq.pdf.
[50] M. J. Todd: Semidefinite optimization. Acta Numer. 10, 515-560 (2001) · Zbl 1105.65334
[51] P. M. Van Dooren: Structured linear algebra problems in digital signal processing, in Numerical linear algebra, digital signal processing and parallel algorithms (Leuven, 1988) vol. 70 of NATO Adv. Sci. Inst. Ser. F Comput. Systems Sci., pp 361-384. Springer, Berlin (1991) · Zbl 0736.65032
[52] C. F. Van Loan: The ubiquitous Kronecker product, J. Comput. Appl. Math., 123 (2000), pp. 85-100. Vol. III. Linear algebra, Numerical analysis (2000) · Zbl 0966.65039
[53] L. Vandenberghe, S. Boyd: Semidefinite programming. SIAM Rev. 38, 49-95 (1996) · Zbl 0845.65023
[54] B. Vandereycken, S. Vandewalle: A Riemannian optimization approach for computing low-rank solutions of Lyapunov equations. SIAM Journal on Matrix Analysis and Applications 31, 2553-2579 (2010) · Zbl 1221.65108
[55] G. Xu, M. Wei, D, Zheng: On solutions of matrix equation AXB+CYD=F. Linear Algebra Appl. 279, 93-109 (1998) · Zbl 0933.15024
[56] J.-J. Zhang: A note on the iterative solutions of general coupled matrix equation. Appl Math. Comput. 217, 9380-9386 (2011) · Zbl 1217.65081
[57] B. Zhou, G.-R. Duan, Z.-Y. Li: Gradient based iterative algorithm for solving coupled matrix equations. Systems Control Lett. 58, 327-333 (2009) · Zbl 1159.93323
[58] B. Zhou, J. Lam, G.-R. Duan: Gradient-based maximal convergence rate iterative method for solving linear matrix equations. Int. J. Comput. Math. 87, 515-527 (2010) · Zbl 1188.65058
[59] K. Ziȩtak: On a particular case of the inconsistent linear matrix equation AX+YB=C. Linear Algebra Appl. 66, 249-258 (1985) · Zbl 0573.15008
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.