×

zbMATH — the first resource for mathematics

Hierarchical matrix approximations of Hessians arising in inverse problems governed by PDEs. (English) Zbl 1453.65289
The authors analyze the role of Hessians in deterministic or Bayesian inverse problems governed by partial differential equations. When discretizing over a \(d\)-dimensional domain \(\Omega\), an inverse problem governed by a partial differential equation with distributed parameter fields to be inferred from data, an optimization problem of the form \(minimize_{m}\) \(J(m)=F(u(m))+\alpha R(m)\) is obtained, where the state variables \(u(m)\in \mathbb{R}^{N}\) depend on the model parameters \(m\in\mathbb{R}^{n}\) via the solution of the discretized partial differential equations \(g(m,u)=K(m)u-f=0\), with coefficient matrix \(K\in \mathbb{R}^{N\times N}\) and source \(f\in \mathbb{R}^{N}\). The data misfit term \(F(u(m))\) measures the difference between recorded observations and the response of the model at receivers placed on the boundary or the interior of \(\Omega \). The authors introduce the partial derivative \(G=\partial _{m}g=\partial _{m}K\times _{2}u\), where \(\partial _{m}K\) is a third-order tensor of size \(N\times N\times n\) and \(\times _{2}\) is a 2-mode tensor vector product operation. They observe that, unlike the local sparse matrices \(K\) and \(G\), the inverse operator \(K^{-1}\) is a discretized, nonlocal solution operator and is in general formally dense. They compute the gradient of the data misfit term of the objective function as \(\nabla _{m}F=(\partial _{m}K\times _{2}u)^{T}p=-G^{T}K^{-T}\partial _{u}F\), where \(p\in \mathbb{R}^{N}\) is an adjoint variable defined via the adjoint equations \(l(m,p)=K^{T}(m)p+ \partial _{u}F=0\). The authors then compute the Hessian \(\nabla_{mm}^{2}F=G^{T}K^{-T}\partial_{uu}^{2}FK^{-1}G-G^{T}K^{-T}L-L^{T}K^{-1}G+(\partial _{mm}^{2}K\times _{2}u)\times _{1}p\), with \(L=\partial _{m}l=\partial _{m}K^{T}\times _{2}p\). They start proving that Hessian matrices can be approximated with low-rank hierarchical matrices. They show how to draw fast operations on hierarchical matrices and how to construct the hierarchical Hessians ab initio. The main part of the paper presents four situations: density inversion in a one-dimensional time-dependent diffusion equation, source inversion in stationary advection diffusion, frequency-domain wave equation inversion, and transient controlled-source electromagnetic inversion. In each case, the authors write the functional to be minimized, the associated partial differential equation, the misfit functional to be considered, and they draw the associated computations. In each case, the authors present the results of numerical simulations.

