An accelerated subspaces recycling strategy for the deflation of parametric linear systems based on model order reduction. (English) Zbl 1536.65035
Summary: Krylov subspace recycling has been extensively used to facilitate the solution of sequences of linear systems by constructing a deflation subspace and accelerating the convergence of a corresponding iterative solver. However, most existing techniques update the recycled subspace sequentially for each system, thus inducing a potentially high computational cost. In that context, this work proposes a method to accelerate the above procedure for the case of multiresolution analyses of affine parametric systems, by decoupling the solution of the system from the construction of the recycled subspace. The proposed method follows the projection based Model Order Reduction (MOR) logic that splits operations into an offline and an online phase and therefore proves particularly beneficial in case of affine parametrizations that involve multiple affine coefficients. In the offline phase of the method an especially tailored version of the Automatic Krylov subspaces Recycling (AKR) algorithm [D. Panagiotopoulos et al., Comput. Methods Appl. Mech. Eng. 373, Article ID 113510, 22 p. (2021; Zbl 1506.65058)], proposed within this work and denoted as AKR-D, is employed. In brief, AKR-D constructs a high quality recycling basis \(\mathbf{W}\) for a predefined parameter interval \(\varPsi\) by targeting a desirable convergence rate at an automatically generated set of parameter values \(\varOmega\subset\varPsi\). The upfront construction of \(\mathbf{W}\) enables an a-priori Galerkin projection of the affinely described full parametric system to yield a reduced order model (ROM). This ROM can be leveraged in the online phase of the proposed recycling method to accelerate the construction of the corresponding projector \(\mathbf{P}\) onto \(\mathscr{W} = \mathrm{span}\{\mathbf{W}\}\), whose implicit assembly is required in most recycling based deflation schemes. The effectiveness of the proposed strategy is investigated in terms of algorithmic complexity and is demonstrated on a densely parametrized system arising within the boundary integral solver of the Helmholtz equation and a random sparse parametrization example.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
Keywords:
Krylov subspaces recycling; deflation based iterative solution; parametric systems; AKR algorithmCitations:
Zbl 1506.65058References:
| [1] | Hestenes, M. R.; Stiefel, E., Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Stand., 49, 6, 409-436 (1952) · Zbl 0048.09901 |
| [2] | Saad, Y.; Schultz, M. H., GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 3, 856-869 (1986) · Zbl 0599.65018 |
| [3] | Eisenstat, S. C.; Elman, H. C.; Schultz, M. H., Variational iterative methods for nonsymmetric systems of linear equations, SIAM J. Numer. Anal., 20, 2, 345-357 (1983) · Zbl 0524.65019 |
| [4] | O’Leary, D. P., The block conjugate gradient algorithm and related methods, Linear Algebra Appl., 29, 293-322 (1980) · Zbl 0426.65011 |
| [5] | Simoncini, V.; Szyld, D. B., Recent computational developments in Krylov subspace methods for linear systems, Numer. Linear Algebra Appl., 14, 1, 1-59 (2007) · Zbl 1199.65112 |
| [6] | Golub, G. H.; Van Loan, C. F., Matrix Computations, Vol. 3 (2012), JHU Press |
| [7] | Meurant, G.; Duintjer Tebbens, J., The role eigenvalues play in forming GMRES residual norms with non-normal matrices, Numer. Algorithms, 68, 1, 143-165 (2015) · Zbl 1312.65050 |
| [8] | Chapman, A.; Saad, Y., Deflated and augmented Krylov subspace techniques, Numer. Linear Algebra Appl., 4, 1, 43-66 (1997) · Zbl 0889.65028 |
| [9] | Morgan, R. B., GMRES with deflated restarting, SIAM J. Sci. Comput., 24, 1, 20-37 (2002) · Zbl 1018.65042 |
| [10] | Erhel, J.; Guyomarc’h, F., An augmented conjugate gradient method for solving consecutive symmetric positive definite linear systems, SIAM J. Matrix Anal. Appl., 21, 4, 1279-1299 (2000) · Zbl 0966.65031 |
| [11] | Saad, Y.; Yeung, M.; Erhel, J.; Guyomarc’h, F., A deflated version of the conjugate gradient algorithm, SIAM J. Sci. Comput., 21, 5, 1909-1926 (2000) · Zbl 0955.65021 |
| [12] | Benner, P.; Feng, L., Recycling krylov subspaces for solving linear systems with successively changing right-hand sides arising in model reduction, (Benner, P.; Hinze, M.; ter Maten, E. J.W., Model Reduction for Circuit Simulation (2011), Springer Netherlands: Springer Netherlands Dordrecht), 125-140 |
| [13] | Risler, F.; Rey, C., Iterative accelerating algorithms with krylov subspaces for the solution to large-scale nonlinear problems, Numer. Algorithms, 23, 1, 1 (2000) · Zbl 0951.65047 |
| [14] | Gosselet, P.; Rey, C.; Pebrel, J., Total and selective reuse of Krylov subspaces for the resolution of sequences of nonlinear structural problems, Internat. J. Numer. Methods Engrg., 94, 1, 60-83 (2013) · Zbl 1352.65105 |
| [15] | Chan, T. F.; Ng, M. K., Galerkin projection methods for solving multiple linear systems, SIAM J. Sci. Comput., 21, 3, 836-850 (1999) · Zbl 0954.65027 |
| [16] | Parks, M. L.; De Sturler, E.; Mackey, G.; Johnson, D. D.; Maiti, S., Recycling Krylov subspaces for sequences of linear systems, SIAM J. Sci. Comput., 28, 5, 1651-1674 (2006) · Zbl 1123.65022 |
| [17] | De Sturler, E., Truncation strategies for optimal Krylov subspace methods, SIAM J. Numer. Anal., 36, 3, 864-889 (1999) · Zbl 0960.65031 |
| [18] | Keuchel, S.; Biermann, J.; von Estorff, O., A combination of the fast multipole boundary element method and Krylov subspace recycling solvers, Eng. Anal. Bound. Elem., 65, 136-146 (2016) · Zbl 1403.65202 |
| [19] | Simoncini, V., On the convergence of restarted Krylov subspace methods, SIAM J. Matrix Anal. Appl., 22, 2, 430-452 (2000) · Zbl 0969.65023 |
| [20] | Daas, H. A.; Grigori, L.; Hénon, P.; Ricoux, P., Recycling Krylov subspaces and truncating deflation subspaces for solving sequence of linear systems, ACM Trans. Math. Softw., 47, 2, 1-30 (2021) · Zbl 07467973 |
| [21] | Panagiotopoulos, D.; Desmet, W.; Deckers, E., An automatic Krylov subspaces recycling technique for the construction of a global solution basis of non-affine parametric linear systems, Comput. Methods Appl. Mech. Engrg., 373, Article 113510 pp. (2021) · Zbl 1506.65058 |
| [22] | Panagiotopoulos, D.; Desmet, W.; Deckers, E., Parametric model order reduction for acoustic BEM systems through a multi-parameter krylov subspaces recycling strategy, Internat. J. Numer. Methods Engrg., 123.22, 5546-5569 (2022) · Zbl 07769288 |
| [23] | Soodhalter, K. M.; de Sturler, E.; Kilmer, M. E., A survey of subspace recycling iterative methods, GAMM-Mitt., 43, 4, Article e202000016 pp. (2020) · Zbl 1541.65019 |
| [24] | Brebbia, C. A., The Boundary Element Method for Engineers (1980), Pentech Press |
| [25] | Arnoldi, W. E., The principle of minimized iterations in the solution of the matrix eigenvalue problem, Quart. Appl. Math., 9, 1, 17-29 (1951) · Zbl 0042.12801 |
| [26] | Lanczos, C., An Iteration Method for the Solution of the Eigenvalue Problem of Linear Differential and Integral Operators (1950), United States Governm. Press Office Los Angeles, CA · Zbl 0067.33703 |
| [27] | Reichel, L.; Ye, Q., Breakdown-free GMRES for singular systems, SIAM J. Matrix Anal. Appl., 26, 4, 1001-1021 (2005) · Zbl 1086.65030 |
| [28] | Gaul, A.; Gutknecht, M. H.; Liesen, J.; Nabben, R., A framework for deflated and augmented Krylov subspace methods, SIAM J. Matrix Anal. Appl., 34, 2, 495-518 (2013) · Zbl 1273.65049 |
| [29] | Saad, Y., Krylov subspace methods for solving large unsymmetric linear systems, Math. Comp., 37, 155, 105-126 (1981) · Zbl 0474.65019 |
| [30] | Calvetti, D.; Lewis, B.; Reichel, L., GMRES-type methods for inconsistent systems, Linear Algebra Appl., 316, 1-3, 157-169 (2000) · Zbl 0963.65042 |
| [31] | Rey, C.; Risler, F., A Rayleigh-Ritz preconditioner for the iterative solution to large scale nonlinear problems, Numer. Algorithms, 17, 3, 279-311 (1998) · Zbl 0908.65034 |
| [32] | Panagiotopoulos, D.; Deckers, E.; Desmet, W., Krylov subspaces recycling based model order reduction for acoustic BEM systems and an error estimator, Comput. Methods Appl. Mech. Engrg., 359, Article 112755 pp. (2020) · Zbl 1441.76083 |
| [33] | Xie, X.; Liu, Y., An adaptive model order reduction method for boundary element-based multi-frequency acoustic wave problems, Comput. Methods Appl. Mech. Engrg., 373, Article 113532 pp. (2021) · Zbl 1506.74470 |
| [34] | Van der Vorst, H. A.; Vuik, C., The superlinear convergence behaviour of GMRES, J. Comput. Appl. Math., 48, 3, 327-341 (1993) · Zbl 0797.65026 |
| [35] | Simoncini, V.; Szyld, D. B., On the occurrence of superlinear convergence of exact and inexact krylov subspace methods, SIAM Rev., 47, 2, 247-272 (2005) · Zbl 1079.65034 |
| [36] | Greenbaum, A.; Pták, V.; Strakoš, Z.e.k., Any nonincreasing convergence curve is possible for GMRES, Siam J. Matrix Anal. Appl., 17, 3, 465-469 (1996) · Zbl 0857.65029 |
| [37] | Antoine, X.; Darbas, M., An introduction to operator preconditioning for the fast iterative integral equation solution of time-harmonic scattering problems, Multiscale Sci. Eng., 1-35 (2021) |
| [38] | Liang, T.; Wang, J.; Xiao, J.; Wen, L., Coupled BE-FE based vibroacoustic modal analysis and frequency sweep using a generalized resolvent sampling method, Comput. Methods Appl. Mech. Engrg., 345, 518-538 (2019) · Zbl 1440.65217 |
| [39] | Panagiotopoulos, D.; Deckers, E.; Desmet, W., A two-step reduction method for acoustic BEM systems, (Proceedings of Forum Acusticum 2020 (2020), European Acoustics association) |
| [40] | Mason, J. C.; Handscomb, D. C., Chebyshev Polynomials (2002), Chapman and Hall/CRC · Zbl 1015.33001 |
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.
