Two new variants of the simpler block GMRES method with vector deflation and eigenvalue deflation for multiple linear systems. (English) Zbl 1458.65034
Summary: In this paper, two effective methods based on the simpler block GMRES method are established in order to solve the linear systems of equations with multiple right-hand sides. The first method is derived from the simpler block GMRES method with vector deflation restarting (SBGMRES-DR). The second method is constructed from a combination of SBGMRES-DR with the eigenvalue deflation technique, which is called the deflated simpler block GMRES method with vector deflation restarting (D-SBGMRES-DR). To be more specific, SBGMRES-DR is capable of removing linearly or almost linearly dependent vectors created by the block Arnoldi process. On the other hand, D-SBGMRES-DR not only deletes linearly or almost linearly dependent vectors but also retains harmonic Ritz vectors associated with the smallest harmonic Ritz values in magnitude, and adds them to the new search subspace at the time of restart. Finally, a wide range of practical experiments are carried out to assess the efficiency of the proposed methods. The numerical results indicate that the D-SBGMRES-DR method outperforms the compared methods with respect to the number of matrix-vector products and the computational time.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
References:
| [1] | Abdaoui, l.; Elbouyahyaoui, L.; Heyouni, M., The simpler block CMRH method for linear systems, Numer. Algorithms, 84, 1265-1293 (2020) · Zbl 1470.65048 |
| [2] | Al Daas, H.; Grigori, L.; Hénon, P.; Ricoux, P., Enlarged GMRES for solving linear systems with one or multiple right-hand sides, IMA J. Numer. Anal., 39, 1924-1956 (2019) · Zbl 1496.65045 |
| [3] | Bloch, JC; Breu, T.; Frommer, A.; Heybrock, S.; Schaefer, K.; Wettig, T., Short-recurrence Krylov subspace methods for the overlap Dirac operator at nonzero chemical potential, Comput. Phys. Commun., 181, 8, 1378-1387 (2010) · Zbl 1219.81096 |
| [4] | Bloch, JC; Heybrock, S., A nested Krylov subspace method to compute the sign function of large complex matrices, Comput. Phys. Commun., 182, 4, 878-889 (2011) · Zbl 1221.65104 |
| [5] | Boojhawon, R.; Bhuruth, M., Restarted simpler GMRES augmented with harmonic ritz vectors, Future Gener. Comput. Syst., 20, 3, 389-397 (2004) · Zbl 1062.65039 |
| [6] | Bouyouli, R.; Jbilou, K.; Sadaka, R.; Sadok, H., Convergence properties of some block Krylov subspace methods for multiple linear systems, J. Comput. Appl. Math., 196, 498-511 (2006) · Zbl 1100.65024 |
| [7] | Calandra, H.; Gratton, S.; Lago, R.; Vasseur, X.; Carvalho, LM, A modified block flexible GMRES method with deflation at each iteration for the solution of non-Hermitian linear systems with multiple right-hand sides, SIAM J. Sci. Comput., 35, 5, S345-S367 (2013) · Zbl 1281.65056 |
| [8] | Calandra, H.; Gratton, S.; Langou, J.; Pinel, X.; Vasseur, X., Flexible variants of block restarted GMRES methods with application to geophysics, SIAM J. Sci. Comput., 34, 2, A714-A736 (2012) · Zbl 1248.65036 |
| [9] | Carpentieri, B.; Jing, Y-F; Huang, T-Z, The BiCOR and CORS iterative algorithms for solving nonsymmetric linear systems, SIAM J. Sci. Comput., 33, 5, 3020-3036 (2011) · Zbl 1251.65045 |
| [10] | Chen, G.; Jia, ZX, Theoretical and numerical comparisons of GMRES and WZ-GMRES, Comput. Math. Appl., 47, 8-9, 1335-1350 (2004) · Zbl 1071.65037 |
| [11] | Clough, RW; Penzien, J., Structural Dynamics (1975), New York: McGrowHill Inc, New York · Zbl 0357.73068 |
| [12] | Davis, TA; Hu, Y., The University of Florida sparse matrix collection, ACM Trans. Math. Softw. (TOMS), 38, 1, 1 (2011) · Zbl 1365.65123 |
| [13] | Elbouyahyaoui, L.; Heyouni, M.; Tajaddini, A.; Saberi-Movahed, F., On restarted and deflated block FOM and GMRES methods for sequences of shifted linear systems, Numer. Algorithms, 25, 1-43 (2020) |
| [14] | Erlangga, YA; Vuik, C.; Oosterlee, CW, On a class of preconditioners for solving the Helmholtz equation, Appl. Numer. Math., 50, 409-425 (2004) · Zbl 1051.65101 |
| [15] | Freund, RW, Krylov-subspace methods for reduced-order modeling in circuit simulation, J. Comput. Appl. Math., 123, 1-2, 395-421 (2000) · Zbl 0964.65082 |
| [16] | Frommer, A.; Lund, K.; Szyld, DB, Block Krylov subspace methods for functions of matrices, Electron. Trans. Numer. Anal., 47, 100-126 (2017) · Zbl 1372.65138 |
| [17] | Frommer, A.; Lund, K.; Szyld, DB, Block Krylov subspace methods for functions of matrices II: modified block FOM, SIAM J. Matrix Anal. Appl., 4, 2, 804-837 (2020) · Zbl 1441.65051 |
| [18] | Giraud, L.; Gratton, S.; Pinel, X.; Vasseur, X., Flexible GMRES with deflated restarting, SIAM J. Sci. Comput., 32, 4, 1858-1878 (2010) · Zbl 1215.65057 |
| [19] | Golub, GH; Van Loan, CF, Matrix Computations (2013), Baltimore: The Johns Hopkins University Press, Baltimore · Zbl 1268.65037 |
| [20] | Gu, G-D; Cao, Z-H, A block GMRES method augmented with eigenvectors, Appl. Math. Comput., 121, 2-3, 271-289 (2001) · Zbl 1024.65031 |
| [21] | Gutknecht, MH; Siddiqi, A.; Duff, I.; Christensen, O., Block Krylov space methods for linear systems with multiple right-hand sides: an introduction, Modern Mathematical Models, Methods and Algorithms for Real World Systems, 420-447 (2006), New Delhi: Anamaya Publishers, New Delhi |
| [22] | Heyouni, M.; Essai, A., Matrix Krylov subspace methods for linear systems with multiple right-hand sides, Numer. Algorithms, 40, 137-156 (2005) · Zbl 1087.65028 |
| [23] | Jbilou, K.; Messaoudi, A.; Sadok, H., Global FOM and GMRES algorithms for matrix equations, Appl. Numer. Math., 31, 1, 49-63 (1999) · Zbl 0935.65024 |
| [24] | Ji, H.; Li, Y-H, A breakdown-free block conjugate gradient method, BIT Numer. Math., 57, 379-403 (2017) · Zbl 1392.65057 |
| [25] | Jiránek, P.; Rozložník, M., Adaptive version of simpler GMRES, Numer. Algorithms, 53, 1, 93-112 (2010) · Zbl 1188.65033 |
| [26] | J. Langou. Iterative Methods for Solving Linear Systems with Multiple Right-hand Sides. Ph.D. thesis, Ph. D. dissertation, INSA Toulouse (2003) |
| [27] | Liu, H.; Zhong, B., Simpler block GMRES for nonsymmetric systems with multiple right-hand sides, Electron. Trans. Numer. Anal., 30, 1-9 (2008) · Zbl 1188.65034 |
| [28] | Meng, J.; Zhu, P-Y; Li, H-B, A block GCROT \((m, k)\) method for linear systems with multiple right-hand sides, J. Comput. Appl. Math., 255, 544-554 (2014) · Zbl 1291.65105 |
| [29] | Meng, J.; Zhu, P-Y; Li, H-B; Gu, X-M, A deflated block flexible GMRES-DR method for linear systems with multiple right-hand sides, Electron. Trans. Numer. Anal., 41, 478-496 (2014) · Zbl 1312.65048 |
| [30] | Morgan, RB, Restarted block-GMRES with deflation of eigenvalues, Appl. Numer. Math., 54, 2, 222-236 (2005) · Zbl 1074.65043 |
| [31] | Rashedi, S.; Ebadi, G.; Birk, S.; Frommer, A., On short recurrence Krylov type methods for linear systems with many right-hand sides, J. Comput. Appl. Math., 300, 18-29 (2016) · Zbl 1382.65092 |
| [32] | Robbé, M.; Sadkane, M., Exact and inexact breakdowns in the block GMRES method, Linear Algebra Appl., 419, 1, 265-285 (2006) · Zbl 1112.65028 |
| [33] | Saad, Y., Iterative Methods for Sparse Linear Systems (2003), Philadelphia: SIAM, Philadelphia · Zbl 1031.65046 |
| [34] | Sakurai, T.; Tadano, H.; Kuramashi, Y., Application of block Krylov subspace algorithms to the Wilson-Dirac equation with multiple right-hand sides in lattice QCD, Comput. Phys. Commun., 181, 1, 113-117 (2010) · Zbl 1205.81131 |
| [35] | Simoncini, V.; Gallopoulos, E., An iterative method for nonsymmetric systems with multiple right-hand sides, SIAM J. Sci. Comput., 16, 4, 917-933 (1995) · Zbl 0831.65037 |
| [36] | Simoncini, V.; Gallopoulos, E., A hybrid block GMRES method for nonsymmetric systems with multiple right-hand sides, J. Comput. Appl. Math., 66, 1-2, 457-469 (1996) · Zbl 0859.65021 |
| [37] | Soudais, P., Iterative solution of a 3D scattering problem from arbitrary shaped multidielectric and multiconducting bodies, IEEE Trans. Antennas Propag., 42, 7, 954-959 (1994) |
| [38] | Sun, D-L; Carpentieri, B.; Huang, T-Z; Jing, Y-F, A spectrally preconditioned and initially deflated variant of the restarted block GMRES method for solving multiple right-hand sides linear systems, Int. J. Mech. Sci., 144, 775-787 (2018) |
| [39] | Sun, D-L; Huang, T-Z; Carpentieri, B.; Jing, Y-F, A new shifted block GMRES method with inexact breakdowns for solving multi-shifted and multiple right-hand sides linear systems, J. Sci. Comput., 78, 2, 746-769 (2019) · Zbl 1483.65054 |
| [40] | Sun, D-L; Huang, T-Z; Carpentieri, B.; Jing, Y-F, Flexible and deflated variants of the block shifted GMRES method, J. Comput. Appl. Math., 345, 168-183 (2019) · Zbl 1415.65080 |
| [41] | Walker, HF; Zhou, L., A simpler GMRES, Numer. Linear Algebra Appl., 1, 6, 571-581 (1994) · Zbl 0838.65030 |
| [42] | Wu, Q.; Bao, L.; Lin, Y., Residual-based simpler block GMRES for nonsymmetric linear systems with multiple right-hand sides, Adv. Math. Phys., 2018, 1369707 (2018) · Zbl 1431.65037 |
| [43] | Xiang, Y-F; Jing, Y-F; Huang, T-Z, A new projected variant of the deflated block conjugate gradient method, J. Sci. Comput., 80, 1116-1138 (2019) · Zbl 1416.65089 |
| [44] | Zhang, F., Matrix Theory: Basic Results and Techniques (2011), New York: Springer, New York · Zbl 1229.15002 |
| [45] | Zhong, H-X; Gu, X-M, A flexible and adaptive simpler GMRES with deflated restarting for shifted linear systems, Comput. Math. Appl., 78, 3, 997-1007 (2019) · Zbl 1442.65052 |
| [46] | Zhong, H-X; Wu, G.; Chen, G-L, A flexible and adaptive simpler block GMRES with deflated restarting for linear systems with multiple right-hand sides, J. Comput. Appl. Math., 282, 139-156 (2015) · Zbl 1309.65038 |
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.
