Multilevel Monte Carlo methods for stochastic convection-diffusion eigenvalue problems. (English) Zbl 07845619
Summary: We develop new multilevel Monte Carlo (MLMC) methods to estimate the expectation of the smallest eigenvalue of a stochastic convection-diffusion operator with random coefficients. The MLMC method is based on a sequence of finite element (FE) discretizations of the eigenvalue problem on a hierarchy of increasingly finer meshes. For the discretized, algebraic eigenproblems we use both the Rayleigh quotient (RQ) iteration and implicitly restarted Arnoldi (IRA), providing an analysis of the cost in each case. By studying the variance on each level and adapting classical FE error bounds to the stochastic setting, we are able to bound the total error of our MLMC estimator and provide a complexity analysis. As expected, the complexity bound for our MLMC estimator is superior to plain Monte Carlo. To improve the efficiency of the MLMC further, we exploit the hierarchy of meshes and use coarser approximations as starting values for the eigensolvers on finer ones. To improve the stability of the MLMC method for convection-dominated problems, we employ two additional strategies. First, we consider the streamline upwind Petrov-Galerkin formulation of the discrete eigenvalue problem, which allows us to start the MLMC method on coarser meshes than is possible with standard FEs. Second, we apply a homotopy method to add stability to the eigensolver for each sample. Finally, we present a multilevel quasi-Monte Carlo method that replaces Monte Carlo with a quasi-Monte Carlo (QMC) rule on each level. Due to the faster convergence of QMC, this improves the overall complexity. We provide detailed numerical results comparing our different strategies to demonstrate the practical feasibility of the MLMC method in different use cases. The results support our complexity analysis and further demonstrate the superiority over plain Monte Carlo in all cases.
MSC:
| 65N25 | Numerical methods for eigenvalue problems for boundary value problems involving PDEs |
| 65C05 | Monte Carlo methods |
| 65N30 | Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs |
| 65N50 | Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs |
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 65N15 | Error bounds for boundary value problems involving PDEs |
| 65N99 | Numerical methods for partial differential equations, boundary value problems |
| 35R60 | PDEs with randomness, stochastic partial differential equations |
Keywords:
convection-diffusion eigenvalue problems; multilevel Monte Carlo; uncertainty quantification; homotopyReferences:
| [1] | Arnoldi, WE, The principle of minimized iterations in the solution of the matrix eigenvalue problem, Q. Appl. Math., 9, 17-29, 1951 · Zbl 0042.12801 · doi:10.1090/qam/42792 |
| [2] | Avramova, MN; Ivanov, KN, Verification, validation and uncertainty quantification in multi-physics modeling for nuclear reactor design and safety analysis, Prog. Nucl. Energy, 52, 601-614, 2010 · doi:10.1016/j.pnucene.2010.03.009 |
| [3] | Ayres, DAF; Eaton, MD; Hagues, AW; Williams, MMR, Uncertainty quantification in neutron transport with generalized polynomial chaos using the method of characteristics, Ann. Nucl. Energy, 45, 14-28, 2012 · doi:10.1016/j.anucene.2012.02.008 |
| [4] | Babuška, I.; Osborn, J.; Ciarlet, PG; Lions, JL, Eigenvalue problems, Handbook of Numerical Analysis, Finite Element Methods (Part 1), 641-787, 1991, Amsterdam: Elsevier, Amsterdam · Zbl 0875.65087 · doi:10.1016/S1570-8659(05)80042-0 |
| [5] | Barrenechea, G.; Valentin, F., An unusual stabilized finite element method for a generalized stokes problem, Numer. Math., 92, 653-677, 2002 · Zbl 1019.65087 · doi:10.1007/s002110100371 |
| [6] | Barth, A.; Schwab, C.; Zollinger, N., Multi-level Monte Carlo finite element method for elliptic PDEs with stochastic coefficients, Numer. Math., 119, 123-161, 2011 · Zbl 1230.65006 · doi:10.1007/s00211-011-0377-0 |
| [7] | Beck, A.; Dürrwächter, J.; Kuhn, T.; Meyer, F.; Munz, C-D; Rohde, C., \(hp\)-Multilevel Monte Carlo methods for uncertainty quantification of compressible Navier-Stokes equations, SIAM J. Sci. Comput., 42, 4, B1067-B1091, 2020 · Zbl 1486.65002 · doi:10.1137/18M1210575 |
| [8] | Bochev, PB; Gunzburger, MD; Shadid, JN, Stability of the SUPG finite element method for transient advection-diffusion problems, Comput. Methods Appl. Mech. Eng., 193, 23, 2301-2323, 2004 · Zbl 1067.76563 · doi:10.1016/j.cma.2004.01.026 |
| [9] | Broersen, R.; Stevenson, R., A robust Petrov-Galerkin discretisation of convection-diffusion equations, Comput. Math. Appl., 68, 11, 1605-1618, 2014 · Zbl 1364.65191 · doi:10.1016/j.camwa.2014.06.019 |
| [10] | Brooks, AN; Hughes, TJR, Streamline upwind/Petrov-Galerkin formulations for convection dominated flows with particular emphasis on the incompressible Navier-Stokes equations, Comput. Methods Appl. Mech. Eng., 32, 199-259, 1982 · Zbl 0497.76041 · doi:10.1016/0045-7825(82)90071-8 |
| [11] | Cai, Z.; Mandel, J.; McCormick, S., Multigrid methods for nearly singular linear equations and eigenvalue problems, SIAM J. Numer. Anal., 34, 1, 178-200, 1997 · Zbl 0873.65030 · doi:10.1137/S1064827594261139 |
| [12] | Carnoy, EG; Geradin, M.; Kågström, B.; Ruhe, A., On the practical use of the Lanczos algorithm in finite element applications to vibration and bifurcation problems, Matrix Pencils, 156-176, 1983, Berlin: Springer, Berlin · Zbl 0497.73078 · doi:10.1007/BFb0062100 |
| [13] | Carstensen, C.; Gedicke, J.; Mehrmann, V.; Miedlar, A., An adaptive homotopy approach for non-self-adjoint eigenvalue problems, Numer. Math., 119, 557-583, 11, 2011 · Zbl 1263.65106 · doi:10.1007/s00211-011-0388-x |
| [14] | Cliffe, KA; Giles, MB; Scheichl, R.; Teckentrup, AL, Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients, Comput. Vis. Sci., 14, 3-15, 2011 · Zbl 1241.65012 · doi:10.1007/s00791-011-0160-x |
| [15] | Cohen, A.; Dahmen, W.; Welper, G., Adaptivity and variational stabilization for convection-diffusion equations, Eur. Ser. Appl. Ind. Math. Math. Model. Numer. Anal., 46, 1247-1273, 2012 · Zbl 1270.65065 · doi:10.1051/m2an/2012003 |
| [16] | Cools, R.; Kuo, FY; Nuyens, D., Constructing embedded lattice rules for multivariate integration, SIAM J. Sci. Comput., 28, 2162-2188, 2006 · Zbl 1126.65002 · doi:10.1137/06065074X |
| [17] | Crandall, SH, Iterative procedures related to relaxation methods for eigenvalue problems, Proc. R. Soc. A Math. Phys. Eng. Sci., 207, 416-423, 1951 · Zbl 0042.36401 |
| [18] | Davis, TA, Direct Methods for Sparse Linear Systems, 2006, Philadelphia: SIAM, Philadelphia · Zbl 1119.65021 · doi:10.1137/1.9780898718881 |
| [19] | Dick, J.; Gantner, RN; Le Gia, QT; Schwab, C., Higher order Quasi-Monte Carlo integration for Bayesian PDE inversion, Comput. Math. Appl., 77, 144-172, 2019 · Zbl 1442.62051 · doi:10.1016/j.camwa.2018.09.019 |
| [20] | Dick, J.; Kuo, FY; Sloan, IH, High dimensional integration: the quasi-Monte Carlo way, Acta Numer., 22, 133-288, 2013 · Zbl 1296.65004 · doi:10.1017/S0962492913000044 |
| [21] | Dick, J.; Pillichshammer, F., Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration, 2010, New York: Cambridge University Press, New York · Zbl 1282.65012 · doi:10.1017/CBO9780511761188 |
| [22] | Dobson, D.; Gopalakrishnan, J.; Pasciak, J., An efficient method for band structure calculations in 3d photonic crystals, J. Comput. Phys., 161, 668-679, 2000 · Zbl 1034.78013 · doi:10.1006/jcph.2000.6521 |
| [23] | Donea, J.; Huerta, A., Finite Element Methods for Flow Problems, 2003, New York: Wiley, New York · doi:10.1002/0470013826 |
| [24] | Drummond, IT; Duane, S.; Horgan, RR, Scalar diffusion in simulated helical turbulence with molecular diffusivity, J. Fluid Mech., 138, 75-91, 1984 · Zbl 0536.76084 · doi:10.1017/S0022112084000045 |
| [25] | Duderstadt, JJ; Hamilton, LJ, Nuclear Reactor Analysis, 1976, New York: Wiley, New York |
| [26] | George, A.; Ng, E., On the complexity of sparse QR & LU factorization of finite-element matrices, SIAM J. Sci. Stat. Comput., 9, 5, 849-861, 1988 · Zbl 0658.65023 · doi:10.1137/0909057 |
| [27] | Giani, S.; Graham, IG, Adaptive finite element methods for computing band gaps in photonic crystals, Numer. Math., 121, 31-64, 2012 · Zbl 1241.82077 · doi:10.1007/s00211-011-0425-9 |
| [28] | Gilbert, A.D., Scheichl, R.: Multilevel quasi-Monte Carlo for random elliptic eigenvalue problems I: regularity and error analysis. IMA J. Numer. Anal. (to appear) (2023) |
| [29] | Gilbert, A.D., Scheichl, R.: Multilevel quasi-Monte Carlo for random elliptic eigenvalue problems II: efficient algorithms and numerical results. IMA J. Numer. Anal. (to appear) (2023) |
| [30] | Giles, MB, Multilevel Monte Carlo path simulation, Oper. Res., 56, 3, 607-617, 2008 · Zbl 1167.65316 · doi:10.1287/opre.1070.0496 |
| [31] | Giles, MB, Multilevel Monte Carlo methods, Acta Numer., 24, 259-328, 2015 · Zbl 1316.65010 · doi:10.1017/S096249291500001X |
| [32] | Giles, M.B., Waterhouse, B.: Multilevel quasi-Monte Carlo path simulation. In: Advanced Financial Modelling. Radon Series on Computational and Applied Mathematics, pp. 165-181. De Gruyter, New York (2009) · Zbl 1181.91335 |
| [33] | Grisvard, P., Elliptic Problems in Nonsmooth Domains, 2011, Philadelphia: SIAM, Philadelphia · Zbl 1231.35002 · doi:10.1137/1.9781611972030 |
| [34] | Guennebaud, G., Jacob, B. et al.: Eigen v3. http://eigen.tuxfamily.org (2010) |
| [35] | Hauke, G., A simple subgrid scale stabilized method for the advection-diffusion-reaction equation, Comput. Methods Appl. Mech. Eng., 191, 2925-2947, 2002 · Zbl 1005.76057 · doi:10.1016/S0045-7825(02)00217-7 |
| [36] | Heinrich, S.; Margenov, S., Multilevel Monte Carlo methods, Large-Scale Scientific Computing, 58-67, 2001, Berlin: Springer, Berlin · Zbl 1031.65005 · doi:10.1007/3-540-45346-6_5 |
| [37] | Higdon, D.; Anderson, CW, Space and space-time modeling using process convolutions, Quantitative Methods for Current Environmental Issues, 37-56, 2002, London: Springer, London · Zbl 1255.86016 · doi:10.1007/978-1-4471-0657-9_2 |
| [38] | Hughes, TJR; Franca, LP; Hulbert, GM, A new finite element formulation for computational fluid dynamics: VIII. The Galerkin/least-squares method for advective-diffusive equations, Comput. Methods Appl. Mech. Eng., 73, 2, 173-189, 1989 · Zbl 0697.76100 · doi:10.1016/0045-7825(89)90111-4 |
| [39] | Hughes, TJR; Mallet, M., A new finite element formulation for computational fluid dynamics: III. The generalized streamline operator for multidimensional advective-diffusive systems, Comput. Methods Appl. Mech. Eng., 58, 3, 305-328, 1986 · Zbl 0622.76075 · doi:10.1016/0045-7825(86)90152-0 |
| [40] | Hughes, TJR; Tezduyar, TE, Finite element methods for first-order hyperbolic systems with particular emphasis on the compressible Euler equations, Comput. Methods Appl. Mech. Eng., 45, 1, 217-284, 1984 · Zbl 0542.76093 · doi:10.1016/0045-7825(84)90157-9 |
| [41] | Kana, A.A.: Enabling Decision Insight by Applying Monte Carlo Simulations and Eigenvalue Spectral Analysis to the Ship-Centric Markov Decision Process Framework. Ph.D thesis, Univeristy of Michigan, Ann Arbor, Michigan (2016) |
| [42] | Kato, T., Perturbation Theory for Linear Operators, 1984, Berlin: Springer, Berlin · Zbl 0531.47014 |
| [43] | Knobloch, P., On the definition of the SUPG parameter, Electron. Trans. Numer. Anal., 32, 76-89, 2008 · Zbl 1171.65079 |
| [44] | Kraichnan, RH, Diffusion by a random velocity field, Phys. Fluids, 13, 1, 22-31, 1970 · Zbl 0193.27106 · doi:10.1063/1.1692799 |
| [45] | Kuo, FY; Nuyens, D., Application of quasi-Monte Carlo methods to elliptic PDEs with random diffusion coefficients: a survey of analysis and implementation, Found. Comput. Math., 16, 6, 1631-1696, 2016 · Zbl 1362.65015 · doi:10.1007/s10208-016-9329-5 |
| [46] | Kuo, FY; Scheichl, R.; Schwab, C.; Sloan, IH; Ullmann, E., Multilevel quasi-Monte Carlo methods for lognormal diffusion problems, Math. Comp., 86, 2827-2860, 2017 · Zbl 1368.65005 · doi:10.1090/mcom/3207 |
| [47] | Kuo, FY; Schwab, C.; Sloan, IH, Multi-level quasi-Monte Carlo finite element methods for a class of elliptic PDEs with random coefficients, Found. Comput. Math., 15, 411-449, 2015 · Zbl 1318.65006 · doi:10.1007/s10208-014-9237-5 |
| [48] | Lehoucq, R.B.: Analysis and implementation of an implicitly restarted Arnoldi iteration. Ph.D Thesis, Rice University, Houston, Texas (1995) |
| [49] | Lehoucq, RB; Sorensen, DC; Yang, C., ARPACK Users’ Guide, 1998, Philadelphia: SIAM, Philadelphia · Zbl 0901.65021 · doi:10.1137/1.9780898719628 |
| [50] | Lui, SH; Keller, HB; Kwok, TWC, Homotopy method for the large, sparse, real non-symmetric eigenvalue problem, SIAM J. Matrix Anal. Appl., 18, 2, 312-333, 1997 · Zbl 0872.65035 · doi:10.1137/S0895479894273900 |
| [51] | McGrail, BP; Ahmed, S.; Schaef, HT; Owen, AT; Martin, PF; Zhu, T., Gas hydrate property measurements in porous sediments with resonant ultrasonic spectroscopy, J. Geophys. Res. Solid Earth, 112, 1, 2007 · doi:10.1029/2005JB004084 |
| [52] | Migliori, A.: Resonant ultrasound spectroscopy. Technical Report, Los Alamos National Lab, Los Alamos, NM, USA (2016) |
| [53] | Mishra, S.; Schwab, C.; Sukys, J., Multi-level Monte Carlo finite volume methods for nonlinear systems of conservation laws in multi-dimensions, J. Comput. Phys., 231, 8, 3365-3388, 2012 · Zbl 1402.76083 · doi:10.1016/j.jcp.2012.01.011 |
| [54] | Morton, KW, Numerical Solution of Convection-Diffusion Problems, 1996, Boca Raton: CRC Press, Boca Raton · Zbl 0861.65070 |
| [55] | Norton, RA; Scheichl, R., Plane wave expansion methods for photonic crystal fibres, Appl. Numer. Math., 63, 88-104, 2013 · Zbl 1269.82009 · doi:10.1016/j.apnum.2012.09.008 |
| [56] | Ostrowski, AM, On the convergence of the Rayleigh quotient iteration for the computation of the characteristic roots and vectors. I, Arch. Ration. Mech. Anal., 1, 1, 233-241, 1957 · Zbl 0083.12002 · doi:10.1007/BF00298007 |
| [57] | Rayleigh, JWSB, The Theory of Sound, 1894, New York: Macmillan, New York · JFM 25.1604.01 |
| [58] | Saad, Y., Variations on Arnoldi’s method for computing eigen elements of large unsymmetric matrices, Linear Algebra Appl., 34, C, 269-295, 1980 · Zbl 0456.65017 · doi:10.1016/0024-3795(80)90169-X |
| [59] | Saad, Y., Chebyshev acceleration techniques for solving nonsymmetric eigenvalue problems, Math. Comput., 42, 567-588, 1984 · Zbl 0539.65013 · doi:10.1090/S0025-5718-1984-0736453-8 |
| [60] | Scheichl, R.; Stuart, AM; Teckentrup, AL, Quasi-Monte Carlo and multilevel Monte Carlo methods for computing posterior expectations in elliptic inverse problems, SIAM/ASA J. Uncertain. Quantif., 5, 1, 493-518, 2017 · Zbl 1516.65118 · doi:10.1137/16M1061692 |
| [61] | Schwartz, RB; Vuorinen, JF, Resonant ultrasound spectroscopy: applications, current status and limitations, J. Alloy. Compd., 310, 243-250, 2000 · doi:10.1016/S0925-8388(00)00925-7 |
| [62] | Scott, JA, An Arnoldi code for computing selected eigenvalues of sparse, real, unsymmetric matrices, ACM Trans. Math. Softw., 21, 432-475, 1995 · Zbl 0888.65041 · doi:10.1145/212066.212091 |
| [63] | Stynes, M., Steady-state convection-diffusion problems, Acta Numer., 14, 445-508, 2005 · Zbl 1115.65108 · doi:10.1017/S0962492904000261 |
| [64] | Tartakovsky, DM; Broyda, S., PDF equations for advective-reactive transport in heterogeneous porous media with uncertain properties, J. Contam. Hydrol., 120-121, 129-140, 2011 · doi:10.1016/j.jconhyd.2010.08.009 |
| [65] | Teckentrup, AL; Scheichl, R.; Giles, MB; Ullmann, E., Further analysis of multilevel Monte Carlo methods for elliptic PDEs with random coefficients, Numer. Math., 125, 569-600, 2012 · Zbl 1306.65009 · doi:10.1007/s00211-013-0546-4 |
| [66] | Thomson, W.T.: The Theory of Vibrations with Applications. Prentice-Hall (1981) · Zbl 0498.70001 |
| [67] | Zhang, D., Stochastic Methods for Flow in Porous Media: Coping With Uncertainties, 2002, New York: Academic Press, New York |
| [68] | Zienkiewicz, OC; Taylor, RL, Finite Element Method: Fluid Dynamics, 2000, Oxford: Butterworth-Heinemann, Oxford · Zbl 0991.74004 |
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.
