Error estimates in the fast multipole method for scattering problems. Part 2 : truncation of the Gegenbauer series

Quentin Carayol; Francis Collino

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique (2005)

  • Volume: 39, Issue: 1, page 183-221
  • ISSN: 0764-583X

Abstract

top
We perform a complete study of the truncation error of the Gegenbauer series. This series yields an expansion of the Green kernel of the Helmholtz equation, e i | u → - v → | 4 π i | u → - v → | , which is the core of the Fast Multipole Method for the integral equations. We consider the truncated series where the summation is performed over the indices ℓ ≤ L . We prove that if v = | v → | is large enough, the truncated series gives rise to an error lower than ϵ as soon as L satisfies L + 1 2 ≃ v + C W 2 3 ( K ( α ) ϵ - δ v γ ) v 1 3 where W is the Lambert function, K ( α ) depends only on α = | u → | | v → | and C , δ , γ are pure positive constants. Numerical experiments show that this asymptotic is optimal. Those results are useful to provide sharp estimates of the error in the fast multipole method for scattering computation.

How to cite

top

Carayol, Quentin, and Collino, Francis. "Error estimates in the fast multipole method for scattering problems. Part 2 : truncation of the Gegenbauer series." ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique 39.1 (2005): 183-221. <http://eudml.org/doc/244693>.

@article{Carayol2005,
abstract = {We perform a complete study of the truncation error of the Gegenbauer series. This series yields an expansion of the Green kernel of the Helmholtz equation, $\frac\{ \{\rm e\}^\{i |\vec\{u\}-\vec\{v\}|\}\}\{4 \pi i |\vec\{u\}-\vec\{v\}|\}$, which is the core of the Fast Multipole Method for the integral equations. We consider the truncated series where the summation is performed over the indices $\ell \le L$. We prove that if $v = |\vec\{v\}|$ is large enough, the truncated series gives rise to an error lower than $\epsilon $ as soon as $L$ satisfies $L+\frac\{1\}\{2\} \simeq v + C W^\{\frac\{2\}\{3\}\}(K(\alpha ) \epsilon ^\{-\delta \} v^\gamma )\, v^\{\frac\{1\}\{3\}\}$ where $W$ is the Lambert function, $K(\alpha )$ depends only on $\alpha =\frac\{|\vec\{u\}|\}\{|\vec\{v\}|\}$ and $C\,, \delta , \, \gamma $ are pure positive constants. Numerical experiments show that this asymptotic is optimal. Those results are useful to provide sharp estimates of the error in the fast multipole method for scattering computation.},
author = {Carayol, Quentin, Collino, Francis},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique},
keywords = {Gegenbauer; fast multipole method; truncation error},
language = {eng},
number = {1},
pages = {183-221},
publisher = {EDP-Sciences},
title = {Error estimates in the fast multipole method for scattering problems. Part 2 : truncation of the Gegenbauer series},
url = {http://eudml.org/doc/244693},
volume = {39},
year = {2005},
}

TY - JOUR
AU - Carayol, Quentin
AU - Collino, Francis
TI - Error estimates in the fast multipole method for scattering problems. Part 2 : truncation of the Gegenbauer series
JO - ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique
PY - 2005
PB - EDP-Sciences
VL - 39
IS - 1
SP - 183
EP - 221
AB - We perform a complete study of the truncation error of the Gegenbauer series. This series yields an expansion of the Green kernel of the Helmholtz equation, $\frac{ {\rm e}^{i |\vec{u}-\vec{v}|}}{4 \pi i |\vec{u}-\vec{v}|}$, which is the core of the Fast Multipole Method for the integral equations. We consider the truncated series where the summation is performed over the indices $\ell \le L$. We prove that if $v = |\vec{v}|$ is large enough, the truncated series gives rise to an error lower than $\epsilon $ as soon as $L$ satisfies $L+\frac{1}{2} \simeq v + C W^{\frac{2}{3}}(K(\alpha ) \epsilon ^{-\delta } v^\gamma )\, v^{\frac{1}{3}}$ where $W$ is the Lambert function, $K(\alpha )$ depends only on $\alpha =\frac{|\vec{u}|}{|\vec{v}|}$ and $C\,, \delta , \, \gamma $ are pure positive constants. Numerical experiments show that this asymptotic is optimal. Those results are useful to provide sharp estimates of the error in the fast multipole method for scattering computation.
LA - eng
KW - Gegenbauer; fast multipole method; truncation error
UR - http://eudml.org/doc/244693
ER -

