[Approximations creuses pour la méthode de Galerkin stochastique]
Dans cette Note, nous formulons une méthode de Krylov creuse pour la résolution de grands systèmes linéaires issus de la discrétisation d'équations aux dérivées partielles elliptiques paramétrées aléatoirement. Nous analysons l'algorithme du gradient conjugué (GC) creux dans le cadre des méthodes de sous-espaces de Krylov inexactes, montrons sa convergence et étudions sa complexité algorithmique. Les études numériques réalisées sur des modèles de diffusion stochastiques montrent que la méthode du GC creux converge plus rapidement que le GC classique lorsque la solution recherchée admet une représentation creuse dans une base de chaos polynomial. Dans ce cas, l'algorithme du GC creux retrouve presque intégralement la structure creuse de la solution exacte, permettant d'accélérer la convergence. Lorsque la solution exacte est dense, l'algorithme du GC creux fournit des résultats de convergence similaires à ceux obtenus avec le GC classique.
In this Note, we formulate a sparse Krylov-based algorithm for solving large-scale linear systems of algebraic equations arising from the discretization of randomly parametrized (or stochastic) elliptic partial differential equations (SPDEs). We analyze the proposed sparse conjugate gradient (CG) algorithm within the framework of inexact Krylov subspace methods, prove its convergence and study its abstract computational cost. Numerical studies conducted on stochastic diffusion models show that the proposed sparse CG algorithm outperforms the classical CG method when the sought solutions admit a sparse representation in a polynomial chaos basis. In such cases, the sparse CG algorithm recovers almost exactly the sparsity pattern of the exact solutions, which enables accelerated convergence. In the case when the SPDE solution does not admit a sparse representation, the convergence of the proposed algorithm is very similar to the classical CG method.
Accepté le :
Publié le :
@article{CRMATH_2019__357_6_561_0,
author = {Audouze, Christophe and Nair, Prasanth B.},
title = {Sparse approximate solutions to stochastic {Galerkin} equations},
journal = {Comptes Rendus. Math\'ematique},
pages = {561--570},
publisher = {Elsevier},
volume = {357},
number = {6},
year = {2019},
doi = {10.1016/j.crma.2019.05.009},
language = {en},
url = {http://www.numdam.org/articles/10.1016/j.crma.2019.05.009/}
}
TY - JOUR AU - Audouze, Christophe AU - Nair, Prasanth B. TI - Sparse approximate solutions to stochastic Galerkin equations JO - Comptes Rendus. Mathématique PY - 2019 SP - 561 EP - 570 VL - 357 IS - 6 PB - Elsevier UR - http://www.numdam.org/articles/10.1016/j.crma.2019.05.009/ DO - 10.1016/j.crma.2019.05.009 LA - en ID - CRMATH_2019__357_6_561_0 ER -
%0 Journal Article %A Audouze, Christophe %A Nair, Prasanth B. %T Sparse approximate solutions to stochastic Galerkin equations %J Comptes Rendus. Mathématique %D 2019 %P 561-570 %V 357 %N 6 %I Elsevier %U http://www.numdam.org/articles/10.1016/j.crma.2019.05.009/ %R 10.1016/j.crma.2019.05.009 %G en %F CRMATH_2019__357_6_561_0
Audouze, Christophe; Nair, Prasanth B. Sparse approximate solutions to stochastic Galerkin equations. Comptes Rendus. Mathématique, Tome 357 (2019) no. 6, pp. 561-570. doi : 10.1016/j.crma.2019.05.009. http://www.numdam.org/articles/10.1016/j.crma.2019.05.009/
[1] A stopping criterion for iterative solution of stochastic Galerkin matrix equations, Int. J. Uncertain. Quantificat., Volume 6 (2016) no. 3, pp. 245-269
[2] Galerkin finite element approximations of stochastic elliptic partial differential equations, SIAM J. Numer. Anal., Volume 42 (2004), pp. 800-825
[3] Convergence of quasi-optimal Stochastic Galerkin methods for a class of PDES with random coefficients, Comput. Math. Appl., Volume 67 (2014) no. 4, pp. 732-751
[4] Energy norm a posteriori estimation for parametric operator equations, SIAM J. Sci. Comput., Volume 36 (2014), pp. 339-363
[5] Sparse High Order FEM for Elliptic SPDEs, ETH, Zürich, Switzerland, 2008 (Research Report No. 2008-22)
[6] Accelerated iterative hard thresholding, Signal Process., Volume 92 (2012), pp. 752-756
[7] A posteriori error analysis of parameterized linear systems using spectral methods, SIAM J. Matrix Anal. Appl., Volume 33 (2012) no. 1, pp. 195-209
[8] Convergence Rates of Best N-Term Galerkin Approximations for a Class of Elliptic SPDEs, University of Zürich, Switzerland, 2009 (Research Report No. 2009-02)
[9] Spectral methods for parameterized matrix equations, SIAM J. Matrix Anal. Appl., Volume 31 (2010) no. 5, pp. 2681-2699
[10] Stochastic Galerkin matrices, SIAM J. Matrix Anal. Appl., Volume 31 (2010) no. 4, pp. 1848-1872
[11] Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems, IEEE J. Sel. Top. Signal Process., Volume 1 (2008) no. 4, pp. 586-597
[12] Generalized Arnoldi–Tikhonov method for sparse reconstruction, SIAM J. Sci. Comput., Volume 36 (2014) no. 2, p. B225-B247
[13] Stochastic Finite Elements: A Spectral Approach, Springer Verlag, New York, 1991
[14] Matrix Computations, Johns Hopkins University Press, Baltimore, MD, USA, 2013
[15] Statistical Learning with Sparsity: The Lasso and Generalizations, Monographs on Statistics and Applied Probability, vol. 143, Chapman and Hall/CRC, 2015
[16] A generalized Krylov subspace method for – minimization, SIAM J. Sci. Comput., Volume 37 (2015) no. 5, p. S30-S50
[17] Probability Theory, Springer, 1977
[18] A generalized spectral decomposition technique to solve a class of linear stochastic partial differential equations, Comput. Methods Appl. Mech. Eng., Volume 196 (2007), pp. 4521-4537
[19] Generalized spectral decomposition for stochastic nonlinear problems, J. Comput. Phys., Volume 228 (2009), pp. 202-235
[20] Stochastic Differential Equations. An Introduction with Applications, Springer-Verlag, Berlin, 1998
[21] Block-diagonal preconditioning for spectral stochastic finite-element systems, IMA J. Numer. Anal., Volume 29 (2009), pp. 350-375
[22] Preconditioning steady-state Navier–Stokes equations with random data, SIAM J. Sci. Comput., Volume 34 (2012) no. 5, p. A2482-A2506
[23] An Efficient Reduced Basis Solver for Stochastic Galerkin Matrix Equations, University of Manchester, UK, 2015 (MIMS Report 2015.64)
[24] Sparse finite element approximation of high-dimensional transport-dominated diffusion problems, ESAIM: Math. Model. Numer. Anal., Volume 42 (2008), pp. 777-819
[25] A stochastic Galerkin method for the Boltzmann equation with multi-dimensional random inputs using sparse wavelet bases, Numer. Math., Theory Methods Appl., Volume 10 (2017) no. 2, pp. 1-23
[26] Theory of inexact Krylov subspace methods and applications to scientific computing, SIAM J. Sci. Comput., Volume 25 (2003) no. 2, pp. 454-477
[27] Relaxed Krylov subspace approximation, Proc. Appl. Math. Mech., Volume 5 (2005), pp. 797-800
[28] Hierarchical Schur complement preconditioner for the stochastic Galerkin finite element methods, Numer. Linear Algebra Appl., Volume 21 (2014) no. 1, pp. 136-151
[29] Convergence rates for sparse chaos approximations of elliptic problems with stochastic coefficients, IMA J. Numer. Anal., Volume 27 (2007), pp. 232-261
[30] A Kronecker product preconditioner for stochastic Galerkin finite element discretizations, SIAM J. Sci. Comput., Volume 32 (2010) no. 2, pp. 923-946
[31] High order collocation methods for differential equations with random inputs, SIAM J. Sci. Comput., Volume 27 (2005), pp. 1118-1139
[32] Modeling uncertainty in steady-state diffusion problems via generalized polynomial chaos, Comput. Methods Appl. Mech. Eng., Volume 191 (2003), pp. 4927-4948
Cité par Sources :
