A Filon-Clenshaw-Curtis-Smolyak rule for multi-dimensional oscillatory integrals with application to a UQ problem for the Helmholtz equation

Wu, Zhizhang; Graham, Ivan; Ma, Dingjiong; Zhang, Zhiwen

doi:10.1090/mcom/4007

A Filon-Clenshaw-Curtis-Smolyak rule for multi-dimensional oscillatory integrals with application to a UQ problem for the Helmholtz equation
HTML articles powered by AMS MathViewer

by Zhizhang Wu, Ivan G. Graham, Dingjiong Ma and Zhiwen Zhang;

Math. Comp.

DOI: https://doi.org/10.1090/mcom/4007

Published electronically: August 15, 2024

HTML | PDF | Request permission

Abstract:

In this paper, we combine the Smolyak technique for multi-dimensional interpolation with the Filon-Clenshaw-Curtis (FCC) rule for one-dimensional oscillatory integration, to obtain a new Filon-Clenshaw-Curtis-Smolyak (FCCS) rule for oscillatory integrals with linear phase over the $d-$dimensional cube $[-1,1]^d$. By combining stability and convergence estimates for the FCC rule with error estimates for the Smolyak interpolation operator, we obtain an error estimate for the FCCS rule, consisting of the product of a Smolyak-type error estimate multiplied by a term that decreases with $\mathcal {O}(k^{-\widetilde {d}})$, where $k$ is the wavenumber and $\widetilde {d}$ is the number of oscillatory dimensions. If all dimensions are oscillatory, a higher negative power of $k$ appears in the estimate. As an application, we consider the forward problem of uncertainty quantification (UQ) for a one-space-dimensional Helmholtz problem with wavenumber $k$ and a random heterogeneous refractive index, depending in an affine way on $d$ i.i.d. uniform random variables. After applying a classical hybrid numerical-asymptotic approximation, expectations of functionals of the solution of this problem can be formulated as a sum of oscillatory integrals over $[-1,1]^d$, which we compute using the FCCS rule. We give numerical results for the FCCS rule which illustrate its theoretical properties and show that the accuracy of the UQ algorithm improves when both $k$ and the order of the FCCS rule increase. We also give results for both the quadrature and UQ problems when the underlying FCCS rule uses a dimension-adaptive Smolyak interpolation. These show increasing accuracy for the UQ problem as both the adaptive tolerance decreases and $k$ increases, requiring very modest increase in work as the stochastic dimension increases, for a case when the affine expansion in random variables decays quickly.

References

