Interpolation of inverse operators for preconditioning parameter-dependent equations. (English) Zbl 1382.65035
Summary: We propose a method for the construction of preconditioners of parameter-dependent matrices for the solution of large systems of parameter-dependent equations. The proposed method is an interpolation of the matrix inverse based on a projection of the identity matrix with respect to the Frobenius norm. Approximations of the Frobenius norm using random matrices are introduced in order to handle large matrices. The resulting statistical estimators of the Frobenius norm yield quasi-optimal projections that are controlled with high probability. Strategies for the adaptive selection of interpolation points are then proposed for different objectives in the context of projection-based model order reduction methods: the improvement of residual-based error estimators, the improvement of the projection on a given reduced approximation space, and the reuse of computations for sampling-based model order reduction methods.
MSC:
| 65D05 | Numerical interpolation |
| 65F08 | Preconditioners for iterative methods |
| 15B52 | Random matrices (algebraic aspects) |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
Keywords:
preconditioning; parameter-dependent equations; empirical interpolation; random matrices; projection-based model order reduction; reduced basisReferences:
| [1] | N. Ailon and B. Chazelle, {\it The fast Johnson-Lindenstrauss transform and approximate nearest neighbors}, in Proceedings of STOC, ACM, New York, 2006, pp. 557-563. · Zbl 1301.68232 |
| [2] | H. Avron and S. Toledo, {\it Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix}, J. ACM, 58 (2011), 8. · Zbl 1327.68331 |
| [3] | C. Bekas, E. Kokiopoulou, and Y. Saad, {\it An estimator for the diagonal of a matrix}, Appl. Numer. Math., 57 (2007), pp. 1214-1229. · Zbl 1123.65026 |
| [4] | M. Benzi, {\it Preconditioning techniques for large linear systems: A survey}, J. Comput. Phys., 182 (2002), pp. 418-477. · Zbl 1015.65018 |
| [5] | P. Binev, A. Cohen, W. Dahmen, R. DeVore, G. Petrova, and P. Wojtaszczyk, {\it Convergence rates for greedy algorithms in reduced basis methods}, SIAM J. Math. Anal., 43 (2011), pp. 1457-1472, http://dx.doi.org/10.1137/100795772 doi:10.1137/100795772. · Zbl 1229.65193 |
| [6] | J. Bourgain, J. Lindenstrauss, and V. Milman, {\it Approximation of zonoids by zonotopes}, Acta Math., 162 (1989), pp. 73-141. · Zbl 0682.46008 |
| [7] | C. Boutsidis and A. Gittens, {\it Improved matrix algorithms via the subsampled randomized Hadamard transform}, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 1301-1340, http://dx.doi.org/10.1137/120874540 doi:10.1137/120874540. · Zbl 1286.65054 |
| [8] | A. N. Brooks and T. J. R. Hughes, {\it Streamline upwind/Petrov-Galerkin formulations for convection dominated flows with particular emphasis on the incompressible Navier-Stokes equations}, Comput. Methods Appl. Mech. Engrg., 32 (1982), pp. 199-259. · Zbl 0497.76041 |
| [9] | F. Casenave, A. Ern, and T. Lelièvre, {\it A nonintrusive reduced basis method applied to aero-acoustic simulations}, Adv. Comput. Math. 41 (2015), pp. 961-986. · Zbl 1338.76049 |
| [10] | P. Chen, A. Quarteroni, and G. Rozza, {\it Comparison between reduced basis and stochastic collocation methods for elliptic problems}, J. Sci. Comput., 59 (2014), pp. 187-216. · Zbl 1301.65007 |
| [11] | Y. Chen, S. Gottlieb, and Y. Maday, {\it Parametric analytical preconditioning and its applications to the reduced collocation methods}, C. R. Math. Acad. Sci. Paris, 352 (2014), pp. 661-666. · Zbl 1297.65166 |
| [12] | A. Cohen, W. Dahmen, and G. Welper, {\it Adaptivity and variational stabilization for convection-diffusion equations}, ESAIM Math. Model. Numer. Anal., 46 (2012), pp. 1247-1273. · Zbl 1270.65065 |
| [13] | W. Dahmen, C. Huang, C. Schwab, and G. Welper, {\it Adaptive Petrov-Galerkin methods for first order transport equations}, SIAM J. Numer. Anal., 50 (2012), pp. 2420-2445, http://dx.doi.org/10.1137/110823158 doi:10.1137/110823158. · Zbl 1260.65091 |
| [14] | W. Dahmen, C. Plesken, and G. Welper, {\it Double greedy algorithms: Reduced basis methods for transport dominated problems}, ESAIM Math. Model. Numer. Anal., 48 (2013), pp. 623-663. · Zbl 1291.65339 |
| [15] | A. Dasgupta, P. Drineas, B. Harb, R. Kumar, and M. W. Mahoney, {\it Sampling algorithms and coresets for \(ℓ_p\) regression}, SIAM J. Comput., 38 (2009), pp. 2060-2078, http://dx.doi.org/10.1137/070696507 doi:10.1137/070696507. · Zbl 1191.68851 |
| [16] | M. Deb, I. Babuska, and J. T. Oden, {\it Solution of stochastic partial differential equations using Galerkin finite element techniques}, Comput. Methods Appl. Mech. Engrg., 190 (2001), pp. 6359-6372. · Zbl 1075.65006 |
| [17] | C. Desceliers, R. Ghanem, and C. Soize, {\it Polynomial chaos representation of a stochastic preconditioner}, Internat. J. Numer. Methods Engrg., 64 (2005), pp. 618-634. · Zbl 1122.74541 |
| [18] | R. DeVore, G. Petrova, and P. Wojtaszczyk, {\it Greedy algorithms for reduced bases in Banach spaces}, Constr. Approx., 37 (2013), pp. 455-466. · Zbl 1276.41021 |
| [19] | H. C. Elman and V. Forstall, {\it Preconditioning techniques for reduced basis methods for parameterized elliptic partial differential equations}, SIAM J. Sci. Comput., 37 (2015), pp. S177-S194, http://dx.doi.org/10.1137/140970859 doi:10.1137/140970859. · Zbl 1457.65174 |
| [20] | O. G. Ernst, C. E. Powell, D. J. Silvester, and E. Ullmann, {\it Efficient solvers for a linear stochastic Galerkin mixed formulation of diffusion problems with random data}, SIAM J. Sci. Comput., 31 (2009), pp. 1424-1447, http://dx.doi.org/10.1137/070705817 doi:10.1137/070705817. · Zbl 1187.35298 |
| [21] | R. Ghanem and R. M. Kruger, {\it Numerical solution of spectral stochastic finite element systems}, Comput. Methods Appl. Mech. Engrg., 129 (1996), pp. 289-303. · Zbl 0861.73071 |
| [22] | L. Giraldi, A. Litvinenko, D. Liu, H. G. Matthies, and A. Nouy, {\it To be or not to be intrusive? The solution of parametric and stochastic equations–the “plain vanilla” Galerkin case}, SIAM J. Sci. Comput., 36 (2014), pp. A2720-A2744, http://dx.doi.org/10.1137/130942802 doi:10.1137/130942802. · Zbl 1310.65132 |
| [23] | L. Giraldi, A. Nouy, and G. Legrain., {\it Low-rank approximate inverse for preconditioning tensor-structured linear systems}, SIAM J. Sci. Comput., 36 (2014), pp. A1850-A1870, http://dx.doi.org/10.1137/130918137 doi:10.1137/130918137. · Zbl 1307.65033 |
| [24] | L. González, {\it Orthogonal projections of the identity: Spectral analysis and applications to approximate inverse preconditioning}, SIAM Rev., 48 (2006), pp. 66-75, http://dx.doi.org/10.1137/S0036144504431905 doi:10.1137/S0036144504431905. · Zbl 1095.65042 |
| [25] | M. J. Grote and T. Huckle, {\it Parallel preconditioning with sparse approximate inverses}, SIAM J. Sci. Comput., 18 (1997), pp. 838-853, http://dx.doi.org/10.1137/S1064827594276552 doi:10.1137/S1064827594276552. · Zbl 0872.65031 |
| [26] | M. F. Hutchinson, {\it A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines}, Comm. Statist. Simulation Comput., 19 (1990), pp. 433-450. · Zbl 0718.62058 |
| [27] | D. B. P. Huynh, G. Rozza, S. Sen, and A. T. Patera, {\it A successive constraint linear optimization method for lower bounds of parametric coercivity and inf-sup stability constants}, C. R. Math. Acad. Sci. Paris, 345 (2007), pp. 473-478. · Zbl 1127.65086 |
| [28] | B. N. Khoromskij and C. Schwab, {\it Tensor-structured Galerkin approximation of parametric and stochastic elliptic PDEs}, SIAM J. Sci. Comput., 33 (2011), pp. 364-385, http://dx.doi.org/10.1137/100785715 doi:10.1137/100785715. · Zbl 1243.65009 |
| [29] | Y. Maday, N. C. Nguyen, A. T. Patera, and G. S. H. Pau, {\it A general multipurpose interpolation procedure: The magic points}, Commun. Pure Appl. Anal., 8 (2009), pp. 383-404. · Zbl 1184.65020 |
| [30] | P. Maréchal and J. J. Ye, {\it Optimizing condition numbers}, SIAM J. Optim., 20 (2009), pp. 935-947, http://dx.doi.org/10.1137/080740544 doi:10.1137/080740544. · Zbl 1198.90328 |
| [31] | H. G. Matthies and A. Keese, {\it Galerkin methods for linear and nonlinear elliptic stochastic partial differential equations}, Comput. Methods Appl. Mech. Engrg., 194 (2005), pp. 1295-1331. · Zbl 1088.65002 |
| [32] | H. G. Matthies and E. Zander, {\it Solving stochastic systems with low-rank tensor compression}, Linear Algebra Appl., 436 (2012), pp. 3819-3838. · Zbl 1241.65016 |
| [33] | A. Nouy, {\it Recent developments in spectral stochastic methods for the numerical solution of stochastic partial differential equations}, Arch. Comput. Methods Eng., 16 (2009), pp. 251-285. · Zbl 1360.65036 |
| [34] | P. Pacciarini and G. Rozza, {\it Stabilized reduced basis method for parametrized advection-diffusion PDEs}, Comput. Methods Appl. Mech. Engrg., 274 (2014), pp. 1-18. · Zbl 1296.65165 |
| [35] | G. Rozza and K. Veroy, {\it On the stability of the reduced basis method for Stokes equations in parametrized domains}, Comput. Methods Appl. Mech. Engrg., 196 (2007), pp. 1244-1260. · Zbl 1173.76352 |
| [36] | G. Rozza, D. B. P. Huynh, and A. T. Patera, {\it Reduced basis approximation and a posteriori error estimation for affinely parametrized elliptic coercive partial differential equations}, Arch. Comput. Methods Eng., 15 (2008), pp. 229-275. · Zbl 1304.65251 |
| [37] | J. Tropp, {\it Improved analysis of the subsampled randomized Hadamard transform}, Adv. Adapt. Data Anal., 3 (2011), pp. 115-126. · Zbl 1232.15029 |
| [38] | K. Veroy, C. Prud’homme, D. V. Rovas, and A. T. Patera, {\it A posteriori error bounds for reduced-basis approximation of parametrized noncoercive and nonlinear elliptic partial differential equations}, in Proceedings of the 16th AIAA Computational Fluid Dynamics Conference, AIAA, Reston, VA, 2003, pp. 2003-3847. |
| [39] | L. Welch, {\it Lower bounds on the maximum cross correlation of signals}, IEEE Trans. Inform. Theory, 20 (1974), pp. 397-399. · Zbl 0298.94006 |
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.
