A multiscale method for model order reduction in PDE parameter estimation. (English) Zbl 07006455

Summary: Estimating parameters of Partial Differential Equations (PDEs) is of interest in a number of applications such as geophysical and medical imaging. Parameter estimation is commonly phrased as a PDE-constrained optimization problem that can be solved iteratively using gradient-based optimization. A computational bottleneck in such approaches is that the underlying PDEs need to be solved numerous times before the model is reconstructed with sufficient accuracy. One way to reduce this computational burden is by using Model Order Reduction (MOR) techniques such as the Multiscale Finite Volume Method (MSFV).
In this paper, we apply MSFV for solving high-dimensional parameter estimation problems. Given a finite volume discretization of the PDE on a fine mesh, the MSFV method reduces the problem size by computing a parameter-dependent projection onto a nested coarse mesh. A novelty in our work is the integration of MSFV into a PDE-constrained optimization framework, which updates the reduced space in each iteration. We present a computationally tractable way of explicitly differentiating the MOR solution that acknowledges the change of basis. As we demonstrate in our numerical experiments, our method leads to computational savings for large-scale parameter estimation problems where iterative PDE solvers are necessary and offers potential for additional speed-ups through parallel implementation.


65-XX Numerical analysis
92-XX Biology and other natural sciences
Full Text: DOI arXiv


