Top

BIT Numerical Mathematics

Published in:

01-03-2015

A spectrally accurate direct solution technique for frequency-domain scattering problems with variable media

Authors: Adrianna Gillman, Alex H. Barnett, Per-Gunnar Martinsson

Published in: BIT Numerical Mathematics | Issue 1/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper presents a direct solution technique for the scattering of time-harmonic waves from a bounded region of the plane in which the wavenumber varies smoothly in space. The method constructs the interior Dirichlet-to-Neumann (DtN) map for the bounded region via bottom-up recursive merges of (discretization of) certain boundary operators on a quadtree of boxes. These operators take the form of impedance-to-impedance (ItI) maps. Since ItI maps are unitary, this formulation is inherently numerically stable, and is immune to problems of artificial internal resonances. The ItI maps on the smallest (leaf) boxes are built by spectral collocation on tensor-product grids of Chebyshev nodes. At the top level the DtN map is recovered from the ItI map and coupled to a boundary integral formulation of the free space exterior problem, to give a provably second kind equation. Numerical results indicate that the scheme can solve challenging problems 70 wavelengths on a side to 9-digit accuracy with 4 million unknowns, in under 5 min on a desktop workstation. Each additional solve corresponding to a different incident wave (right-hand side) then requires only 0.04 s.

previous article An efficient algorithm for computing acoustic wave interactions in large -obstacle three dimensional configurations

next article When is the error in the -BEM for solving the Helmholtz equation bounded independently of ?

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

This is also known as the Steklov–Poincaré operator [28].

Including both endpoints allows more accurate interpolation back to Gauss nodes; functions on each edge are available at all Chebyshev nodes for that edge.

We note that some refinement is necessary even though the solution is smooth near the (fictitious) corners. However, the extra cost of refinement, as opposed to, say, local corner rounding, is negligible.

The choice of bump height and width needs to be made carefully to ensure that a usable bandgap exists; this was done by creating a separate spectral solver for the band structure of the periodic problem.

Ang, W.: A beginner’s course in boundary element methods. Universal Publishers, USA (2007)

Babuska, I.M., Sauter, S.A.: Is the pollution effect of the FEM avoidable for the Helmholtz equation considering high wave numbers SIAM. J. Numer. Anal. 34(6), 2392–2423 (1997)MATHMathSciNet

Bayliss, A., Goldstein, C.I., Turkel, E.: The numerical solution of the Helmholtz equation for wave propagation problems in underwater acoustics. Comput. Math. Appl. 11(7–8), 655–665 (1985)CrossRefMATHMathSciNet

Bayliss, A., Goldstein, C.I., Turkel, E.: On accuracy conditions for the numerical computation of waves. J. Comput. Phys. 59(3), 396–404 (1985)CrossRefMATHMathSciNet

Bebendorf, M.: Hierarchical matrices. Lecture Notes in Computational Science and Engineering. Springer, Berlin (2008)MATH

Börm, S.: Efficient numerical methods for non-local operators. EMS Tracts in Mathematics. European Mathematical Society (EMS), Zürich (2010)CrossRefMATH

Britt, S., Tsynkov, S., Turkel, E.: Numerical simulation of time-harmonic waves in inhomogeneous media using compact high order schemes. Commun. Comput. Phys. 9(3), 520–541 (2011)MathSciNet

Chen, Y.: A fast, direct algorithm for the Lippmann–Schwinger integral equation in two dimensions. Adv. Comput. Math. 16(2–3), 175–190 (2002)CrossRefMATHMathSciNet

Y. Chen. Total wave based fast direct solver for volume scattering problems. arxiv.org., #1302.2101 (2013)

10.

Collino, F., Ghanemi, S., Joly, P.: Domain decomposition method for harmonic wave propagation: a general presentation. Comput. Methods Appl. Mech. Eng. 184(2–4), 171–211 (2000)CrossRefMATHMathSciNet

11.

Colton, D., Kress, R.: Inverse acoustic and electromagnetic scattering theory. Applied Mathematical Sciences, 2nd edn. Springer, Berlin (1998)CrossRefMATH

12.

Duan, R., Rokhlin, V.: High-order quadratures for the solution of scattering problems in two dimensions. J. Comput. Phys. 228(6), 2152–2174 (2009)CrossRefMATHMathSciNet

13.

Engquist, B., Majda, A.: Absorbing boundary conditions for the numerical simulation of waves. Math. Comput. 31, 629–651 (1977)CrossRefMATHMathSciNet

14.

Engquist, B., Ying, L.: Sweeping preconditioner for the Helmholtz equation: moving perfectly matched layers. Multiscale Model. Simul. 9(2), 686–710 (2011)CrossRefMATHMathSciNet

15.

Fang, Q., Meaney, P.M., Paulsen, K.D.: Viable three-dimensional medical microwave tomography: theory and numerical experiments. IEEE Trans. Antennas Propag. 58(2), 449–458 (2010)CrossRefMathSciNet

16.

Friedlander, L.: Some inequalities between Dirichlet and Neumann eigenvalues. Arch. Ration. Mech. Anal. 116(2), 153–160 (1991)CrossRefMATH

17.

George, A.: Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal. 10, 345–363 (1973)CrossRefMATHMathSciNet

18.

Gillman, A., Martinsson, P.: A direct solver with \(O(N)\) complexity for variable coefficient elliptic PDEs discretized via a high-order composite spectral collocation method (2013) (In review).

19.

Gillman, A., Young, P., Martinsson, P.: A direct solver O(N) complexity for integral equations on one-dimensional domains. Front. Math. China 7, 217–247 (2012). doi:10.1007/s11464-012-0188-3 CrossRefMATHMathSciNet

