×

Adaptive stochastic Galerkin FEM with hierarchical tensor representations. (English) Zbl 1397.65262

Summary: The solution of PDE with stochastic data commonly leads to very high-dimensional algebraic problems, e.g. when multiplicative noise is present. The Stochastic Galerkin FEM considered in this paper then suffers from the curse of dimensionality. This is directly related to the number of random variables required for an adequate representation of the random fields included in the PDE. With the presented new approach, we circumvent this major complexity obstacle by combining two highly efficient model reduction strategies, namely a modern low-rank tensor representation in the tensor train format of the problem and a refinement algorithm on the basis of a posteriori error estimates to adaptively adjust the different employed discretizations. The adaptive adjustment includes the refinement of the FE mesh based on a residual estimator, the problem-adapted stochastic discretization in anisotropic Legendre Wiener chaos and the successive increase of the tensor rank. Computable a posteriori error estimators are derived for all error terms emanating from the discretizations and the iterative solution with a preconditioned ALS scheme of the problem. Strikingly, it is possible to exploit the tensor structure of the problem to evaluate all error terms very efficiently. A set of benchmark problems illustrates the performance of the adaptive algorithm with higher-order FE. Moreover, the influence of the tensor rank on the approximation quality is investigated.

MSC:

65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
35R60 PDEs with randomness, stochastic partial differential equations
47B80 Random linear operators
60H35 Computational methods for stochastic equations (aspects of stochastic analysis)
65J10 Numerical solutions to equations with linear operators
65N12 Stability and convergence of numerical methods for boundary value problems involving PDEs
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65N75 Probabilistic methods, particle methods, etc. for boundary value problems involving PDEs
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ainsworth, M., Oden, J.T.: A Posteriori Error Estimation in Finite Element Analysis. Pure and Applied Mathematics (New York). Wiley-Interscience [Wiley], New York (2000) · Zbl 1008.65076
[2] Babuška, I., Chatzipantelidis, P.: On solving elliptic stochastic partial differential equations. Comput. Methods Appl. Mech. Eng. 191(37-38), 4093-4122 (2002) · Zbl 1019.65010 · doi:10.1016/S0045-7825(02)00354-7
[3] Babuška, I., Nobile, F., Tempone, R.: A stochastic collocation method for elliptic partial differential equations with random input data. SIAM J. Numer. Anal. 45(3), 1005-1034 (2007) · Zbl 1151.65008 · doi:10.1137/050645142
[4] Babuška, I., Tempone, R., Zouraris, G.E.: Galerkin finite element approximations of stochastic elliptic partial differential equations. SIAM J. Numer. Anal. 42(2), 800-825 (2004) · Zbl 1080.65003 · doi:10.1137/S0036142902418680
[5] Babuška, I., Tempone, R., Zouraris, G.E.: Solving elliptic boundary value problems with uncertain coefficients by the finite element method: the stochastic formulation. Comput. Methods Appl. Mech. Eng. 194(12-16), 1251-1294 (2005) · Zbl 1087.65004 · doi:10.1016/j.cma.2004.02.026
[6] Bachmayr, M., Cohen, A., Migliorati, G.: Sparse polynomial approximation of parametric elliptic pdes. Part i: affine coefficients (2015). arXiv:1509.07045 · Zbl 1365.41003
[7] Ballani, J., Grasedyck, L.: Hierarchical tensor approximation of output quantities of parameter-dependent pdes. SIAM/ASA J. Uncertainty Quantification. 3(1), 852-872 (2015) · Zbl 1327.65010 · doi:10.1137/140960980
[8] Bespalov, A., Powell, C.E., Silvester, D.: Energy norm a posteriori error estimation for parametric operator equations. SIAM J. Sci. Comput. 36(2), A339-A363 (2014) · Zbl 1294.35199
[9] Braess, D.: Finite Elements: Theory, fast solvers, and applications in elasticity theory (Translated from the German by Schumaker, L.L) Cambridge University Press, Cambridge (2007) · Zbl 1118.65117
[10] Carstensen, C., Eigel, M., Hoppe, R.H.W., Löbhard, C.: A review of unified a posteriori finite element error control. Numer. Math. Theor. Methods. Appl. 5(4), 509-558 (2012) · Zbl 1289.65249 · doi:10.4208/nmtma.2011.m1032
[11] Chen, P., Quarteroni, A., Rozza, G.: A weighted reduced basis method for elliptic partial differential equations with random input data. SIAM J. Numer. Anal. 51(6), 3163-3185 (2013) · Zbl 1288.65007 · doi:10.1137/130905253
[12] Chen, P., Quarteroni, A., Rozza, G.: Comparison between reduced basis and stochastic collocation methods for elliptic problems. J. Sci. Comput. 59(1), 187-216 (2014) · Zbl 1301.65007 · doi:10.1007/s10915-013-9764-2
[13] Cohen, A., DeVore, R., Schwab, C.: Convergence rates of best \[NN\]-term Galerkin approximations for a class of elliptic sPDEs. Found. Comput. Math. 10(6), 615-646 (2010) · Zbl 1206.60064 · doi:10.1007/s10208-010-9072-2
[14] Cohen, A., Devore, R., Schwab, C.: Analytic regularity and polynomial approximation of parametric and stochastic elliptic PDE’s. Anal. Appl. (Singap.) 9(1), 11-47 (2011) · Zbl 1219.35379 · doi:10.1142/S0219530511001728
[15] de Silva, V., Lim, L.H.: Tensor rank and the ill-posedness of the best low-rank approximation problem. SIAM J. Matrix Anal. Appl. 30(3), 1084-1127 (2008) · Zbl 1167.14038 · doi:10.1137/06066518X
[16] Deb, M.K., Babuška, I.M., Oden, J.T.: Solution of stochastic partial differential equations using Galerkin finite element techniques. Comput. Methods Appl. Mech. Eng. 190(48), 6359-6372 (2001) · Zbl 1075.65006 · doi:10.1016/S0045-7825(01)00237-7
[17] Sergey, D., Khoromskij, B.N., Litvinenko, A., Matthies, H.G.: Computation of the response surface in the tensor train data format (2014). arXiv:1406.2816 · Zbl 1329.65271
[18] Dolgov, S., Khoromskij, B.N., Litvinenko, A., Matthies, H.G.: Polynomial chaos expansion of random coefficients and the solution of stochastic partial differential equations in the tensor train format (2015). arXiv preprint. arXiv:1503.03210 · Zbl 1329.65271
[19] Dolgov, S.V., Savostyanov, D.V.: Alternating minimal energy methods for linear systems in higher dimensions. SIAM J. Sci. Comput. 36(5), A2248-A2271 (2014) · Zbl 1307.65035 · doi:10.1137/140953289
[20] Eigel, M., Gittelson, C.J., Schwab, C., Zander, E.: Adaptive stochastic Galerkin FEM. Comput. Methods Appl. Mech. Eng. 270, 247-269 (2014) · Zbl 1296.65157 · doi:10.1016/j.cma.2013.11.015
[21] Eigel, M., Gittelson, C.J., Schwab, C., Zander, E.: A convergent adaptive stochastic galerkin finite element method with quasi-optimal spatial meshes. ESAIM Math. Model. Numer. Anal. 49(5), 1367-1398 (2015) · Zbl 1335.65006 · doi:10.1051/m2an/2015017
[22] Eigel, M., Merdon, C.: Local equilibration error estimators for guaranteed error control in adaptive stochastic higher-order galerkin fem. WIAS Preprint (1997) (2014) · Zbl 1398.65297
[23] Eigel, M., Zander, E.: \[ \mathtt{alea}\] alea—A Python Framework for Spectral Methods and Low-Rank Approximations in Uncertainty Quantification. https://bitbucket.org/aleadev/alea · Zbl 1143.65392
[24] Ernst, O.G., Mugler, A., Starkloff, H., Ullmann, E.: On the convergence of generalized polynomial chaos expansions. Technical Report 60, DFG Schwerpunktprogramm 1324, (2010) · Zbl 1273.65012
[25] Espig, M., Hackbusch, W., Khachatryan, A.: On the convergence of alternating least squares optimisation in tensor format Representations. 423, (2015). arXiv:1506.00062
[26] Espig, M., Hackbusch, W., Litvinenko, A., Matthies, H.G., Wähnert, P.: Efficient low-rank approximation of the stochastic Galerkin matrix in tensor formats. Preprint, Max Planck Institute for Mathematics in the Sciences (2012) · Zbl 1350.65005
[27] Espig, M., Hackbusch, W., Litvinenko, A., Matthies, H.G., Zander, E.: Efficient analysis of high dimensional data in tensor formats. In Sparse Grids and Applications, pp. 31-56. Springer (2013) · Zbl 1075.65006
[28] FEniCS Project - Automated solution of Differential Equations by the Finite Element Method. http://fenicsproject.org · Zbl 1296.65157
[29] Fischer, J., Otto, F.: A higher-order large-scale regularity theory for random elliptic operators. MPI-MIS preprint Leipzig (2015) · Zbl 1349.35440
[30] Frauenfelder, P., Christoph, S., Todor, R.A.: Finite elements for elliptic problems with stochastic coefficients. Comput. Methods Appl. Mech. Eng. 194(2-5), 205-228 (2005) · Zbl 1143.65392 · doi:10.1016/j.cma.2004.04.008
[31] Garcia, L.D., Stillman, M., Sturmfels, B.: Algebraic geometry of bayesian networks. J. Symbolic Comput. 39(3-4), 331-355 (2005). (Special issue on the occasion of MEGA 2003) · Zbl 1126.68102 · doi:10.1016/j.jsc.2004.11.007
[32] Ghanem, R.G., Kruger, R.M.: Numerical solution of spectral stochastic finite element systems. Comput. Methods Appl. Mech. Eng. 129(3), 289-303 (1996) · Zbl 0861.73071 · doi:10.1016/0045-7825(95)00909-4
[33] Ghanem, R.G., Spanos, P.D.: Stochastic Finite Elements: A Spectral Approach. Springer, New York (1991) · Zbl 0722.73080
[34] Gittelson, C.J.: Stochastic Galerkin approximation of operator equations with infinite dimensional noise. Technical Report 2011-10, Seminar for Applied Mathematics, ETH Zürich (2011) · Zbl 1289.65249
[35] Grasedyck, L.: Hierarchical singular value decomposition of tensors. SIAM J. Matrix Anal. Appl. 31(4), 2029-2054 (2010) · Zbl 1210.65090
[36] Gunzburger, M.D., Webster, C.G., Zhang, G.: Stochastic finite element methods for partial differential equations with random input data. Acta Numer. 23, 521-650 (2014) · Zbl 1398.65299
[37] Hackbusch, W.: Tensor spaces and numerical tensor calculus. Springer Series in Computational Mathematics, vol. 42. Springer, Heidelberg (2012) · Zbl 1244.65061
[38] Hackbusch, W.: Numerical tensor calculus. Acta Numer. 23, 651-742 (2014) · Zbl 1396.65091 · doi:10.1017/S0962492914000087
[39] Hackbusch, W., Kühn, S.: A new scheme for the tensor representation. J. Fourier Anal. Appl. 15(5), 706-722 (2009) · Zbl 1188.15022 · doi:10.1007/s00041-009-9094-9
[40] Hackbusch, W., Schneider,R.: Tensor spaces and hierarchical tensor representations. In: Extr. Quant. Inf. Complex Syst., pp. 237-261. Springer (2014) · Zbl 1317.65102
[41] Holtz, S., Rohwedder, T., Schneider, R.: The alternating linear scheme for tensor optimization in the tensor train format. SIAM J. Sci. Comput. 34(2), A683-A713 (2012) · Zbl 1252.15031 · doi:10.1137/100818893
[42] Holtz, S., Rohwedder, T., Schneider, R.: On manifolds of tensors of fixed TT-rank. Numerische Mathematik 120(4), 701-731 (2012) · Zbl 1242.15022 · doi:10.1007/s00211-011-0419-7
[43] Khoromskij, B.N., Oseledets, I.V.: Quantics-TT collocation approximation of parameter-dependent and stochastic elliptic PDEs. Comput. Methods Appl. Math. 10(4), 376-394 (2010) · Zbl 1283.65039
[44] Khoromskij, B.N., Schwab, C.: Tensor-structured Galerkin approximation of parametric and stochastic elliptic PDEs. SIAM J. Sci. Comput. 33(1), 364-385 (2011) · Zbl 1243.65009 · doi:10.1137/100785715
[45] Kolda, T.G., Bader, B.W.: Tensor decompositions and applications. SIAM Rev. 51(3), 455-500 (2009) · Zbl 1173.65029 · doi:10.1137/07070111X
[46] Landsberg, J.M.: Tensors: Geometry and Applications. In: Graduate studies in mathematics, American Mathematical Society, USA (2012) · Zbl 1238.15013
[47] De Lathauwer, L., De Moor, B., Vandewalle, J.: A multilinear singular value decomposition. SIAM J. Matrix Anal. Appl. 21(4), 1253-1278 (2000) · Zbl 0962.15005 · doi:10.1137/S0895479896305696
[48] Matthies, H.G., Keese, A.: Galerkin methods for linear and nonlinear elliptic stochastic partial differential equations. Comput. Methods Appl. Mech. Eng. 194(12-16), 1295-1331 (2005) · Zbl 1088.65002 · doi:10.1016/j.cma.2004.05.027
[49] Nobile, F., Tempone, R., Webster, C.G.: An anisotropic sparse grid stochastic collocation method for partial differential equations with random input data. SIAM J. Numer. Anal. 46(5), 2411-2442 (2008) · Zbl 1176.65007
[50] Nobile, F., Tempone, R., Webster, C.G.: A sparse grid stochastic collocation method for partial differential equations with random input data. SIAM J. Numer. Anal. 46(5), 2309-2345 (2008) · Zbl 1176.65137
[51] Oseledets, I.: Tensor-train decomposition. SIAM J. Sci. Comput. 33(5), 2295-2317 (2011) · Zbl 1232.15018 · doi:10.1137/090752286
[52] Oseledets, I.V.: ttpy - A Python Implementation of the TT-Toolbox. https://github.com/oseledets/ttpy · Zbl 1173.65029
[53] Oseledets, I.V.: Tensor-train decomposition. SIAM J. Sci. Comput. 33(5), 2295-2317 (2011) · Zbl 1232.15018
[54] Oseledets, I.V., Tyrtyshnikov, E.: TT-cross approximation for multidimensional arrays. Linear Algebra Appl. 432(1), 70-88 (2010) · Zbl 1183.65040 · doi:10.1016/j.laa.2009.07.024
[55] Pellissetti, M.F., Ghanem, R.G.: Iterative solution of systems of linear equations arising in the context of stochastic finite elements. Adv. Eng. Softw. 31(8), 607-616 (2000) · Zbl 1003.68553 · doi:10.1016/S0965-9978(00)00034-X
[56] Powell, C.E., Elman, H.C.: Block-diagonal preconditioning for spectral stochastic finite-element systems. IMA J. Numer. Anal. 29, 350-375 (2009) · Zbl 1169.65007
[57] Rohwedder, T., Uschmajew, A.: On local convergence of alternating schemes for optimization of convex problems in the tensor train format. SIAM J. Numer. Anal. 51(2), 1134-1162 (2013) · Zbl 1273.65088 · doi:10.1137/110857520
[58] Schmidt, E.: Zur Theorie der linearen und nichtlinearen Integralgleichungen. I. Teil: Entwicklung. Mathematische Annalen 63, 433-476 (1907) · JFM 38.0377.02 · doi:10.1007/BF01449770
[59] Schneider, R., Uschmajew, A.: Convergence results for projected line-search methods on varieties of low-rank matrices via Łojasiewicz inequality. SIAM J. Optim. 25(1), 622-646 (2015) · Zbl 1355.65079 · doi:10.1137/140957822
[60] Schwab, C., Gittelson, C.J.: Sparse tensor discretizations of high-dimensional parametric and stochastic PDEs. Acta Numer. 20, 291-467 (2011) · Zbl 1269.65010
[61] Szalay, S., Pfeffer, M., Murg, V., Barcza, G., Verstraete, F., Schneider, R., Legeza,Ö.: Tensor product methods and entanglement optimization for ab initio quantum chemistry. Int. J. Quantum Chem. 115(19), 1342-1391 (2015) doi:10.1002/qua.24898
[62] Ullmann, E.: A kronecker product preconditioner for stochastic galerkin finite element discretizations. SIAM J. Sci. Comput. 32(2), 923-946 (2010) · Zbl 1210.35306
[63] Uschmajew, A., Vandereycken, B.: The geometry of algorithms using hierarchical tensors. Linear Algebra Appl 439(1), 133-166 (2013) · Zbl 1281.65062 · doi:10.1016/j.laa.2013.03.016
[64] Verfürth, R.: A Review of a Posteriori Error Estimation and Adaptive Mesh-Refinement Techniques. Teubner Verlag and J. Wiley, Stuttgart (1996) · Zbl 0853.65108
[65] Xiu, D., Hesthaven, J.S.: High-order collocation methods for differential equations with random inputs. SIAM J. Sci. Comput. 27(3), 1118-1139 (2005). (electronic) · Zbl 1091.65006 · doi:10.1137/040615201
[66] Xiu, D., Karniadakis, G.E.: Modeling uncertainty in steady state diffusion problems via generalized polynomial chaos. Comput. Methods Appl. Mech. Eng. 191(43), 4927-4948 (2002) · Zbl 1016.65001 · doi:10.1016/S0045-7825(02)00421-8
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.