[1] Ward, S.; Hohmann, G., Electromagnetic theory for geophysical applications, Electromagn. Methods Appl. Geophys., 1, 131-311, (1988), Soc. Expl. Geophys
[2] Parker, R. L., Geophysical Inverse Theory, (1994), Princeton University Press: Princeton University Press Princeton NJ · Zbl 0812.35159
[3] Pratt, R., Seismic waveform inversion in the frequency domain, part 1: Theory, and verification in a physical scale model, Geophysics, 64, 3, 888-901, (1999)
[4] Dey, A.; Morrison, H., Resistivity modeling for arbitrarily shaped three dimensional structures, Geophysics, 44, 4, 753-780, (1979)
[5] Epanomeritakis, I.; Akcelik, V.; Ghattas, O.; Bielak, J., A newton-cg method for large-scale three-dimensional elastic full-waveform seismic inversion, Inverse Problems, 24, 3, 034015, (2008) · Zbl 1142.65052
[6] Borzi, A.; Schulz, V., Computational Optimization of Systems Governed by Partial Differential Equations, (2011), SIAM: SIAM Philadelphia
[7] Haber, E., Computational Methods in Geophysical Electromagnetics, (2014), SIAM: SIAM Philadelphia · Zbl 1304.86001
[8] Arridge, S. R., Optical tomography in medical imaging, Inverse Problems, 15, 2, R41-R93, (1999) · Zbl 0926.35155
[9] Cheney, M.; Isaacson, D.; Newell, J. C., Electrical impedance tomography, SIAM Rev., 41, 1, 85-101, (1999) · Zbl 0927.35130
[10] Arridge, S. R.; Schotland, J. C., Optical tomography: forward and inverse problems, Inverse Problems, 25, 12, 123010-123060, (2009) · Zbl 1188.35197
[11] Lipponen, A.; Seppänen, A.; Kaipio, J., Electrical impedance tomography imaging with reduced-order model based on proper orthogonal decomposition, J. Electron. Imaging, 22, 2, 023008-023016, (2013)
[12] De Sturler, E.; Gugercin, S.; Kilmer, M. E.; Chaturantabut, S.; Beattie, C.; O’Connell, M., Nonlinear parametric inversion using interpolatory model reduction, SIAM J. Sci. Comput., 37, 3, B495-B517, (2015) · Zbl 1433.65194
[13] Kaipio, J.; Somersalo, E., (Statistical and Computational Inverse Problems. Statistical and Computational Inverse Problems, Applied Mathematical Sciences, vol. 160, (2006), Springer Science & Business Media: Springer Science & Business Media New York)
[14] Dean, O. S.; Reynolds, A. C.; Liu, N., Inverse Theory for Petroleum Reservoir Characterization and History Matching, (2008), Cambridge University Press: Cambridge University Press Cambridge
[15] Kunisch, K.; Volkwein, S., Proper orthogonal decomposition for optimality systems, ESAIM Math. Model. Numer. Anal., 42, 1, 1-23, (2008) · Zbl 1141.65050
[16] Negri, F.; Rozza, G.; Manzoni, A.; Quarteroni, A., Reduced basis method for parametrized elliptic optimal control problems, SIAM J. Sci. Comput., 35, 5, A2316-A2340, (2013) · Zbl 1280.49046
[17] Himpe, C.; Ohlberger, M., Data-driven combined state and parameter reduction for inverse problems, Adv. Comput. Math., 41, 5, 1343-1364, (2015) · Zbl 1327.37025
[18] Gallivan, K.; Vandendorpe, A.; Van Dooren, P., Model reduction of mimo systems via tangential interpolation, SIAM J. Matrix Anal. Appl., 26, 2, 328-349, (2004) · Zbl 1078.41016
[19] Grimme, E. J.; Sorensen, D. C.; Van Dooren, P., Model reduction of state space systems via an implicitly restarted Lanczos method, Numer. Algorithms, 12, 1, 1-31, (1996) · Zbl 0870.65052
[20] Calo, V. M.; Efendiev, Y.; Galvis, J.; Li, G., Randomized oversampling for generalized multiscale finite element methods, Multiscale Model. Simul., 14, 1, 482-501, (2016) · Zbl 1337.65148
[21] Ghasemi, M.; Yang, Y.; Gildin, E.; Efendiev, Y. R.; Calo, V. M., Fast multiscale reservoir simulations using pod-deim model reduction, (SPE Reservoir Simulation Symposium, (2015))
[22] Benner, P.; Gugercin, S.; Willcox, K., A survey of projection-based model reduction methods for parametric dynamical systems, SIAM Rev., 57, 4, 483-531, (2015) · Zbl 1339.37089
[23] Feng, L.; Benner, P., A robust algorithm for parametric model order reduction, PAMM, 7, 1, 1021501-1021502, (2007)
[24] Barrault, M.; Maday, Y.; Nguyen, N. C.; Patera, A. T., An ‘empirical interpolation’ method: application to efficient reduced-basis discretization of partial differential equations, C. R. Math., 339, 9, 667-672, (2004) · Zbl 1061.65118
[25] O’Connell, M.; Kilmer, M. E.; de Sturler, E., Computing reduced order models via inner-outer krylov recycling in diffuse optical tomography, SIAM J. Sci. Comput., 39, 2, B272-B297, (2017) · Zbl 1365.65242
[26] Bui-Thanh, T.; Willcox, K.; Ghattas, O., Model reduction for large-scale systems with high-dimensional parametric input space, SIAM J. Sci. Comput., 30, 6, 3270-3288, (2008) · Zbl 1196.37127
[27] Kaleta, M. P.; Hanea, R. G.; Heemink, A. W.; Jansen, J.-D., Model-reduced gradient-based history matching, Comput. Geosci., 15, 1, 135-153, (2010) · Zbl 1209.86003
[28] Galbally, D.; Fidkowski, K.; Willcox, K.; Ghattas, O., Non-linear model reduction for uncertainty quantification in large-scale inverse problems, Internat. J. Numer. Methods Engrg., 81, 1581-1608, (2009) · Zbl 1183.76837
[29] Lieberman, C.; Willcox, K.; Ghattas, O., Parameter and state model reduction for large-scale statistical inverse problems, SIAM J. Sci. Comput., 32, 5, 2523-2542, (2010) · Zbl 1217.65123
[30] Martin, J.; Wilcox, L. C.; Burstedde, C.; Ghattas, O., A stochastic newton MCMC method for large-scale statistical inverse problems with application to seismic inversion, SIAM J. Sci. Comput., 34, 3, A1460-A1487, (2012) · Zbl 1250.65011
[31] Spantini, A.; Solonen, A.; Cui, T.; Martin, J.; Tenorio, L.; Marzouk, Y., Optimal low-rank approximations of bayesian linear inverse problems, SIAM J. Sci. Comput., 37, 6, A2451-A2487, (2015) · Zbl 1325.62060
[32] Efendiev, Y.; Hou, T. Y., Multiscale Finite Element Methods: Theory and Applications, Vol. 4, (2009), Springer Science & Business Media: Springer Science & Business Media New York · Zbl 1163.65080
[33] Lee, S. H.; Zhou, H.; Tchelepi, H. A., Adaptive multiscale finite-volume method for nonlinear multiphase transport in heterogeneous formations, J. Comput. Phys., 228, 24, 9036-9058, (2009) · Zbl 1388.76179
[34] Hajibeygi, H.; Jenny, P., Adaptive iterative multiscale finite volume method, J. Comput. Phys., 230, 3, 628-643, (2011) · Zbl 1283.76041
[35] Hajibeygi, H.; Tchelepi, H. A., Compositional multiscale finite-volume formulation, SPE J., 19, 02, 316-326, (2014)
[36] Jenny, P.; Lunati, I., Modeling complex wells with the multi-scale finite-volume method, J. Comput. Phys., 228, 3, 687-702, (2009) · Zbl 1155.76040
[37] Parramore, E.; Edwards, M. G.; Pal, M.; Lamine, S., Multiscale finite-volume cvd-mpfa formulations on structured and unstructured grids, Multiscale Model. Simul., 14, 2, 559-594, (2016) · Zbl 1381.76224
[38] Jiang, L.; Efendiev, Y.; Ginting, V., Multiscale methods for parabolic equations with continuum spatial scales, Discrete Contin. Dyn. Syst. Ser. B, 8, 4, 833, (2007) · Zbl 1145.35319
[39] Chung, E. T.; Efendiev, Y.; Li, G.; Vasilyeva, M., Generalized multiscale finite element methods for problems in perforated heterogeneous domains, Appl. Anal., 95, 10, 2254-2279, (2016) · Zbl 1457.65189
[40] Chung, E. T.; Efendiev, Y.; Lee, C. S., Mixed generalized multiscale finite element methods and applications, Multiscale Model. Simul., 13, 1, 338-366, (2015) · Zbl 1317.65204
[41] Chung, E. T.; Efendiev, Y.; Gibson Jr, R. L., An energy-conserving discontinuous multiscale finite element method for the wave equation in heterogeneous media, Adv. Adapt. Data Anal., 3, 01n02, 251-268, (2011) · Zbl 1263.74048
[42] Lipnikov, K.; Morel, J.; Shashkov, M., Mimetic finite difference methods for diffusion equations on non-orthogonal non-conformal meshes, J. Comput. Phys., 199, 2, 589-597, (2004) · Zbl 1057.65071
[43] Horesh, L.; Haber, E., A second order discretization of maxwell’s equations in the quasi-static regime on OcTree grids, SIAM J. Sci. Comput., 33, 5, 2805-2822, (2011) · Zbl 1232.65019
[44] Hou, T. Y.; Wu, X. H., A multiscale finite element method for elliptic problems in composite materials and porous media, J. Comput. Phys., 134, 1, 169-189, (1997) · Zbl 0880.73065
[45] MacLachlan, S. P.; Moulton, J. D., Multilevel upscaling through variational coarsening, Water Resour. Res., 42, 2, 131-139, (2006)
[46] Kalchev, D. Z.; Lee, C. S.; Villa, U.; Efendiev, Y., Upscaling of mixed finite element discretization problems by the spectral AMGe method, SIAM J. Sci. Comput., 38, 5, A2912-A2933, (2016) · Zbl 1348.65165
[47] Møyner, O.; Lie, K.-A., A multiscale restriction-smoothed basis method for high contrast porous media represented on unstructured grids, J. Comput. Phys., 304, 46-71, (2016) · Zbl 1349.76824
[48] de Moraes, R. J.; Rodrigues, J. R.; Hajibeygi, H.; Jansen, J. D., Multiscale gradient computation for flow in heterogeneous porous media, J. Comput. Phys., 336, 644-663, (2017) · Zbl 1375.76191
[49] Durlofsky, L.; Efendiev, Y.; Ginting, V., An adaptive local-global multiscale finite volume element method for two-phase flow simulations, Adv. Water Resour., 30, 3, 576-588, (2007)
[50] Lunati, I.; Jenny, P., Multiscale finite-volume method for density-driven flow in porous media, Comput. Geosci., 12, 3, 337-350, (2008) · Zbl 1259.76051
[51] Jenny, P.; Lee, S. H.; Tchelepi, H. A., Adaptive multiscale finite-volume method for multiphase flow and transport in porous media, Multiscale Model. Simul., 3, 1, 50-64, (2005) · Zbl 1160.76372
[52] Jenny, P.; Lee, S.; Tchelepi, H. A., Multi-scale finite-volume method for elliptic problems in subsurface flow simulation, J. Comput. Phys., 187, 1, 47-67, (2003) · Zbl 1047.76538
[53] Haber, E.; Ruthotto, L., A multiscale finite volume method for Maxwell’s equations at low frequencies, Geophys. J. Int., 199, 2, 1268-1277, (2014)
[54] Ruthotto, L.; Treister, E.; Haber, E., jinv-a flexible julia package for pde parameter estimation, SIAM J. Sci. Comput., 39, 5, S702-S722, (2017) · Zbl 1373.86013
[55] Krogstad, S.; Hauge, V. L.; Gulbransen, A., Adjoint multiscale mixed finite elements, SPE J., 16, 01, 162-171, (2011)
[56] Fu, J.; Tchelepi, H. A.; Caers, J., A multiscale adjoint method to compute sensitivity coefficients for flow in heterogeneous porous media, Adv. Water Resour., 33, 6, 698-709, (2010)
[57] Fu, J.; Caers, J.; Tchelepi, H. A., A multiscale method for subsurface inverse modeling: Single-phase transient flow, Adv. Water Resour., 34, 8, 967-979, (2011)
[58] McGillivray, P. R., Forward Modeling and Inversion of DC Resistivity and MMR Data, (1992), University of British Columbia, (Ph.D. thesis)
[59] Gamkrelidze, R., Principles of Optimal Control Theory, Vol. 7, (2013), Springer Science & Business Media: Springer Science & Business Media New York
[60] Sargent, R., Optimal control, J. Comput. Appl. Math., 124, 1, 361-371, (2000) · Zbl 0970.49003
[61] Haber, E., Solving csem problems with massive number of sources and receivers, (78th EAGE Conference and Exhibition 2016, (2016))
[62] van Leeuwen, T.; Herrmann, F. J., A penalty method for pde-constrained optimization in inverse problems, Inverse Problems, 32, 1, 015007, (2015) · Zbl 1410.49029
[63] Bai, Z.; Dewilde, P. M.; Freund, R. W., Reduced-order modeling, Handb. Numer. Anal., 13, 825-895, (2005) · Zbl 1180.78032
[64] Chung, E.; Efendiev, Y.; Hou, T. Y., Adaptive multiscale model reduction with generalized multiscale finite element methods, J. Comput. Phys., 320, 69-95, (2016) · Zbl 1349.76191
[65] Benner, P.; Sachs, E.; Volkwein, S., Model order reduction for pde constrained optimization, (Trends in PDE Constrained Optimization, (2014), Springer), 303-326 · Zbl 1327.49043
[66] Haber, E.; Holtham, E.; Granek, J.; Marchant, D.; Oldenburg, D.; Schwarzbach, C.; Shekhtman, R., An adaptive mesh method for electromagnetic inverse problems, (SEG Technical Program Expanded Abstracts 2012, (2012), Society of Exploration Geophysicists), 1-6
[67] Lohmann, B.; Eid, R., Efficient order reduction of parametric and nonlinear models by superposition of locally reduced models, Methoden Anwendungen Regel.tech., (2007)
[68] Panzer, H.; Mohring, J.; Eid, R.; Lohmann, B., Parametric model order reduction by matrix interpolation, at - Automatisierungstechnik, 58, 8, (2010)
[69] Amsallem, D.; Farhat, C., An online method for interpolating linear parametric reduced-order models, SIAM J. Sci. Comput., 33, 5, 2169-2198, (2011) · Zbl 1269.65059
[70] Baur, U.; Beattie, C.; Benner, P.; Gugercin, S., Interpolatory projection methods for parameterized model reduction, SIAM J. Sci. Comput., 33, 5, 2489-2518, (2011) · Zbl 1254.93032
[71] Haasdonk, B.; Ohlberger, M., Reduced basis method for finite volume approximations of parametrized linear evolution equations, ESAIM Math. Model. Numer. Anal., 42, 02, 277-302, (2008) · Zbl 1388.76177
[72] Willcox, K.; Peraire, J., Balanced model reduction via the proper orthogonal decomposition, AIAA J., 40, 11, 2323-2330, (2002)
[73] Elman, H. C.; Liao, Q., Reduced basis collocation methods for partial differential equations with random coefficients, SIAM/ASA J. Uncertain. Quant., 1, 1, 192-217, (2013) · Zbl 1282.35424
[74] Hou, T.; Wu, X.-H.; Cai, Z., Convergence of a multiscale finite element method for elliptic problems with rapidly oscillating coefficients, Math. Comput. Amer. Math. Soc., 68, 227, 913-943, (1999) · Zbl 0922.65071
[75] Efendiev, Y. R.; Hou, T. Y.; Wu, X.-H., Convergence of a nonconforming multiscale finite element method, SIAM J. Numer. Anal., 37, 3, 888-910, (2000) · Zbl 0951.65105
[76] Chung, E. T.; Du, Q.; Zou, J., Convergence analysis of a finite volume method for maxwell’s equations in nonhomogeneous media, SIAM J. Numer. Anal., 41, 1, 37-63, (2003) · Zbl 1067.78018
[77] Aminzadeh, F.; Jean, B.; Kunz, T., 3-D Salt and Overthrust Models, (1997), Society of Exploration Geophysicists
[78] Bezanson, J.; Edelman, A.; Karpinski, S.; Shah, V. B., Julia: A fresh approach to numerical computing, SIAM Rev., 59, 1, 65-98, (2017) · Zbl 1356.68030
[79] Amestoy, P. R.; Duff, I. S.; LExcellent, J.-Y.; Koster, J., Mumps: a general purpose distributed memory sparse solver, (International Workshop on Applied Parallel Computing, (2000), Springer), 121-130
[80] O’Leary, D. P., The block conjugate gradient algorithm and related methods, Linear Algebra Appl., 29, 293-322, (1980) · Zbl 0426.65011
[81] L. Ruthotto, KrylovMethods.jl. https://github.com/lruthotto/KrylovMethods.jl.
[82] Dongarra, J. J.; Du Croz, J.; Hammarling, S.; Duff, I. S., A set of level 3 basic linear algebra subprograms, ACM Trans. Math. Softw. (TOMS), 16, 1, 1-17, (1990) · Zbl 0900.65115
[83] Saad, Y., Iterative Methods for Sparse Linear Systems, (2003), SIAM: SIAM Philadelphia · Zbl 1002.65042
[84] Ayachit, U., The Paraview Guide: A Parallel Visualization Application, (2015), Kitware, Inc.
[85] Caudillo-Mata, L. A.; Haber, E.; Heagy, L. J.; Schwarzbach, C., A framework for the upscaling of the electrical conductivity in the quasi-static maxwells equations, J. Comput. Appl. Math., 317, 388-402, (2017) · Zbl 1358.78086
[86] Wilhelms, W.; Schwarzbach, C.; Börner, R.-U.; Spitzer, K., A fast 3d mt inversion-the forward operator behind, J. Future Gener. Comput. Syst., 20, 3, 475-487, (2018)
[87] Caudillo Mata, L.; Haber, E.; Schwarzbach, C., An oversampling technique for multiscale finite volume method to simulate frequency-domain electromagnetic responses, (SEG Technical Program Expanded Abstracts 2016, (2016), Society of Exploration Geophysicists), 981-985
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.