References

top
  1. [1] M. Abramowitz and I. Stegun, Handbook of Mathematical Functions. Dover, New-York (1964). 
  2. [2] S. Amini and A. Profit, Analysis of the truncation errors in the fast multipole method for scattering problems. J. Comput. Appl. Math. 115 (2000) 23–33. Zbl0973.65092
  3. [3] J.A. Barcelo, A. Ruiz and L. Vega, Weighted estimates for the Helmholtz equation and some applications. J. Funct. Anal. 150 (1997) 356–382. Zbl0890.35028
  4. [4] H. Bateman, Higher transcendental Functions. McGraw-Hill (1953). Zbl0051.30303MR58756
  5. [5] Q. Carayol, Développement et analyse d’une méthode multipôle multiniveau pour l’électromagnétisme. Ph.D. thesis, Université Paris VI Pierre et Marie Curie, rue Jussieu 75005 Paris (2002). 
  6. [6] Q. Carayol and F. Collino, Error estimates in the fast multipole method for scattering problems. part 1: Truncation of the jacobi-anger series. ESAIM: M2AN 38 (2004) 371–394. Zbl1077.41027
  7. [7] T.M. Cherry, Uniform asymptotic formulae for functions with transition points. Trans. AMS 68 (1950) 224–257. Zbl0036.06102
  8. [8] W.C. Chew, J.M. Jin, E. Michielssen and J.M. Song, Fast and Efficient Algorithms in Computational Electromagnetics. Artech House (2001). 
  9. [9] R. Coifman, V. Rokhlin and S. Greengard, The Fast Multipole Method for the wave equation: A pedestrian prescription. IEEE Antennas and Propagation Magazine 35 (1993) 7–12. 
  10. [10] D. Colton and R. Kress, Inverse Acoustic and Electromagnetic Scattering Theory. Springer-Verlag 93 (1992). Zbl0760.35053MR1183732
  11. [11] E. Darve, The fast multipole method. I. Error analysis and asymptotic complexity. SIAM J. Numer. Anal. 38 (2000) 98–128 (electronic). Zbl0974.65033
  12. [12] E. Darve, The fast multipole method: Numerical implementation. J. Comput. Physics 160 (2000) 196–240. Zbl0974.78012
  13. [13] E. Darve and P. Havé, Efficient fast multipole method for low frequency scattering. J. Comput. Physics 197 (2004) 341–363. Zbl1073.65133
  14. [14] B. Dembart and E. Yip, Accuracy of fast multipole methods for maxwell’s equations. IEEE Comput. Sci. Engrg. 5 (1998) 48–56. 
  15. [15] M.A. Epton and B. Dembart, Multipole translation theory for the three-dimensional Laplace and Helmholtz equations. SIAM J. Sci. Comput. 16 (1995) 865–897. Zbl0852.31006
  16. [16] I.S. Gradshteyn, I.M. Ryzhik, Table of integrals, series, and products, 5th edition. Academic Press (1994). Zbl0918.65002MR1243179
  17. [17] S. Koc, J. Song and W.C. Chew, Error analysis for the numerical evaluation of the diagonal forms of the scalar spherical addition theorem. SIAM J. Numer. Anal. 36 (1999) 906–921 (electronic). Zbl0924.65116
  18. [18] L. Lorch, Alternative proof of a sharpened form of Bernstein’s inequality for Legendre polynomials. Applicable Anal. 14 (1982/83) 237–240. Zbl0505.33007
  19. [19] L. Lorch, Corrigendum: “Alternative proof of a sharpened form of Bernstein’s inequality for Legendre polynomials” [Appl. Anal. 14 (1982/83) 237–240; MR 84k:26017]. Appl. Anal. 50 (1993) 47. Zbl0505.33007
  20. [20] J.C. Nédélec, Acoustic and Electromagnetic Equation. Integral Representation for Harmonic Problems. Springer-Verlag 144 (2001). Zbl0981.35002MR1822275
  21. [21] J. Rahola, Diagonal forms of the translation operators in the fast multipole algorithm for scattering problems. BIT 36 (1996) 333–358. Zbl0854.65122
  22. [22] G.N. Watson, A treatise on the theory of Bessel functions. Cambridge University Press (1966). Zbl0174.36202MR1349110JFM48.0412.02

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.