×

Low-rank solution methods for stochastic eigenvalue problems. (English) Zbl 1420.65046

Summary: We study efficient solution methods for stochastic eigenvalue problems arising from discretization of self-adjoint PDEs with random data, where the underlying operators depend linearly on the random parameters. With the stochastic Galerkin approach, the solutions are represented as generalized polynomial chaos expansions. When these solutions can be approximated well by low-rank objects, we introduce a low-rank variant of the inverse subspace iteration algorithm for computing one or several minimal eigenvalues and corresponding eigenvectors of parameter-dependent matrices. In the algorithm, the iterates are approximated by low-rank matrices, which leads to significant cost savings. The algorithm is tested on two benchmark problems: a stochastic diffusion problem with some poorly separated eigenvalues and an operator derived from a discrete stochastic Stokes problem whose minimal eigenvalue is related to the inf-sup stability constant. Numerical experiments show that the low-rank algorithm produces accurate solutions compared to the Monte Carlo method, and it uses much less computational time than the original algorithm without low-rank approximation.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
35R60 PDEs with randomness, stochastic partial differential equations
65F18 Numerical solutions to inverse eigenvalue problems
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs

References:

[1] R. Andreev and C. Schwab, Sparse tensor approximation of parametric eigenvalue problems, in Numerical Analysis of Multiscale Problems, I. G. Graham, T. Y. Hou, O. Lakkis, and R. Scheichl, eds., Springer, Berlin, 2012, pp. 203-241. · Zbl 1248.65116
[2] J. Ballani and L. Grasedyck, A projection method to solve linear systems in tensor format, Numer. Linear Algebra Appl., 20 (2013), pp. 27-43. · Zbl 1289.65049
[3] P. Benner, S. Dolgov, A. Onwunta, and M. Stoll, Low-rank solvers for unsteady Stokes-Brinkman optimal control problem with random data, Comput. Methods Appl. Mech. Engrg., 304 (2016), pp. 26-54. · Zbl 1423.76329
[4] P. Benner, A. Onwunta, and M. Stoll, Low-rank solution of unsteady diffusion equations with stochastic coefficients, SIAM/ASA J. Uncertain. Quantif., 3 (2015), pp. 622-649. · Zbl 1325.65016
[5] P. Benner, A. Onwunta, and M. Stoll, A low-rank inexact Newton-Krylov method for stochastic eigenvalue problems, Comput. Methods Appl. Math., 19 (2019), pp. 5-22. · Zbl 1420.65043
[6] P. Benner, Y. Qiu, and M. Stoll, Low-rank eigenvector compression of posterior covariance matrices for linear Gaussian inverse problems, SIAM/ASA J. Uncertain. Quantif., 6 (2018), pp. 965-989. · Zbl 1398.65057
[7] \AA. Björck and G. H. Golub, Numerical methods for computing angles between linear subspaces, Math. Comp., 27 (1973), pp. 579-594. · Zbl 0282.65031
[8] H. C. Elman, D. J. Silvester, and A. J. Wathen, Finite Elements and Fast Iterative Solvers: With Applications in Incompressible Fluid Dynamics, 2nd ed., Oxford University Press, Oxford, 2014. · Zbl 1304.76002
[9] H. C. Elman and T. Su, A low-rank multigrid method for the stochastic steady-state diffusion problem, SIAM J. Matrix Anal. Appl., 39 (2018), pp. 492-509. · Zbl 1390.35437
[10] O. G. Ernst and E. Ullmann, Stochastic Galerkin matrices, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 1848-1872. · Zbl 1205.65021
[11] I. Fumagalli, A. Manzoni, N. Parolini, and M. Verani, Reduced basis approximation and a posteriori error estimates for parametrized elliptic eigenvalue problems, ESAIM Math. Model. Numer. Anal., 50 (2016), pp. 1857-1885. · Zbl 1355.65149
[12] T. Gerstner and M. Griebel, Numerical integration using sparse grids, Numer. Algorithms, 18 (1998), pp. 209-232. · Zbl 0921.65022
[13] R. Ghanem and D. Ghosh, Efficient characterization of the random eigenvalue problem in a polynomial chaos decomposition, Internat. J. Numer. Methods Engrg., 72 (2007), pp. 486-504. · Zbl 1194.74153
[14] G. H. Golub and Q. Ye, Inexact inverse iteration for generalized eigenvalue problems, BIT, 40 (2000), pp. 671-684. · Zbl 0984.65032
[15] W. Hackbusch, Solution of linear systems in high spatial dimensions, Comput. Vis. Sci., 17 (2015), pp. 111-118. · Zbl 1388.65032
[16] H. Hakula, V. Kaarnioja, and M. Laaksonen, Approximate methods for stochastic eigenvalue problems, Appl. Math. Comput., 267 (2015), pp. 664-681. · Zbl 1410.60066
[17] H. Hakula and M. Laaksonen, Asymptotic convergence of spectral inverse iterations for stochastic eigenvalue problems, Numer. Math., (2019), pp. 1-33. · Zbl 07073234
[18] T. Horger, B. Wohlmuth, and T. Dickopf, Simultaneous reduced basis approximation of parameterized elliptic eigenvalue problems, ESAIM Math. Model. Numer. Anal., 51 (2017), pp. 443-465. · Zbl 1362.65121
[19] D. B. P. Huynh, G. Rozza, S. Sen, and A. T. Patera, A successive constraint linear optimization method for lower bounds of parametric coercivity and inf-sup stability constants, Comptes Rendus Math., 345 (2007), pp. 473-478. · Zbl 1127.65086
[20] A. Klimke and B. Wohlmuth, Algorithm 847: SPINTERP: Piecewise multilinear hierarchical sparse grid interpolation in MATLAB, ACM Trans. Math. Software, 31 (2005), pp. 561-579. · Zbl 1136.65308
[21] A. V. Knyazev, Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method, SIAM J. Sci. Comput., 23 (2001), pp. 517-541. · Zbl 0992.65028
[22] D. Kressner and C. Tobler, Low-rank tensor Krylov subspace methods for parametrized linear systems, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 1288-1316. · Zbl 1237.65034
[23] D. Kressner and C. Tobler, Preconditioned low-rank methods for high-dimensional elliptic PDE eigenvalue problems, Comput. Methods Appl. Math., 11 (2011), pp. 363-381. · Zbl 1283.65025
[24] Y.-L. Lai, K.-Y. Lin, and W.-W. Lin, An inexact inverse iteration for large sparse eigenvalue problems, Numer. Linear Algebra Appl., 4 (1997), pp. 425-437. · Zbl 0889.65038
[25] K. Lee and H. C. Elman, A preconditioned low-rank projection method with a rank-reduction scheme for stochastic partial differential equations, SIAM J. Sci. Comput., 39 (2017), pp. 828-850. · Zbl 1373.60126
[26] M. Loève, Probability Theory, Van Nostrand, New York, 1960. · Zbl 0095.12201
[27] L. Machiels, Y. Maday, I. B. Oliveira, A. T. Patera, and D. V. Rovas, Output bounds for reduced-basis approximations of symmetric positive definite eigenvalue problems, C. R. Math. Acad. Sci. Paris, 331 (2000), pp. 153-158. · Zbl 0960.65063
[28] H. Meidani and R. Ghanem, Spectral power iterations for the random eigenvalue problem, AIAA J., 52 (2014), pp. 912-925.
[29] N. Ngoc Cuong, K. Veroy, and A. T. Patera, Certified real-time solution of parametrized partial differential equations, in Handbook of Materials Modeling, S. Yip, ed., Springer, Dordrecht, the Netherlands, 2005, pp. 1529-1564.
[30] C. E. Powell and H. C. Elman, Block-diagonal preconditioning for spectral stochastic finite-element systems, IMA J. Numer. Anal., 29 (2009), pp. 350-375. · Zbl 1169.65007
[31] C. E. Powell and D. J. Silvester, Preconditioning steady-state Navier-Stokes equations with random data, SIAM J. Sci. Comput., 34 (2012), pp. A2482-A2506. · Zbl 1256.35216
[32] H. J. Pradlwarter, G. I. Schuëller, and G. S. Szekely, Random eigenvalue problems for large systems, Comput. Struct., 80 (2002), pp. 2415-2424.
[33] M. Robbé, M. Sadkane, and A. Spence, Inexact inverse subspace iteration with preconditioning applied to non-Hermitian eigenvalue problems, SIAM J. Matrix Anal. Appl., 31 (2009), pp. 92-113. · Zbl 1269.65036
[34] D. Silvester, H. Elman, and A. Ramage, Incompressible Flow and Iterative Solver Software (IFISS), Version 3.4, 2015, http://www.manchester.ac.uk/ifiss.
[35] D. J. Silvester and V. Simoncini, An optimal iterative solver for symmetric indefinite systems stemming from mixed approximation, ACM Trans. Math. Software, 37 (2011), p. 42. · Zbl 1365.65085
[36] P. Sirković and D. Kressner, Subspace acceleration for large-scale parameter-dependent Hermitian eigenproblems, SIAM J. Matrix Anal. Appl., 37 (2016), pp. 695-718. · Zbl 1382.65104
[37] D. C. Sorensen, Implicit application of polynomial filters in a \(k\)-step Arnoldi method, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 357-385. · Zbl 0763.65025
[38] B. Sousedík and H. C. Elman, Inverse subspace iteration for spectral stochastic finite element methods, SIAM/ASA J. Uncertain. Quantif., 4 (2016), pp. 163-189. · Zbl 1336.65060
[39] B. Sousedík and H. C. Elman, Stochastic Galerkin methods for the steady-state Navier-Stokes equations, J. Comput. Phys., 316 (2016), pp. 435-452. · Zbl 1349.76268
[40] G. W. Stewart, Accelerating the orthogonal iteration for the eigenvectors of a Hermitian matrix, Numer. Math., 13 (1969), pp. 362-376. · Zbl 0185.40203
[41] G. W. Stewart, Matrix Algorithms: Volume II: Eigensystems, SIAM, Philadelphia, 2001. · Zbl 0984.65031
[42] C. V. Verhoosel, M. A. Gutiérrez, and S. J. Hulshoff, Iterative solution of the random eigenvalue problem with application to spectral stochastic finite element systems, Internat. J. Numer. Methods Engrg., 68 (2006), pp. 401-424. · Zbl 1127.76054
[43] K. Veroy and A. T. Patera, Certified real-time solution of the parametrized steady incompressible Navier-Stokes equations: Rigorous reduced-basis a posteriori error bounds, Internat. J. Numer. Methods Fluids, 47 (2005), pp. 773-788. · Zbl 1134.76326
[44] D. Xiu and G. E. Karniadakis, Modeling uncertainty in flow simulations via generalized polynomial chaos, J. Comput. Phys., 187 (2003), pp. 137-167. · Zbl 1047.76111
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.