Dmytryshyn, Andrii; Fasi, Massimiliano; Gulliksson, Mårten The dynamical functional particle method for multi-term linear matrix equations. (English) Zbl 1510.65078 Appl. Math. Comput. 435, Article ID 127458, 10 p. (2022). Summary: Recent years have seen a renewal of interest in multi-term linear matrix equations, as these have come to play a role in a number of important applications. Here, we consider the solution of such equations by means of the dynamical functional particle method, an iterative technique that relies on the numerical integration of a damped second order dynamical system. We develop a new algorithm for the solution of a large class of these equations, a class that includes, among others, all linear matrix equations with Hermitian positive definite or negative definite coefficients. In numerical experiments, our MATLAB implementation outperforms existing methods for the solution of multi-term Sylvester equations. For the Sylvester equation \(AX + XB = C\), in particular, it can be faster and more accurate than the built-in implementation of the Bartels-Stewart algorithm, when \(A\) and \(B\) are well conditioned and have very different size. MSC: 65F45 Numerical methods for matrix equations 15A24 Matrix equations and identities Keywords:linear matrix equation; discrete functional particle method; Lyapunov equation; Sylvester equation; generalized Sylvester equation Software:mctoolbox PDFBibTeX XMLCite \textit{A. Dmytryshyn} et al., Appl. Math. Comput. 435, Article ID 127458, 10 p. (2022; Zbl 1510.65078) Full Text: DOI References: [1] Sylvester, J. J., Sur l’equations en matrices \(p x = x q\), C. R. Acad. Sci. Paris, 99, 2, 67-71 (1884) · JFM 16.0108.03 [2] Bouhamidi, A.; Jbilou, K., A note on the numerical approximate solutions for generalized Sylvester matrix equations with applications, Appl. Math. Comput., 206, 2, 687-694 (2008) · Zbl 1162.65019 [3] Zhou, B.; Duan, G.-R., On the generalized Sylvester mapping and matrix equations, Syst. Control Lett., 57, 3, 200-208 (2008) · Zbl 1129.93018 [4] Konstantinov, M.; Gu, D.-W.; Mehrmann, V.; Petkov, P., Perturbation theory for matrix equations, Studies in Computational Mathematics, volume 9 (2003), Elsevier: Elsevier Amsterdam, The Netherlands · Zbl 1025.15017 [5] Lancaster, P., Explicit solutions of linear matrix equations, SIAM Rev., 12, 4, 544-566 (1970) · Zbl 0209.06502 [6] Ben-Israel, A.; Greville, T. N., Generalized inverses: theory and applications, CMS Books in Mathematics (2003), Springer-Verlag: Springer-Verlag New York · Zbl 1026.15004 [7] Benner, P.; Damm, T., Lyapunov equations, energy functionals, and model order reduction of bilinear and stochastic systems, SIAM J. Control Optim., 49, 2, 686-711 (2011) · Zbl 1217.93158 [8] Gajić, Z.; Qureshi, M. T.J., Lyapunov matrix equation in system stability and control, Mathemtics in Scinences and Engineering, volume 195 (1995), Academic Press: Academic Press San Diego, CA, USA · Zbl 1153.93300 [9] Simoncini, V., Computational methods for linear matrix equations, SIAM Rev., 58, 3, 377-441 (2016) · Zbl 1386.65124 [10] Bartels, R. H.; Stewart, G. W., Algorithm 432: solution of the matrix equation \(A X + X B = C\), Comm. ACM, 15, 9, 820-826 (1972) · Zbl 1372.65121 [11] Dmytryshyn, A.; Kågström, B., Coupled Sylvester-type matrix equations and block diagonalization, SIAM J. Matrix Anal. Appl., 36, 2, 580-593 (2015) · Zbl 1328.15028 [12] Feng, Y.; Yagoubi, M., Robust control of linear descriptor systems, Studies in Systems, Decision and Control (2017), Springer-Verlag: Springer-Verlag Singapore · Zbl 1402.93005 [13] Higham, N. J., Accuracy and stability of numerical algorithms (2002), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 1011.65010 [14] Gray, W. S.; Mesko, J., Energy functions and algebraic Gramians for bilinear systems, IFAC P. Vol., 31, 17, 101-106 (1998) [15] Hartmann, C.; Schäfer-Bung, B.; Thöns-Zueva, A., Balanced averaging of bilinear systems with applications to stochastic control, SIAM J. Control Optim., 51, 3, 2356-2378 (2013) · Zbl 1273.35273 [16] Elman, H. C.; Furnival, D. G.; Powell, C. E., \( H ( \text{div} )\) Preconditioning for a mixed finite element formulation of the diffusion problem with random data, Math. Comp., 79, 270, 733-760 (2009) · Zbl 1216.65155 [17] Ernst, O. G.; Powell, C. E.; Silvester, D. J.; Ullmann, E., Efficient solvers for a linear stochastic Galerkin mixed formulation of diffusion problems with random data, SIAM J. Sci. Comput., 31, 2, 1424-1447 (2009) · Zbl 1187.35298 [18] Powell, C. E.; Silvester, D.; Simoncini, V., An efficient reduced basis solver for stochastic Galerkin matrix equations, SIAM J. Sci. Comput., 39, 1, A141-A163 (2017) · Zbl 1381.35257 [19] Edvardsson, S.; Gulliksson, M.; Persson, J., The dynamical functional particle method: an approach for boundary value problems, J. Appl. Mech., 79, 2 (2012) [20] Watkins, D. S., Francis’s algorithm, Amer. Math. Month., 118, 5, 387-403 (2011) · Zbl 1214.65016 [21] Watkins, D. S., Understanding the \(Q R\) algorithm, SIAM Rev., 24, 4, 427-440 (1982) · Zbl 0525.65018 [22] Watkins, D. S., The \(Q R\) algorithm revisited, SIAM Rev., 50, 1, 133-145 (2008) · Zbl 1134.65028 [23] Golub, G. H.; Van Loan, C. F., Matrix computations (2013), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD, USA · Zbl 1268.65037 [24] Fasi, M.; Higham, N. J., Multiprecision algorithms for computing the matrix logarithm, SIAM J. Matrix Anal. Appl., 39, 1, 472-491 (2018) · Zbl 1390.15073 [25] 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 [26] Ding, F.; Chen, T., On iterative solutions of general coupled matrix equations, SIAM J. Control Optim., 44, 6, 2269-2284 (2006) · Zbl 1115.65035 [27] Benner, P.; Li, R.-C.; Truhar, N., On the ADI method for Sylvester equations, J. Comput. Appl. Math., 233, 4, 1035-1045 (2009) · Zbl 1176.65050 [28] Gulliksson, M., The discrete dynamical functional particle method for solving constrained optimization problems, Dolomites Res. Notes Approx., 10, Special Issue, 6-12 (2017) · Zbl 1370.90262 [29] Gulliksson, M.; Ögren, M.; Oleynik, A.; Zhang, Y., Damped dynamical systems for solving equations and optimization problems, Handbook Math. Art. Sci., 1-44 (2018) [30] Edvardsson, S.; Neuman, M.; Edström, P.; Olin, H., Solving equations through particle dynamics, Comput. Phys. Comm., 197, 169-181 (2015) · Zbl 1351.74163 [31] Hairer, E.; Wanner, G.; Lubich, C., Geometric numerical integration: structure-preserving algorithms for ordinary differential equations, Springer Series in Computational Mathematics (2006), Springer-Verlag: Springer-Verlag Berlin, Heidelberg · Zbl 1094.65125 [32] Saad, Y., Numerical methods for large eigenvalue problems (2011), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 1242.65068 [33] Druskin, V.; Knizhnerman, L., Extended Krylov subspaces: approximation of the matrix square root and related functions, SIAM J. Matrix Anal. Appl., 19, 3, 755-771 (1998) · Zbl 0912.65022 [34] Horn, R. A.; Johnson, C. R., Topics in matrix analysis (1991), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 0729.15001 [35] Fehr, J.; Heiland, J.; Himpe, C.; Saak, J., Best practices for replicability, reproducibility and reusability of computer-based experiments exemplified by model reduction software, AIMS Math., 1, 3, 261-281 (2016) · Zbl 07129995 [36] IEEE Standard for floating-point arithmetic, IEEE std 754-2019 (revision of IEEE std 754-2008) (2019), Institute of Electrical and Electronics Engineers: Institute of Electrical and Electronics Engineers Piscataway, NJ, USA [37] Reprinted in SIGPAN Notices 22(2) (1987) 9-25. [38] IEEE Standard for floating-point arithmetic, IEEE std 754-2008 (revision of IEEE std 754-1985) (2008), Institute of Electrical and Electronics Engineers: Institute of Electrical and Electronics Engineers Piscataway, NJ, USA [39] Fasi, M.; Higham, N. J., Generating extreme-scale matrices with specified singular values or condition numbers, SIAM J. Sci. Comput., 43, 1, A663-A684 (2021) · Zbl 1462.65041 [40] Golub, G. H.; Nash, S.; Van Loan, C. F., A Hessenberg-Schur method for the problem \(A X + X B = C\), IEEE Trans. Automat. Control, AC-24, 6, 909-913 (1979) · Zbl 0421.65022 [41] Saad, Y., Iterative methods for sparse linear systems (2003), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 1002.65042 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.