20.

Hackbusch, W.: A sparse matrix arithmetic based on H-matrices. Part I: Introduction to H-matrices. Computing 62, 89–108 (1999)CrossRefMATHMathSciNet

21.

Hao, S., Barnett, A.H., Martinsson, P.G., Young, P.: High-order accurate Nyström discretization of integral equations with weakly singular kernels on smooth curves in the plane Adv. Comput. Math. (2013) (in press)

22.

Heikkola, E., Rossi, T., Toivanen, J.: Fast direct solution of the Helmholtz equation with a perfectly matched layer/an absorbing boundary condition. Int. J. Numer. Methods Eng. 57, 2007–2025 (2003)CrossRefMATHMathSciNet

23.

Ho, K., Greengard, L.: A fast direct solver for structured linear systems by recursive skeletonization. SIAM J. Sci. Comput. 34(5), A2507–A2532 (2012)CrossRefMATHMathSciNet

24.

Kirsch, A., Monk, P.: An analysis of the coupling of finite-element and Nyström methods in acoustic scattering. IMA J. Numer. Anal. 14, 523–544 (1994)CrossRefMATHMathSciNet

25.

Kopriva, D.: A staggered-grid multi domain spectral method for the compressible Navier–Stokes equations. J. Comput. Phys 143(1), 125–158 (1998)CrossRefMATHMathSciNet

26.

Martinsson, P.: A fast direct solver for a class of elliptic partial differential equations. J. Sci. Comput. 38(3), 316–330 (2009)CrossRefMATHMathSciNet

27.

Martinsson, P.: A direct solver for variable coefficient elliptic PDEs discretized via a composite spectral collocation method. J. Comput. Phys. 242, 460–479 (2013)CrossRefMATHMathSciNet

28.

McLean, W.: Strongly elliptic systems and boundary integral equations. Cambridge University Press, Cambridge (2000)MATH

29.

Nicholls, D.P., Nigam, N.: Exact non-reflecting boundary conditions on general domains. J. Comput. Phys. 194(1), 278–303 (2004)CrossRefMATHMathSciNet

30.

Olver, F., Lozier, D., Boisvert, R., Clark, C. (eds.) NIST Handbook of Mathematical Functions. Cambridge University Press, Cambridge (2010). http://dlmf.nist.gov

31.

Pfeiffer, H., Kidder, L., Scheel, M., Teukolsky, S.: A multidomain spectral method for solving elliptic equations. Comput. Phys. Commun. 152(3), 253–273 (2003)CrossRefMATHMathSciNet

32.

Salzer, H.E.: Lagrangian interpolation at the Chebyshev points \(x_{n,\nu } \equiv \cos (\nu \pi /n)\), \(\nu =0(1)n\); some unnoted advantages. Comput. J. 15, 156–159 (1972)CrossRefMATHMathSciNet

33.

Schmitz, P., Ying, L.: A fast direct solver for elliptic problems on Cartesian meshes in 3D, 2011 (preprint)

34.

Schmitz, P., Ying, L.: A fast direct solver for elliptic problems on general meshes in 2D. J. Comput. Phys. 231(4), 1314–1338 (2012)CrossRefMATHMathSciNet

35.

Trefethen, L.: Spectral methods in MATLAB. SIAM, Philadelphia (2000)CrossRefMATH

36.

Tyrtyshnikov, E.E.: A brief introduction to numerical analysis. Birkhäuser, Boston (1997)CrossRefMATH

37.

Wadbro, E., Berggren, M.: High contrast microwave tomography using topology optimization techniques. J. Comput. Appl. Math. 234, 1773–1780 (2010)CrossRefMATHMathSciNet

38.

Wang, S., de Hoop, M.V., Xia, J.: On 3D modeling of seismic wave propagation via a structured parallel multifrontal direct Helmholtz solver. Geophys. Prospect. 59(5), 857–873 (2011)

39.

Xia, J., Chandrasekaran, S., Gu, M., Li, X.: Superfast multifrontal method for large structured linear systems of equations. SIAM J. Matrix Anal. Appl. 31(3), 1382–1411 (2009)CrossRefMathSciNet

40.

Xia, J., Chandrasekaran, S., Gu, M., Li, X.S.: Fast algorithms for hierarchically semiseparable matrices. Numer. Linear Algebra Appl. 17(6), 953–976 (2010)CrossRefMATHMathSciNet

41.

Yang, B., Hesthaven, J.: Multidomain pseudospectral computation of Maxwell’s equations in 3-D general curvilinear coordinates. Appl. Numer. Math. 33(1–4), 281–289 (2000)CrossRefMATHMathSciNet

Title: A spectrally accurate direct solution technique for frequency-domain scattering problems with variable media
Authors: Adrianna Gillman
Alex H. Barnett
Per-Gunnar Martinsson
Publication date: 01-03-2015
Publisher: Springer Netherlands
Published in: BIT Numerical Mathematics / Issue 1/2015
Print ISSN: 0006-3835
Electronic ISSN: 1572-9125
DOI: https://doi.org/10.1007/s10543-014-0499-8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 1/2015

Bounding acoustic layer potentials via oscillatory integral techniques

Adaptive edge element approximation of H(curl)-elliptic optimal control problems with control constraints

Regularity for Maxwell eigenproblems in photonic crystal fibre modelling

Robin-to-Robin transparent boundary conditions for the computation of guided modes in photonic crystal wave-guides

Convergence of infinite element methods for scalar waveguide problems

A second-kind Galerkin boundary element method for scattering at composite objects

Premium Partner