A. K. Aziz, R. B. Kellogg, and A. B. Stephens, A two point boundary value problem with a rapidly oscillating solution, Numer. Math. 53 (1988), no. 1-2, 107–121. MR 946371, DOI 10.1007/BF01395880
Joakim Bäck, Fabio Nobile, Lorenzo Tamellini, and Raul Tempone, Stochastic spectral Galerkin and collocation methods for PDEs with random coefficients: a numerical comparison, Spectral and high order methods for partial differential equations, Lect. Notes Comput. Sci. Eng., vol. 76, Springer, Heidelberg, 2011, pp. 43–62. MR 3204803, DOI 10.1007/978-3-642-15337-2_{3}
Volker Barthelmann, Erich Novak, and Klaus Ritter, High dimensional polynomial interpolation on sparse grids, Adv. Comput. Math. 12 (2000), no. 4, 273–288. Multivariate polynomial interpolation. MR 1768951, DOI 10.1023/A:1018977404843
Simon N. Chandler-Wilde, Ivan G. Graham, Stephen Langdon, and Euan A. Spence, Numerical-asymptotic boundary integral methods in high-frequency acoustic scattering, Acta Numer. 21 (2012), 89–305. MR 2916382, DOI 10.1017/S0962492912000037
Abdellah Chkifa, Albert Cohen, and Christoph Schwab, High-dimensional adaptive sparse polynomial interpolation and applications to parametric PDEs, Found. Comput. Math. 14 (2014), no. 4, 601–633. MR 3230010, DOI 10.1007/s10208-013-9154-z
C. W. Clenshaw and A. R. Curtis, A method for numerical integration on an automatic computer, Numer. Math. 2 (1960), 197–205. MR 117885, DOI 10.1007/BF01386223
B. A. Davey and H. A. Priestley, Introduction to lattices and order, Cambridge Mathematical Textbooks, Cambridge University Press, Cambridge, 1990. MR 1058437
Alfredo Deaño, Daan Huybrechs, and Arieh Iserles, Computing highly oscillatory integrals, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2018. MR 3743075
Josef Dick, Frances Y. Kuo, and Ian H. Sloan, High-dimensional integration: the quasi-Monte Carlo way, Acta Numer. 22 (2013), 133–288. MR 3038697, DOI 10.1017/S0962492913000044
V. Domínguez, I. G. Graham, and T. Kim, Filon-Clenshaw-Curtis rules for highly oscillatory integrals with algebraic singularities and stationary points, SIAM J. Numer. Anal. 51 (2013), no. 3, 1542–1566. MR 3056760, DOI 10.1137/120884146
V. Domínguez, I. G. Graham, and V. P. Smyshlyaev, Stability and error estimates for Filon-Clenshaw-Curtis rules for highly oscillatory integrals, IMA J. Numer. Anal. 31 (2011), no. 4, 1253–1280. MR 2846755, DOI 10.1093/imanum/drq036
Xiaobing Feng, Junshan Lin, and Cody Lorton, An efficient numerical method for acoustic wave scattering in random media, SIAM/ASA J. Uncertain. Quantif. 3 (2015), no. 1, 790–822. MR 3394366, DOI 10.1137/140958232
M. Ganesh, Frances Y. Kuo, and Ian H. Sloan, Quasi-Monte Carlo finite element analysis for wave propagation in heterogeneous random media, SIAM/ASA J. Uncertain. Quantif. 9 (2021), no. 1, 106–134. MR 4205674, DOI 10.1137/20M1334164
Thomas Gerstner and Michael Griebel, Numerical integration using sparse grids, Numer. Algorithms 18 (1998), no. 3-4, 209–232. MR 1669959, DOI 10.1023/A:1019129717644
T. Gerstner and M. Griebel, Dimension-adaptive tensor-product quadrature, Computing 71 (2003), no. 1, 65–87. MR 2009651, DOI 10.1007/s00607-003-0015-5
A. Gibbs, D. P. Hewett, D. Huybrechs, and E. Parolin, Fast hybrid numerical-asymptotic boundary element methods for high frequency screen and aperture problems based on least-squares collocation, Partial Differ. Equ. Appl. 1 (2020), no. 4, Paper No. 21, 26. MR 4294981, DOI 10.1007/s42985-020-00013-3
S. P. Groth, D. P. Hewett, and S. Langdon, A hybrid numerical-asymptotic boundary element method for high frequency scattering by penetrable convex polygons, Wave Motion 78 (2018), 32–53. MR 3768771, DOI 10.1016/j.wavemoti.2017.12.008
Michael Hardy, Combinatorics of partial derivatives, Electron. J. Combin. 13 (2006), no. 1, Research Paper 1, 13. MR 2200529, DOI 10.37236/1027
Daan Huybrechs and Stefan Vandewalle, The construction of cubature rules for multivariate highly oscillatory integrals, Math. Comp. 76 (2007), no. 260, 1955–1980. MR 2336276, DOI 10.1090/S0025-5718-07-01937-0
Arieh Iserles, On the numerical quadrature of highly-oscillating integrals. I. Fourier transforms, IMA J. Numer. Anal. 24 (2004), no. 3, 365–391. MR 2068828, DOI 10.1093/imanum/24.3.365
Arieh Iserles, On the numerical quadrature of highly-oscillating integrals. II. Irregular oscillators, IMA J. Numer. Anal. 25 (2005), no. 1, 25–44. MR 2110233, DOI 10.1093/imanum/drh022
A. Iserles and S. P. Nørsett, On quadrature methods for highly oscillatory integrals and their implementation, BIT 44 (2004), no. 4, 755–772. MR 2211043, DOI 10.1007/s10543-004-5243-3
Arieh Iserles and Syvert P. Nørsett, Quadrature methods for multivariate highly oscillatory integrals using derivatives, Math. Comp. 75 (2006), no. 255, 1233–1258. MR 2219027, DOI 10.1090/S0025-5718-06-01854-0
A. Iserles, S. P. Nørsett, and S. Olver, Highly oscillatory quadrature: the story so far, Numerical mathematics and advanced applications, Springer, Berlin, 2006, pp. 97–118. MR 2303638, DOI 10.1007/978-3-540-34288-5_{6}
G. Maierhofer, A. Iserles, and N. Peake, Recursive moment computation in Filon methods and application to high-frequency wave scattering in two dimensions, IMA J. Numer. Anal. 43 (2023), no. 6, 3169–3211. MR 4673334, DOI 10.1093/imanum/drac067
Hassan Majidian, Efficient computation of oscillatory integrals by exponential transformations, BIT 61 (2021), no. 4, 1337–1365. MR 4332139, DOI 10.1007/s10543-021-00855-2
Hassan Majidian, Modified Filon-Clenshaw-Curtis rules for oscillatory integrals with a nonlinear oscillator, Electron. Trans. Numer. Anal. 54 (2021), 276–295. MR 4244341, DOI 10.1553/etna_{v}ol54s276
J. M. Melenk, On the convergence of Filon quadrature, J. Comput. Appl. Math. 234 (2010), no. 6, 1692–1701. MR 2644160, DOI 10.1016/j.cam.2009.08.017
F. Nobile, L. Tamellini, and R. Tempone, Convergence of quasi-optimal sparse-grid approximation of Hilbert-space-valued functions: application to random elliptic PDEs, Numer. Math. 134 (2016), no. 2, 343–388. MR 3537954, DOI 10.1007/s00211-015-0773-y
Fabio Nobile, Lorenzo Tamellini, Francesco Tesei, and Raúl Tempone, An adaptive sparse grid algorithm for elliptic PDEs with lognormal diffusion coefficient, Sparse grids and applications—Stuttgart 2014, Lect. Notes Comput. Sci. Eng., vol. 109, Springer, Cham, 2016, pp. 191–220. MR 3706342, DOI 10.1007/978-3-319-28262-6_{8}
Erich Novak, Optimal algorithms for numerical integration: recent results and open problems, Monte Carlo and quasi-Monte Carlo methods, Springer Proc. Math. Stat., vol. 460, Springer, Cham, [2024] ©2024, pp. 105–131. MR 4774917, DOI 10.1007/978-3-031-59762-6_{5}
Erich Novak and Klaus Ritter, Simple cubature formulas with high polynomial exactness, Constr. Approx. 15 (1999), no. 4, 499–522. MR 1702807, DOI 10.1007/s003659900119
Erich Novak, Mario Ullrich, and Henryk Woźniakowski, Complexity of oscillatory integration for univariate Sobolev spaces, J. Complexity 31 (2015), no. 1, 15–41. MR 3284544, DOI 10.1016/j.jco.2014.07.001
Sheehan Olver, Moment-free numerical approximation of highly oscillatory integrals with stationary points, European J. Appl. Math. 18 (2007), no. 4, 435–447. MR 2344314, DOI 10.1017/S0956792507007012
O. Pembery, The Helmholtz equation in heterogeneous and random media: Analysis and numerics, Ph.D. thesis, University of Bath, 2020.
Chiara Piazzola and Lorenzo Tamellini, Algorithm 1040: the sparse grids Matlab kit—a Matlab implementation of sparse grids for high-dimensional function approximation and uncertainty quantification, ACM Trans. Math. Software 50 (2024), no. 1, Art. 7, 22. MR 4727977
Claudia Schillings and Christoph Schwab, Sparse, adaptive Smolyak quadratures for Bayesian inverse problems, Inverse Problems 29 (2013), no. 6, 065011, 28. MR 3056084, DOI 10.1088/0266-5611/29/6/065011
E. A. Spence and J. Wunsch, Wavenumber-explicit parametric holomorphy of Helmholtz solutions in the context of uncertainty quantification, SIAM/ASA J. Uncertain. Quantif. 11 (2023), no. 2, 567–590. MR 4589578, DOI 10.1137/22M1486170
Grzegorz W. Wasilkowski and Henryk Woźniakowski, Explicit cost bounds of algorithms for multivariate tensor product problems, J. Complexity 11 (1995), no. 1, 1–56. MR 1319049, DOI 10.1006/jcom.1995.1001
R. Wong, Asymptotic approximations of integrals, Classics in Applied Mathematics, vol. 34, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2001. Corrected reprint of the 1989 original. MR 1851050, DOI 10.1137/1.9780898719260
Z. Wu, I.G.Graham, D. Ma, and Z. Zhang, A Filon-Clenshaw-Curtis-Smolyak rule for multi-dimensional oscillatory integrals with application to a UQ problem for the Helmholtz equation, arXiv:2208.10078, 2024.
Shuhuang Xiang, Efficient Filon-type methods for $\int ^b_af(x)e^{i\omega g(x)}dx$, Numer. Math. 105 (2007), no. 4, 633–658. MR 2276763, DOI 10.1007/s00211-006-0051-0
Jakob Zech and Christoph Schwab, Convergence rates of high dimensional Smolyak quadrature, ESAIM Math. Model. Numer. Anal. 54 (2020), no. 4, 1259–1307. MR 4113052, DOI 10.1051/m2an/2020003