×

A low-rank inexact Newton-Krylov method for stochastic eigenvalue problems. (English) Zbl 1420.65043

Summary: This paper aims at the efficient numerical solution of stochastic eigenvalue problems. Such problems often lead to prohibitively high-dimensional systems with tensor product structure when discretized with the stochastic Galerkin method. Here, we exploit this inherent tensor product structure to develop a globalized low-rank inexact Newton method with which we tackle the stochastic eigenproblem. We illustrate the effectiveness of our solver with numerical experiments.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
60H15 Stochastic partial differential equations (aspects of stochastic analysis)
35R60 PDEs with randomness, stochastic partial differential equations
60H35 Computational methods for stochastic equations (aspects of stochastic analysis)
65F50 Computational methods for sparse matrices

Software:

HSL_MI20
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] H.-B. An, Z.-Y. Mo and X.-P. Liu, A choice of forcing terms in inexact Newton method, J. Comput. Appl. Math. 200 (2007), no. 1, 47-60.; An, H.-B.; Mo, Z.-Y.; Liu, X.-P., A choice of forcing terms in inexact Newton method, J. Comput. Appl. Math., 200, 1, 47-60 (2007) · Zbl 1112.65044
[2] 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), 26-54.; Benner, P.; Dolgov, S.; Onwunta, A.; Stoll, M., Low-rank solvers for unsteady Stokes-Brinkman optimal control problem with random data, Comput. Methods Appl. Mech. Engrg., 304, 26-54 (2016) · Zbl 1423.76329
[3] P. Benner, A. Onwunta and M. Stoll, Low-rank solution of unsteady diffusion equations with stochastic coefficients, SIAM/ASA J. Uncertain. Quantif. 3 (2015), no. 1, 622-649.; Benner, P.; Onwunta, A.; Stoll, M., Low-rank solution of unsteady diffusion equations with stochastic coefficients, SIAM/ASA J. Uncertain. Quantif., 3, 1, 622-649 (2015) · Zbl 1325.65016
[4] P. Benner, A. Onwunta and M. Stoll, Block-diagonal preconditioning for optimal control problems constrained by PDEs with uncertain inputs, SIAM J. Matrix Anal. Appl. 37 (2016), no. 2, 491-518.; Benner, P.; Onwunta, A.; Stoll, M., Block-diagonal preconditioning for optimal control problems constrained by PDEs with uncertain inputs, SIAM J. Matrix Anal. Appl., 37, 2, 491-518 (2016) · Zbl 1382.65074
[5] M. Benzi, G. H. Golub and J. Liesen, Numerical solution of saddle point problems, Acta Numer. 14 (2005), 1-137.; Benzi, M.; Golub, G. H.; Liesen, J., Numerical solution of saddle point problems, Acta Numer., 14, 1-137 (2005) · Zbl 1115.65034
[6] E. K. Blum and A. R. Curtis, A convergent gradient method for matrix eigenvector-eigentuple problems, Numer. Math. 31 (1978/79), no. 3, 247-263.; Blum, E. K.; Curtis, A. R., A convergent gradient method for matrix eigenvector-eigentuple problems, Numer. Math., 31, 3, 247-263 (197879) · Zbl 0421.65024
[7] J. Boyle, M. Mihajlović and J. Scott, HSL_MI20: An efficient AMG preconditioner for finite element problems in 3D, Internat. J. Numer. Methods Engrg. 82 (2010), no. 1, 64-98.; Boyle, J.; Mihajlović, M.; Scott, J., HSL_MI20: An efficient AMG preconditioner for finite element problems in 3D, Internat. J. Numer. Methods Engrg., 82, 1, 64-98 (2010) · Zbl 1183.76799
[8] P. R. Brune, M. G. Knepley, B. F. Smith and X. Tu, Composing scalable nonlinear algebraic solvers, SIAM Rev. 57 (2015), no. 4, 535-565.; Brune, P. R.; Knepley, M. G.; Smith, B. F.; Tu, X., Composing scalable nonlinear algebraic solvers, SIAM Rev., 57, 4, 535-565 (2015) · Zbl 1336.65030
[9] X. C. Cai, W. D. Gropp, D. E. Keyes and M. D. Tidriti, Newton-Krylov-Schwarz methods in CFD, Numerical Methods for the Navier-Stokes Equations (Heidelberg 1993), Springer, Berlin (1994), 17-30.; Cai, X. C.; Gropp, W. D.; Keyes, D. E.; Tidriti, M. D., Newton-Krylov-Schwarz methods in CFD, Numerical Methods for the Navier-Stokes Equations, 17-30 (1994) · Zbl 0876.76059
[10] K. A. Cliffe, M. B. Giles, R. Scheichl and A. L. Teckentrup, Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients, Comput. Vis. Sci. 14 (2011), no. 1, 3-15.; Cliffe, K. A.; Giles, M. B.; Scheichl, R.; Teckentrup, A. L., Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients, Comput. Vis. Sci., 14, 1, 3-15 (2011) · Zbl 1241.65012
[11] R. S. Dembo, S. C. Eisenstat and T. Steihaug, Inexact Newton methods, SIAM J. Numer. Anal. 19 (1982), no. 2, 400-408.; Dembo, R. S.; Eisenstat, S. C.; Steihaug, T., Inexact Newton methods, SIAM J. Numer. Anal., 19, 2, 400-408 (1982) · Zbl 0478.65030
[12] R. S. Dembo and T. a. Steihaug, Truncated Newton algorithms for large-scale unconstrained optimization, Math. Programming 26 (1983), no. 2, 190-212.; Dembo, R. S.; Steihaug, T. a., Truncated Newton algorithms for large-scale unconstrained optimization, Math. Programming, 26, 2, 190-212 (1983) · Zbl 0523.90078
[13] S. C. Eisenstat and H. F. Walker, Globally convergent inexact Newton methods, SIAM J. Optim. 4 (1994), no. 2, 393-422.; Eisenstat, S. C.; Walker, H. F., Globally convergent inexact Newton methods, SIAM J. Optim., 4, 2, 393-422 (1994) · Zbl 0814.65049
[14] S. C. Eisenstat and H. F. Walker, Choosing the forcing terms in an inexact Newton method, SIAM J. Sci. Comput. 17 (1996), no. 1, 16-32.; Eisenstat, S. C.; Walker, H. F., Choosing the forcing terms in an inexact Newton method, SIAM J. Sci. Comput., 17, 1, 16-32 (1996) · Zbl 0845.65021
[15] H. C. Elman, D. J. Silvester and A. J. Wathen, Finite Elements and Fast Iterative Solvers: With Applications in Incompressible Fluid Dynamics, 2nd ed., Numer. Math. Sci. Comput., Oxford University Press, Oxford, 2014.; Elman, H. C.; Silvester, D. J.; Wathen, A. J., Finite Elements and Fast Iterative Solvers: With Applications in Incompressible Fluid Dynamics (2014) · Zbl 1304.76002
[16] P. E. Farrell, A. Birkisson and S. W. Funke, Deflation techniques for finding distinct solutions of nonlinear partial differential equations, SIAM J. Sci. Comput. 37 (2015), no. 4, A2026-A2045.; Farrell, P. E.; Birkisson, A.; Funke, S. W., Deflation techniques for finding distinct solutions of nonlinear partial differential equations, SIAM J. Sci. Comput., 37, 4, A2026-A2045 (2015) · Zbl 1327.65237
[17] R. Ghanem and D. Ghosh, Efficient characterization of the random eigenvalue problem in a polynomial chaos decomposition, Internat. J. Numer. Methods Engrg. 72 (2007), no. 4, 486-504.; Ghanem, R.; Ghosh, D., Efficient characterization of the random eigenvalue problem in a polynomial chaos decomposition, Internat. J. Numer. Methods Engrg., 72, 4, 486-504 (2007) · Zbl 1194.74153
[18] R. G. Ghanem and P. D. Spanos, Stochastic Finite Elements: A Spectral Approach, Springer, New York, 1991.; Ghanem, R. G.; Spanos, P. D., Stochastic Finite Elements: A Spectral Approach (1991) · Zbl 0722.73080
[19] W. R. Gilks, S. Richardson and D. J. Spiegelhalter, Markov Chain Monte Carlo in Practice, Interdiscip. Statist., Chapman & Hall, London, 1996.; Gilks, W. R.; Richardson, S.; Spiegelhalter, D. J., Markov Chain Monte Carlo in Practice (1996) · Zbl 0832.00018
[20] G. H. Golub and C. F. Van Loan, Matrix Computations, 3rd ed., Johns Hopkins Stud. Math. Sci., Johns Hopkins University Press, Baltimore, 1996.; Golub, G. H.; Van Loan, C. F., Matrix Computations (1996) · Zbl 0865.65009
[21] H. Hakula, V. Kaarnioja and M. Laaksonen, Approximate methods for stochastic eigenvalue problems, Appl. Math. Comput. 267 (2015), 664-681.; Hakula, H.; Kaarnioja, V.; Laaksonen, M., Approximate methods for stochastic eigenvalue problems, Appl. Math. Comput., 267, 664-681 (2015) · Zbl 1410.60066
[22] M. E. Hochstenbach, T. Košir and B. Plestenjak, A Jacobi-Davidson type method for the two-parameter eigenvalue problem, SIAM J. Matrix Anal. Appl. 26 (2004/05), no. 2, 477-497.; Hochstenbach, M. E.; Košir, T.; Plestenjak, B., A Jacobi-Davidson type method for the two-parameter eigenvalue problem, SIAM J. Matrix Anal. Appl., 26, 2, 477-497 (200405) · Zbl 1077.65036
[23] M. E. Hochstenbach and B. Plestenjak, A Jacobi-Davidson type method for a right definite two-parameter eigenvalue problem, SIAM J. Matrix Anal. Appl. 24 (2002), no. 2, 392-410.; Hochstenbach, M. E.; Plestenjak, B., A Jacobi-Davidson type method for a right definite two-parameter eigenvalue problem, SIAM J. Matrix Anal. Appl., 24, 2, 392-410 (2002) · Zbl 1025.65023
[24] D. A. Knoll and P. R. McHugh, A fully implicit direct Newton’s method for the steady-state Navier-Stokes equations, Internat. J. Numer. Methods Fluids 17 (1993), no. 6, 449-461.; Knoll, D. A.; McHugh, P. R., A fully implicit direct Newton’s method for the steady-state Navier-Stokes equations, Internat. J. Numer. Methods Fluids, 17, 6, 449-461 (1993) · Zbl 0784.76068
[25] D. Kressner and C. Tobler, Low-rank tensor Krylov subspace methods for parametrized linear systems, SIAM J. Matrix Anal. Appl. 32 (2011), no. 4, 1288-1316.; Kressner, D.; Tobler, C., Low-rank tensor Krylov subspace methods for parametrized linear systems, SIAM J. Matrix Anal. Appl., 32, 4, 1288-1316 (2011) · Zbl 1237.65034
[26] H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, CBMS-NSF Regional Conf. Ser. in Appl. Math. 63, Society for Industrial and Applied Mathematics, Philadelphia, 1992.; Niederreiter, H., Random Number Generation and Quasi-Monte Carlo Methods (1992) · Zbl 0761.65002
[27] A. Onwunta, Low-rank iterative solvers for stochastic Galerkin linear systems PhD thesis, Otto-von-Guericke Universität, Magdeburg, 2016.; Onwunta, A., Low-rank iterative solvers for stochastic Galerkin linear systems (2016)
[28] C. C. Paige and M. A. Saunders, Solutions of sparse indefinite systems of linear equations, SIAM J. Numer. Anal. 12 (1975), no. 4, 617-629.; Paige, C. C.; Saunders, M. A., Solutions of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12, 4, 617-629 (1975) · Zbl 0319.65025
[29] R. P. Pawlowski, J. N. Shadid, J. P. Simonis and H. F. Walker, Globalization techniques for Newton-Krylov methods and applications to the fully coupled solution of the Navier-Stokes equations, SIAM Rev. 48 (2006), no. 4, 700-721.; Pawlowski, R. P.; Shadid, J. N.; Simonis, J. P.; Walker, H. F., Globalization techniques for Newton-Krylov methods and applications to the fully coupled solution of the Navier-Stokes equations, SIAM Rev., 48, 4, 700-721 (2006) · Zbl 1110.65039
[30] C. E. Powell and H. C. Elman, Block-diagonal preconditioning for spectral stochastic finite-element systems, IMA J. Numer. Anal. 29 (2009), no. 2, 350-375.; Powell, C. E.; Elman, H. C., Block-diagonal preconditioning for spectral stochastic finite-element systems, IMA J. Numer. Anal., 29, 2, 350-375 (2009) · Zbl 1169.65007
[31] H. J. Pradlwarter, G. I. Schuëller and G. S. Szekely, Random eigenvalue problems for large systems, Comput. & Structures 80 (2002), no. 27-30, 2415-2424.; Pradlwarter, H. J.; Schuëller, G. I.; Szekely, G. S., Random eigenvalue problems for large systems, Comput. & Structures, 80, 27-30, 2415-2424 (2002) · Zbl 0959.65008
[32] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia, 2003.; Saad, Y., Iterative Methods for Sparse Linear Systems (2003) · Zbl 1002.65042
[33] Y. Saad, Numerical Methods for Large Eigenvalue Problems, Class. Appl. Math. 66, Society for Industrial and Applied Mathematics, Philadelphia, 2011.; Saad, Y., Numerical Methods for Large Eigenvalue Problems (2011) · Zbl 1242.65068
[34] Y. Saad and M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 7 (1986), no. 3, 856-869.; Saad, Y.; Schultz, M. H., GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7, 3, 856-869 (1986) · Zbl 0599.65018
[35] G. I. Schuaeller and G. S. Szekely, Computational procedure for a fast calculation of eigenvectors and eigenvalues of structures with random properties, Comput. Methods Appl. Mech. Engrg. 191 (2001), no. 8-10, 799-816.; Schuaeller, G. I.; Szekely, G. S., Computational procedure for a fast calculation of eigenvectors and eigenvalues of structures with random properties, Comput. Methods Appl. Mech. Engrg., 191, 8-10, 799-816 (2001) · Zbl 1016.74030
[36] J. N. Shadid, R. S. Tuminaro and H. F. Walker, An inexact Newton method for fully coupled solution of the Navier-Stokes equations with heat and mass transport, J. Comput. Phys. 137 (1997), no. 1, 155-185.; Shadid, J. N.; Tuminaro, R. S.; Walker, H. F., An inexact Newton method for fully coupled solution of the Navier-Stokes equations with heat and mass transport, J. Comput. Phys., 137, 1, 155-185 (1997) · Zbl 0898.76066
[37] C. Soize, Random matrix theory for modeling uncertainties in computational mechanics, Comput. Methods Appl. Mech. Engrg. 194 (2005), no. 12-16, 1333-1366.; Soize, C., Random matrix theory for modeling uncertainties in computational mechanics, Comput. Methods Appl. Mech. Engrg., 194, 12-16, 1333-1366 (2005) · Zbl 1083.74052
[38] B. Sousedík and H. C. Elman, Inverse subspace iteration for spectral stochastic finite element methods, SIAM/ASA J. Uncertain. Quantif. 4 (2016), no. 1, 163-189.; Sousedík, B.; Elman, H. C., Inverse subspace iteration for spectral stochastic finite element methods, SIAM/ASA J. Uncertain. Quantif., 4, 1, 163-189 (2016) · Zbl 1336.65060
[39] M. Stoll and T. Breiten, A low-rank in time approach to PDE-constrained optimization, SIAM J. Sci. Comput. 37 (2015), no. 1, B1-B29.; Stoll, M.; Breiten, T., A low-rank in time approach to PDE-constrained optimization, SIAM J. Sci. Comput., 37, 1, B1-B29 (2015) · Zbl 1330.65153
[40] H. Tiesler, R. M. Kirby, D. Xiu and T. Preusser, Stochastic collocation for optimal control problems with stochastic PDE constraints, SIAM J. Control Optim. 50 (2012), no. 5, 2659-2682.; Tiesler, H.; Kirby, R. M.; Xiu, D.; Preusser, T., Stochastic collocation for optimal control problems with stochastic PDE constraints, SIAM J. Control Optim., 50, 5, 2659-2682 (2012) · Zbl 1260.60125
[41] R. S. Tuminaro, H. F. Walker and J. N. Shadid, On backtracking failure in Newton-GMRES methods with a demonstration for the Navier-Stokes equations, J. Comput. Phys. 180 (2002), 549-558.; Tuminaro, R. S.; Walker, H. F.; Shadid, J. N., On backtracking failure in Newton-GMRES methods with a demonstration for the Navier-Stokes equations, J. Comput. Phys., 180, 549-558 (2002) · Zbl 1143.76489
[42] H. A. van der Vorst, Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 13 (1992), no. 2, 631-644.; van der Vorst, H. A., Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 13, 2, 631-644 (1992) · Zbl 0761.65023
[43] 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), no. 4, 401-424.; Verhoosel, C. V.; Gutiérrez, M. A.; Hulshoff, S. J., Iterative solution of the random eigenvalue problem with application to spectral stochastic finite element systems, Internat. J. Numer. Methods Engrg., 68, 4, 401-424 (2006) · Zbl 1127.76054
[44] D. Xiu and J. Shen, Efficient stochastic Galerkin methods for random diffusion equations, J. Comput. Phys. 228 (2009), no. 2, 266-281.; Xiu, D.; Shen, J., Efficient stochastic Galerkin methods for random diffusion equations, J. Comput. Phys., 228, 2, 266-281 (2009) · Zbl 1161.65008
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.