MSC:
65M32 Numerical methods for inverse problems for initial value and initial-boundary value problems involving PDEs
35Q93 PDEs in connection with control and optimization
49M25 Discrete approximations in optimal control
49N45 Inverse problems in optimal control
65F10 Iterative numerical methods for linear systems
65F99 Numerical linear algebra
65Y05 Parallel numerical computation
65Y10 Numerical algorithms for specific classes of architectures
78A46 Inverse problems (including inverse scattering) in optics and electromagnetic theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A. Alexanderian, P. J. Gloor, and O. Ghattas, On Bayesian A-and D-optimal experimental designs in infinite dimensions, Bayesian Anal., 11 (2016), pp. 671-695, https://doi.org/10.1214/15-BA969. · Zbl 1359.62315
[2] N. Alger, Data-Scalable Hessian Preconditioning for Distributed Parameter PDE-Constrained Inverse Problems, Ph.D. thesis, The University of Texas at Austin, Austin, TX, 2019.
[3] N. Alger, V. Rao, A. Meyers, T. Bui-Thanh, and O. Ghattas, Scalable matrix-free adaptive product-convolution approximation for locally translation-invariant operators, SIAM J. Sci. Comput., 41 (2019), pp. A2296-A2328, https://doi.org/10.1137/18M1189324. · Zbl 07099346
[4] N. Alger, U. Villa, T. Bui-Thanh, and O. Ghattas, A data scalable augmented Lagrangian KKT preconditioner for large-scale inverse problems, SIAM J. Sci. Comput., 39 (2017), pp. A2365-A2393, https://doi.org/10.1137/16M1084365. · Zbl 1422.65090
[5] S. Ambikasaran and E. Darve, An \(\mathcal{O}(N \log N)\) fast direct solver for partial hierarchically semi-separable matrices, J. Sci. Comput., 57 (2013), pp. 477-501. · Zbl 1292.65030
[6] R. Anderson, J. Andrej, A. Barker, J. Bramwell, J.-S. Camier, J. Cerveny, V. Dobrev, Y. Dudouit, A. Fisher, T. Kolev, W. Pazner, M. Stowell, V. Tomov, I. Akkerman, J. Dahm, D. Medina, and S. Zampini, MFEM: A modular finite element methods library, Comput. Math. Appl., (2020), https://doi.org/10.1016/j.camwa.2020.06.009.
[7] D. N. Arnold, F. Brezzi, B. Cockburn, and L. D. Marini, Unified analysis of discontinuous Galerkin methods for elliptic problems, SIAM J. Numer. Anal., 39 (2002), pp. 1749-1779, https://doi.org/10.1137/S0036142901384162. · Zbl 1008.65080
[8] B. Ayuso and L. D. Marini, Discontinuous Galerkin methods for advection-diffusion-reaction problems, SIAM J. Numer. Anal., 47 (2009), pp. 1391-1420, https://doi.org/10.1137/080719583. · Zbl 1205.65308
[9] S. Balay, S. Abhyankar, M. Adams, J. Brown, P. Brune, K. Buschelman, L. Dalcin, A. Dener, V. Eijkhout, W. Gropp, D. Karpeyev, D. Kaushik, M. Knepley, D. May, L. C. McInnes, R. Mills, T. Munson, K. Rupp, P. Sanan, B.Smith, S. Zampini, H. Zhang, and H. Zhang, PETSc Users Manual: Revision 3.10, tech. report, Argonne National Laboratory (ANL), Argonne, IL, 2018.
[10] O. Bashir, K. Willcox, O. Ghattas, B. van Bloemen Waanders, and J. Hill, Hessian-based model reduction for large-scale systems with initial condition inputs, Internat. J. Numer. Methods Engrg., 73 (2008), pp. 844-868. · Zbl 1195.76311
[11] M. Bebendorf, Low-rank approximation of elliptic boundary value problems with high-contrast coefficients, SIAM J. Math. Anal., 48 (2016), pp. 932-949, https://doi.org/10.1137/140991030. · Zbl 1335.35030
[12] M. Bebendorf and W. Hackbusch, Existence of \(\mathcal{H} \)-matrix approximants to the inverse FE-matrix of elliptic operators with \(L^\infty \)-coefficients, Numer. Math., 95 (2003), pp. 1-28. · Zbl 1033.65100
[13] J.-P. Berenger, A perfectly matched layer for the absorption of electromagnetic waves, J. Comput. Phys., 114 (1994), pp. 185-200. · Zbl 0814.65129
[14] A. Beskos, M. Girolami, S. Lan, P. E. Farrell, and A. M. Stuart, Geometric MCMC for infinite-dimensional inverse problems, J. Comput. Phys., 335 (2017), pp. 327-351. · Zbl 1375.35627
[15] S. Börm, Data-sparse approximation of non-local operators by \(\mathcal{H}^2\)-matrices, Linear Algebra Appl., 422 (2007), pp. 380-403. · Zbl 1115.65041
[16] S. Börm, Approximation of solution operators of elliptic partial differential equations by \(\mathcal{H} \)- and \(\mathcal{H}^2\)-matrices, Numer. Math., 115 (2010), pp. 165-193. · Zbl 1191.65148
[17] S. Börm, Directional \(\mathcal{H}^2\)-matrix compression for high-frequency problems, Numer. Linear Algebra Appl., 24 (2017), e2112. · Zbl 06819613
[18] A. Borz\`\i and V. Schulz, Computational Optimization of Systems Governed by Partial Differential Equations, SIAM, Philadelphia, 2012.
[19] W. Boukaram, G. Turkiyyah, and D. Keyes, Hierarchical matrix operations on GPUs: Matrix-vector multiplication and compression, ACM Trans. Math. Software, 45 (2019), 3. · Zbl 07119122
[20] W. Boukaram, G. Turkiyyah, and D. Keyes, Randomized GPU algorithms for the construction of hierarchical matrices from matrix-vector operations, SIAM J. Sci. Comput., 41 (2019), pp. C339-C366, https://doi.org/10.1137/18M1210101. · Zbl 07099326
[21] T. Bui-Thanh, C. Burstedde, O. Ghattas, J. Martin, G. Stadler, and L. C. Wilcox, Extreme-scale UQ for Bayesian inverse problems governed by PDEs, in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC’12), 2012.
[22] T. Bui-Thanh and O. Ghattas, Analysis of the Hessian for inverse scattering problems. Part I: Inverse shape scattering of acoustic waves, Inverse Problems, 28 (2012), 055001, https://doi.org/10.1088/0266-5611/28/5/055001. · Zbl 1239.78006
[23] T. Bui-Thanh and O. Ghattas, Analysis of the Hessian for inverse scattering problems. Part II: Inverse medium scattering of acoustic waves, Inverse Problems, 28 (2012), 055002, https://doi.org/10.1088/0266-5611/28/5/055002. · Zbl 1239.78006
[24] T. Bui-Thanh and O. Ghattas, Analysis of the Hessian for inverse scattering problems. Part III: Inverse medium scattering of electromagnetic waves, Inverse Probl. Imaging, 7 (2013), pp. 1139-1155. · Zbl 1292.78012
[25] T. Bui-Thanh, O. Ghattas, J. Martin, and G. Stadler, A computational framework for infinite-dimensional Bayesian inverse problems Part I: The linearized case, with application to global seismic inversion, SIAM J. Sci. Comput., 35 (2013), pp. A2494-A2523, https://doi.org/10.1137/12089586X. · Zbl 1287.35087
[26] T. Bui-Thanh and M. A. Girolami, Solving large-scale PDE-constrained Bayesian inverse problems with Riemann manifold Hamiltonian Monte Carlo, Inverse Problems, 30 (2014), 114014. · Zbl 1306.65269
[27] J. M. Carcione, Simulation of electromagnetic diffusion in anisotropic media, Prog. Electromagn. Res., 26 (2010), pp. 425-450.
[28] T. F. Chan, G. H. Golub, and P. Mulet, A nonlinear primal-dual method for total variation-based image restoration, SIAM J. Sci. Comput., 20 (1999), pp. 1964-1977, https://doi.org/10.1137/S1064827596299767. · Zbl 0929.68118
[29] B. Crestel, G. Stadler, and O. Ghattas, A comparative study of structural similarity and regularization for joint inverse problems governed by PDEs, Inverse Problems, 35 (2018), 024003, https://doi.org/10.1088/1361-6420/aaf129. · Zbl 1412.65197
[30] T. Cui, K. Law, and Y. Marzouk, Dimension-independent likelihood-informed MCMC, J. Comput. Phys., 304 (2016), pp. 109-137. · Zbl 1349.65009
[31] L. Demanet, P.-D. Létourneau, N. Boumal, H. Calandra, J. Chiu, and S. Snelson, Matrix probing: A randomized preconditioner for the wave-equation Hessian, Appl. Comput. Harmon. Anal., 32 (2012), pp. 155-168. · Zbl 1241.65062
[32] S. C. Eisenstat and H. F. Walker, Choosing the forcing terms in an inexact Newton method, SIAM J. Sci. Comput., 17 (1996), pp. 16-32, https://doi.org/10.1137/0917003. · Zbl 0845.65021
[33] I. Epanomeritakis, V. Akçelik, O. Ghattas, and J. Bielak, A Newton-CG method for large-scale three-dimensional elastic full-waveform seismic inversion, Inverse Problems, 24 (2008), 034015, https://doi.org/10.1088/0266-5611/24/3/034015. · Zbl 1142.65052
[34] H. P. Flath, L. C. Wilcox, V. Akçelik, J. Hill, B. van Bloemen Waanders, and O. Ghattas, Fast algorithms for Bayesian uncertainty quantification in large-scale linear inverse problems based on low-rank partial Hessian approximations, SIAM J. Sci. Comput., 33 (2011), pp. 407-432, https://doi.org/10.1137/090780717. · Zbl 1229.65174
[35] L. Grasedyck and W. Hackbusch, Construction and arithmetics of \(\mathcal{H} \)-matrices, Computing, 70 (2003), pp. 295-334. · Zbl 1030.65033
[36] E. Haber, Computational Methods in Geophysical Electromagnetics, Math. Ind. (Phila.) 1, SIAM, Philadelphia, 2014, https://doi.org/10.1137/1.9781611973808.
[37] W. Hackbusch, Hierarchical Matrices: Algorithms and Analysis, Springer, Heidelberg, 2015. · Zbl 1336.65041
[38] W. Hackbusch, B. N. Khoromskij, and E. E. Tyrtyshnikov, Approximate iterations for structured matrices, Numer. Math., 109 (2008), pp. 365-383. · Zbl 1144.65029
[39] N. Halko, P. Martinsson, and J. A. Tropp, Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev., 53 (2011), pp. 217-288, https://doi.org/10.1137/090771806. · Zbl 1269.65043
[40] M. Heinkenschloss, Mesh independence for nonlinear least squares problems with norm constraints, SIAM J. Optim., 3 (1993), pp. 81-117, https://doi.org/10.1137/0803005. · Zbl 0771.65030
[41] M. Hesse and G. Stadler, Joint inversion in coupled quasistatic poroelasticity, J. Geophys. Res. Solid Earth, 119 (2014), pp. 1425-1445.
[42] N. J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, Philadelphia, 2002, https://doi.org/10.1137/1.9780898718027. · Zbl 1011.65010
[43] M. Hinze, R. Pinnau, M. Ulbrich, and S. Ulbrich, Optimization with PDE Constraints, Springer, New York, 2009. · Zbl 1167.49001
[44] T. Isaac, N. Petra, G. Stadler, and O. Ghattas, Scalable and efficient algorithms for the propagation of uncertainty from data through inference to prediction for large-scale problems, with application to flow of the Antarctic ice sheet, J. Comput. Phys., 296 (2015), pp. 348-368, https://doi.org/10.1016/j.jcp.2015.04.047. · Zbl 1352.86017
[45] T. G. Kolda and B. W. Bader, Tensor decompositions and applications, SIAM Rev., 51 (2009), pp. 455-500, https://doi.org/10.1137/07070111X. · Zbl 1173.65029
[46] L. Lin, J. Lu, and L. Ying, Fast construction of hierarchical matrix representation from matrix-vector multiplication, J. Comput. Phys., 230 (2011), pp. 4071-4087. · Zbl 1218.65038
[47] A. Logg, K.-A. Mardal, and G. N. Wells, eds., Automated Solution of Differential Equations by the Finite Element Method, Springer, Berlin, Heidelberg, 2012, https://doi.org/10.1007/978-3-642-23099-8.
[48] J. Martin, L. C. Wilcox, C. Burstedde, and O. Ghattas, A stochastic Newton MCMC method for large-scale statistical inverse problems with application to seismic inversion, SIAM J. Sci. Comput., 34 (2012), pp. A1460-A1487, https://doi.org/10.1137/110845598. · Zbl 1250.65011
[49] P. G. Martinsson, A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 1251-1274, https://doi.org/10.1137/100786617. · Zbl 1237.65028
[50] P.-G. Martinsson, Compressing rank-structured matrices via randomized sampling, SIAM J. Sci. Comput., 38 (2016), pp. A1959-A1986, https://doi.org/10.1137/15M1016679.
[51] R. Nammour, Approximate Multi-Parameter Inverse Scattering Using Pseudodifferential Scaling, Ph.D. thesis, Rice University, Houston, TX, 2011.
[52] R. Nammour and W. W. Symes, Approximate constant density acoustic inverse scattering using dip-dependent scaling, in SEG Technical Program Expanded Abstracts, 2009, pp. 2347-2351.
[53] J. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed., Springer-Verlag, Berlin, Heidelberg, New York, 2006. · Zbl 1104.65059
[54] V. Pan and R. Schreiber, An improved Newton iteration for the generalized inverse of a matrix, with applications, SIAM J. Sci. Statist. Comput., 12 (1991), pp. 1109-1130, https://doi.org/10.1137/0912058. · Zbl 0733.65023
[55] V. Pan, F. Soleymani, and L. Zhao, An efficient computation of generalized inverse of a matrix, Appl. Math. Comput., 316 (2018), pp. 89-101. · Zbl 1426.65040
[56] N. Petra, J. Martin, G. Stadler, and O. Ghattas, A computational framework for infinite-dimensional Bayesian inverse problems, Part II: Stochastic Newton MCMC with application to ice sheet flow inverse problems, SIAM J. Sci. Comput., 36 (2014), pp. A1525-A1555, https://doi.org/10.1137/130934805. · Zbl 1303.35110
[57] B. Rivière, Discontinuous Galerkin Methods for Solving Elliptic and Parabolic Equations: Theory and Implementation, SIAM, Philadelphia, 2008, https://doi.org/10.1137/1.9780898717440. · Zbl 1153.65112
[58] P. Sanders, J. Speck, and R. Steffen, Work-efficient matrix inversion in polylogarithmic time, ACM Trans. Parallel Comput., 2 (2015), 15.
[59] G. Schulz, Iterative Berechung der reziproken Matrix, ZAMM Z. Angew. Math. Mech., 13 (1933), pp. 57-59. · JFM 59.0535.04
[60] T. Söderström and G. W. Stewart, On the numerical properties of an iterative method for computing the Moore-Penrose generalized inverse, SIAM J. Numer. Anal., 11 (1974), pp. 61-74, https://doi.org/10.1137/0711008. · Zbl 0241.65038
[61] R. Versteeg, The Marmousi experience: Velocity model determination on a synthetic complex data set, Lead. Edge, 13 (1994), pp. 927-936.
[62] U. Villa, N. Petra, and O. Ghattas, hIPPYlib: An extensible software framework for large-scale deterministic and Bayesian inverse problems, J. Open Source Softw., 3 (2018), 940, https://doi.org/10.21105/joss.00940.
[63] J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li, Fast algorithms for hierarchically semiseparable matrices, Numer. Linear Algebra Appl., 17 (2010), pp. 953-976. · Zbl 1240.65087
[64] Y. Yang and B. Engquist, Analysis of optimal transport and related misfit functions in full-waveform inversion, Geophysics, 83 (2018), pp. A7-A12.
[65] R. Yokota, G. Turkiyyah, and D. Keyes, Communication complexity of the fast multipole method and its algebraic variants, Supercomput. Front. Innov., 1 (2014), pp. 63-84.
[66] C. D. Yu, J. Levitt, S. Reiz, and G. Biros, Geometry-oblivious FMM for compressing dense SPD matrices, in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC ’17), 2017, 53.
[67] C. D. Yu, S. Reiz, and G. Biros, Distributed-memory hierarchical compression of dense SPD matrices, in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC ’18), 2018, 15.
[68] S. Zampini, PETScOPT: A Framework for High Performance PDE-Constrained Optimization with PETSc, https://github.com/stefanozampini/petscopt/.
[69] S. Zampini, Non-overlapping Domain Decomposition Methods for Three-Dimensional Cardiac Reaction-Diffusion Models and Applications, XLedizioni, 2011.
[70] S. Zampini, PCBDDC: A class of robust dual-primal methods in PETSc, SIAM J. Sci. Comput., 38 (2016), pp. S282-S306, https://doi.org/10.1137/15M1025785. · Zbl 1352.65632
[71] S. Zampini, Adaptive BDDC deluxe methods for H (curl), in Domain Decomposition Methods in Science and Engineering XXIII, Springer, Cham, 2017, pp. 285-292. · Zbl 1371.78318
[72] S. Zampini, P. Vassilevski, V. Dobrev, and T. Kolev, Balancing domain decomposition by constraints algorithms for curl-conforming spaces of arbitrary order, in Proceedings of the International Conference on Domain Decomposition Methods, Springer, Cham, 2017, pp. 103-116. · Zbl 1442.65435
[73] M. Zaslavsky, V. Druskin, A. Abubakar, T. Habashy, and V. Simoncini, Large-scale Gauss-Newton inversion of transient controlled-source electromagnetic measurement data using the model reduction framework, Geophysics, 78 (2013), pp. E161-E171.
[74] H. Zhu, S. Li, S. Fomel, G. Stadler, and O. Ghattas, A Bayesian approach to estimate uncertainty for full waveform inversion with a priori information from depth migration, Geophysics, 81 (2016), pp. R307-R323.
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.