×

zbMATH — the first resource for mathematics

Weighted and deflated global GMRES algorithms for solving large Sylvester matrix equations. (English) Zbl 1420.65040
Summary: The solution of a large-scale Sylvester matrix equation plays an important role in control and large scientific computations. In this paper, we are interested in the large Sylvester matrix equation with large dimension \(A\) and small dimension \(B\), and a popular approach is to use the global Krylov subspace method. In this paper, we propose three new algorithms for this problem. We first consider the global GMRES algorithm with weighting strategy, which can be viewed as a precondition method. We present three new schemes to update the weighting matrix during iterations. Due to the growth of memory requirements and computational cost, it is necessary to restart the algorithm effectively. The deflation strategy is efficient for the solution of large linear systems and large eigenvalue problems; to the best of our knowledge, little work is done on applying deflation to the (weighted) global GMRES algorithm for large Sylvester matrix equations. We then consider how to combine the weighting strategy with deflated restarting, and propose a weighted global GMRES algorithm with deflation for solving large Sylvester matrix equations. In particular, we are interested in the global GMRES algorithm with deflation, which can be viewed as a special case when the weighted matrix is chosen as the identity. Theoretical analysis is given to show rationality of the new algorithms. Numerical experiments illustrate the numerical behavior of the proposed algorithms.
MSC:
65F10 Iterative numerical methods for linear systems
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A24 Matrix equations and identities
65F30 Other matrix algorithms (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agoujil, S.; Bentbib, AH; Jabilou, K.; Sadek, EM, A minimal residual norm method for large-scale Sylvester matrix equations, Electron. Tran. Numer. Anal., 43, 45-59, (2014) · Zbl 1302.65096
[2] Bartels, R.; Stewart, GW, Algorithm 432: The solution of the matrix equation AX - XB = c, Commun. ACM, 8, 820-826, (1972) · Zbl 1372.65121
[3] Benner, P.; Li, R.; Truhar, N., On the ADI method for Sylvester equations, J. Comput. Appl. Math., 223, 1035-1045, (2009) · Zbl 1176.65050
[4] Bouhamidi, A.; Jbilou, K., A note on the numerical approximate solutions for generalized Sylvester matrix equations with applications, Appl. Math. Comput., 206, 687-694, (2008) · Zbl 1162.65019
[5] Calvetti, D., Application of ADI iterative methods to the restoration of noisy images, SIAM J. Matrix Anal. Appl., 17, 165-186, (1996) · Zbl 0849.65101
[6] Datta, B.N.: Numerical Methods for Linear Control Systems Design and Analysis. Elsevier Press (2003)
[7] Datta, B.N., Datta, K.: Theoretical and computational aspects of some linear algebra problems in control theory. In: Byrnes, C. I., Lindquist, A. (eds.) Computational and Combinatorial Methods in Systems Theory, vol. 177, pp 201-212. Elsevier, Amsterdam (1986)
[8] Dehghan, M.; Hajarian, M., Two algorithms for finding the Hermitian reflexive and skew-Hermitian solutions of Sylvester matrix equations, Appl. Math. Lett., 24, 444-449, (2011) · Zbl 1206.65144
[9] Duan, C.; Jia, Z., A global harmonic Arnoldi method for large non-Hermitian eigenproblems with an application to multiple eigenvalue problems, J. Comput. Appl. Math., 234, 845-860, (2010) · Zbl 1188.65041
[10] Embree, M.; Morgan, RB; Nguyen, HV, Weighted inner products for GMRES and GMRES-DR, SIAM J. Sci. Comp., 39, s610-s632, (2017) · Zbl 1392.65051
[11] Essai, A., Weighted, FOM and GMRES for solving nonsymmetric linear systems, Numer. Alg., 18, 277-292, (1998) · Zbl 0926.65036
[12] The University of Florida Sparse Matrix Collection, https://www.cise.ufl.edu/research/sparse/matrices
[13] El Guennouni, A.; Jbilou, K.; Riquet, AJ, Block Krylov subspace methods for solving large Sylvester equations, Numer. Alg., 29, 75-96, (2002) · Zbl 0992.65040
[14] Güttel, S.; Pestana, J., Some observations on weighted GMRES, Numer. Alg., 67, 733-752, (2014) · Zbl 1304.65127
[15] Heyouni, M., Extended Arnoldi methods for large low-rank Sylvester matrix equations, Appl. Numer. Math., 60, 1171-1182, (2010) · Zbl 1210.65093
[16] Heyouni, M.; Essai, A., Matrix Krylov subspace methods for linear systems with multiple right-hand sides, Numer. Alg., 40, 137-156, (2005) · Zbl 1087.65028
[17] Jaimoukha, IM; Kasenally, EM, Krylov subspace methods for solving large Lyapunov equations, SIAM J. Numer. Anal., 31, 227-251, (1994) · Zbl 0798.65060
[18] Jbilou, K.; Messaoudi, A.; Sadok, H.; Global, FOM, GMRES algorithms for matrix equations, Appl. Numer Math., 31, 49-63, (1999) · Zbl 0935.65024
[19] Jbilou, K.; Riquet, AJ, Projection methods for large Lyapunov matrix equations, Linear Alg. Appl., 415, 344-358, (2006) · Zbl 1094.65039
[20] Jiang, W.; Wu, G., A thick-restarted block Arnoldi algorithm with modified Ritz vectors for large eigenproblems, Comput. Math. Appl., 60, 873-889, (2010) · Zbl 1201.65053
[21] Khorsand Zak, M.; Toutounian, F., Nested splitting CG-like iterative method for solving the continuous Sylvester equation and preconditioning, Adv. Comput. Math., 40, 865-880, (2013) · Zbl 1295.15011
[22] Liesen, J., Strakos, Z.: Krylov Subspace Methods, Principles and Analysis. Oxford University Press (2013) · Zbl 1263.65034
[23] Lin, Y., Minimal residual methods augmented with eigenvectors for solving Sylvester equations and generalized Sylvester equations, Appl. Math. Comput., 181, 487-499, (2006) · Zbl 1148.65029
[24] Lin, Y., Implicitly restarted global, FOM and GMRES for nonsymmetric matrix equations and Sylvester equations, Appl. Math. Comput., 167, 1004-1025, (2005) · Zbl 1081.65038
[25] Lin, Y.; Bao, L.; Wei, Y., A projection method based on extended krylov subspaces for solving Sylvester equations, Int. J. Math. Comput. Phys. Elec. Comput. Eng., 5, 1064-1070, (2011)
[26] Lin, Y.; Simoncini, V., Minimal residual methods for large scale Lyapunov equations, Appl. Numer. Math., 72, 52-71, (2013) · Zbl 1302.65106
[27] Matrix Market, http://math.nist.gov/matrixMarket/
[28] Morgan, R., GMRES with deflated restarting, SIAM J. Sci. Comput., 24, 20-37, (2002) · Zbl 1018.65042
[29] Morgan, R., Restarted block, GMRES with deflation of eigenvalues, Appl. Numer. Math., 54, 222-236, (2005) · Zbl 1074.65043
[30] Morgan, R.; Zeng, M., A harmonic restarted Arnoldi algorithm for calculating eigenvalues and determining multiplicity, Linear Alg. Appl., 415, 96-113, (2006) · Zbl 1088.65033
[31] Mohseni Mohgadam, M.; Panjeh Ali Beik, F., A new weighted global full orthogonalization method for solving nonsymmetric linear systems with multiple right-hand sides, Int. Electron. J. Pure Appl. Math., 2, 47-67, (2010) · Zbl 1413.65126
[32] Panjeh Ali Beik, F.; Mohseni Mohgadam, M., Global generalized minimum residual method for solving Sylvester equation, Aust. J. Basic Appl. Sci., 5, 1128-1134, (2011)
[33] Panjeh Ali Beik, F.; Khojasteh Salkuyeh, D., Weighted versions of gl-FOM and gl-GMRES for solving general coupled linear matrix equations, Comput. Math. Math. Phys., 55, 1606-1618, (2015) · Zbl 1341.65018
[34] Penzel, T.: LYAPACK: A MATLAB toolbox for large Lyapunov and Riccati equations, model reduction problems, and linear-quadratic optimal control problems, software available at https://www.tu-chemnitz.de/sfb393/lyapack/
[35] Robbé, M.; Sadkane, M., A convergence analysis of GMRES and FOM methods for Sylvester equations, Numer. Alg., 30, 71-89, (2002) · Zbl 1005.65030
[36] Saberi Najafi, H.; Zareamoghaddam, H., A new computational, GMRES Method, Appl. Math. Comput., 199, 527-534, (2008) · Zbl 1143.65031
[37] Simoncini, V., The extended Krylov subspace for parameter dependent systems, Appl. Numer. Math., 60, 550-560, (2010) · Zbl 1190.65052
[38] Simoncini, V., A new iterative method for solving large-scale Lyapunov matrix equations, SIAM J. Sci. Comput., 29, 1268-1288, (2007) · Zbl 1146.65038
[39] Simoncini, V., Computational methods for linear matrix equations, SIAM Rev., 58, 377-441, (2016) · Zbl 1386.65124
[40] Sorensen, D., Implicit application of polynomial filters in a k-step Arnoldi method, SIAM J. Matrix Anal. Appl., 13, 357-385, (1992) · Zbl 0763.65025
[41] Wan, F., An in-core finite difference method for separable boundary value problems on a rectangle, Stud. Appl. Math., 52, 103-113, (1973) · Zbl 0264.65062
[42] Watkins, D.: The Matrix Eigenvalue Problem. GR and Krylov Subspace Methods. SIAM, Philadelphia (2007) · Zbl 1142.65038
[43] Wu, G.; Wei, Y., A Power-Arnoldi algorithm for computing PageRank, Numer. Linear Alg. Appl., 14, 521-546, (2007) · Zbl 1199.65125
[44] Wu, K.; Simon, H., Thick-restart Lanczos method for sysmmetric eigenvalue problems, SIAM J. Matrix Anal. Appl., 22, 602-616, (2000) · Zbl 0969.65030
[45] Zhong, H.; Wu, G., Thick restarting the weighted harmonic Arnoldi algorithm for large interior eigenproblems, Int. J. Comput. Math., 88, 994-1012, (2011) · Zbl 1298.65066
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.