Skip to main content
Top
Published in: BIT Numerical Mathematics 2/2015

01-06-2015

A high-order accurate accelerated direct solver for acoustic scattering from surfaces

Authors: James Bremer, Adrianna Gillman, Per-Gunnar Martinsson

Published in: BIT Numerical Mathematics | Issue 2/2015

Log in

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

search-config
loading …

Abstract

We describe an accelerated direct solver for the integral equations which model low-frequency acoustic scattering from curved surfaces. Surfaces are specified via a collection of smooth parameterizations given on triangles, a setting which generalizes the typical one of triangulated surfaces, and the integral equations are discretized via a high-order Nyström method. This allows for rapid convergence in cases in which high-order surface information is available. The high-order discretization technique is coupled with a direct solver based on the recursive construction of scattering matrices. The result is a solver which often attains \(O(N^{1.5})\) complexity in the number of discretization nodes \(N\) and which is resistant to many of the pathologies which stymie iterative solvers in the numerical simulation of scattering. The performance of the algorithm is illustrated with numerical experiments which involve the simulation of scattering from a variety of domains, including one consisting of a collection of 1,000 ellipsoids with randomly chosen semiaxes arranged in a grid, and a domain whose boundary has 12 curved edges and 8 corner points.

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!

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!

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!

Literature
2.
go back to reference Barnett, A., Greengard, L.: A new integral representation for quasi-periodic fields and its application to two-dimensional band structure calculations. J. Comput. Phys. 229, 6898–6914 (2010)CrossRefMATHMathSciNet Barnett, A., Greengard, L.: A new integral representation for quasi-periodic fields and its application to two-dimensional band structure calculations. J. Comput. Phys. 229, 6898–6914 (2010)CrossRefMATHMathSciNet
3.
go back to reference Börm, S., Hackbusch, W.: Approximation, of boundary element operators by adaptive \({\fancyscript {H}}^{2}\)-matrices. In: Foundations of Computational Mathematics: Minneapolis, 2002, vol. 312 of London Math. Soc. Lecture Note Ser., pp. 58–75. Cambridge Univ. Press, Cambridge (2004) Börm, S., Hackbusch, W.: Approximation, of boundary element operators by adaptive \({\fancyscript {H}}^{2}\)-matrices. In: Foundations of Computational Mathematics: Minneapolis, 2002, vol. 312 of London Math. Soc. Lecture Note Ser., pp. 58–75. Cambridge Univ. Press, Cambridge (2004)
4.
go back to reference Brakhage, H., Werner, P.: Über das Dirichletsche Au\(\beta \)enraum problem für die Helmholtzsche Schwingungsgleichung. Arch. Math. 16, 325–329 (1965)CrossRefMATHMathSciNet Brakhage, H., Werner, P.: Über das Dirichletsche Au\(\beta \)enraum problem für die Helmholtzsche Schwingungsgleichung. Arch. Math. 16, 325–329 (1965)CrossRefMATHMathSciNet
5.
go back to reference Bremer, J.: A fast direct solver for the integral equations of scattering theory on planar curves with corners. J. Comput. Phys. 231, 45–64 (2012)CrossRefMathSciNet Bremer, J.: A fast direct solver for the integral equations of scattering theory on planar curves with corners. J. Comput. Phys. 231, 45–64 (2012)CrossRefMathSciNet
6.
go back to reference Bremer, J.: On the Nyström discretization of integral operators on planar domains with corners. Appl. Comput. Harmon. Anal. 32, 45–64 (2012)CrossRefMATHMathSciNet Bremer, J.: On the Nyström discretization of integral operators on planar domains with corners. Appl. Comput. Harmon. Anal. 32, 45–64 (2012)CrossRefMATHMathSciNet
7.
go back to reference Bremer, J., Gillman, A., Martinsson, P.-G.: A high-order accurate accelerated direct solver for acoustic scattering from surfaces (2013). arXiv:1308.6643 Bremer, J., Gillman, A., Martinsson, P.-G.: A high-order accurate accelerated direct solver for acoustic scattering from surfaces (2013). arXiv:​1308.​6643
8.
go back to reference Bremer, J., Gimbutas, Z.: A Nyström method for weakly singular integral operators on surfaces. J. Comput. Phys. 231, 4885–4903 (2012)CrossRefMATHMathSciNet Bremer, J., Gimbutas, Z.: A Nyström method for weakly singular integral operators on surfaces. J. Comput. Phys. 231, 4885–4903 (2012)CrossRefMATHMathSciNet
9.
go back to reference Bremer, J., Gimbutas, Z.: On the numerical evaluation of the singular integrals of scattering theory. J. Comput. Phys. 251, 327–343 (2013)CrossRefMathSciNet Bremer, J., Gimbutas, Z.: On the numerical evaluation of the singular integrals of scattering theory. J. Comput. Phys. 251, 327–343 (2013)CrossRefMathSciNet
10.
go back to reference Bremer, J., Gimbutas, Z., Rokhlin, V.: A nonlinear optimization procedure for generalized Gaussian quadratures. SIAM J. Sci. Comput. 32, 1761–1788 (2010)CrossRefMATHMathSciNet Bremer, J., Gimbutas, Z., Rokhlin, V.: A nonlinear optimization procedure for generalized Gaussian quadratures. SIAM J. Sci. Comput. 32, 1761–1788 (2010)CrossRefMATHMathSciNet
11.
go back to reference Bremer, J., Rokhlin, V., Sammis, I.: Universal quadratures for boundary integral equations on two-dimensional domains with corners. J. Comput. Phys. 229, 8259–8280 (2010)CrossRefMATHMathSciNet Bremer, J., Rokhlin, V., Sammis, I.: Universal quadratures for boundary integral equations on two-dimensional domains with corners. J. Comput. Phys. 229, 8259–8280 (2010)CrossRefMATHMathSciNet
12.
go back to reference Bruno, O., Elling, T., Turc, C.: Well-conditioned high-order algorithms for the solution of three-dimensional surface acoustic scattering problems with Neumann boundary conditions. J. Numer. Methods Eng. 91, 1045–1072 (2012)CrossRefMathSciNet Bruno, O., Elling, T., Turc, C.: Well-conditioned high-order algorithms for the solution of three-dimensional surface acoustic scattering problems with Neumann boundary conditions. J. Numer. Methods Eng. 91, 1045–1072 (2012)CrossRefMathSciNet
13.
go back to reference Chandrasekaran, S., Gu, M.: Fast and stable algorithms for banded plus semiseparable systems of linear equations. SIAM J. Matrix Anal. Appl. 25(2), 373–384 (2003). (electronic)CrossRefMATHMathSciNet Chandrasekaran, S., Gu, M.: Fast and stable algorithms for banded plus semiseparable systems of linear equations. SIAM J. Matrix Anal. Appl. 25(2), 373–384 (2003). (electronic)CrossRefMATHMathSciNet
14.
go back to reference Cheng, H., Gimbutas, Z., Martinsson, P., Rokhlin, V.: On the compression of low rank matrices. SIAM J. Sci. Comput. 26(4), 1389–1404 (2005)CrossRefMATHMathSciNet Cheng, H., Gimbutas, Z., Martinsson, P., Rokhlin, V.: On the compression of low rank matrices. SIAM J. Sci. Comput. 26(4), 1389–1404 (2005)CrossRefMATHMathSciNet
15.
go back to reference Colton, D., Kress, R.: Inverse Acoustic and Electromagnetic Scattering Theory, 2nd edn. Springer, New York (1998)CrossRefMATH Colton, D., Kress, R.: Inverse Acoustic and Electromagnetic Scattering Theory, 2nd edn. Springer, New York (1998)CrossRefMATH
17.
18.
go back to reference Greengard, L., Gueyffier, D., Martinsson, P.-G., Rokhlin, V.: Fast direct solvers for integral equations in complex three-dimensional domains. Acta Numer. 18, 243–275 (2009)CrossRefMATHMathSciNet Greengard, L., Gueyffier, D., Martinsson, P.-G., Rokhlin, V.: Fast direct solvers for integral equations in complex three-dimensional domains. Acta Numer. 18, 243–275 (2009)CrossRefMATHMathSciNet
19.
go back to reference Gu, M., Eisenstat, S.C.: Efficient algorithms for computing a strong rank-revealing QR factorization. SIAM J. Sci. Comput. 17(4), 848–869 (1996)CrossRefMATHMathSciNet Gu, M., Eisenstat, S.C.: Efficient algorithms for computing a strong rank-revealing QR factorization. SIAM J. Sci. Comput. 17(4), 848–869 (1996)CrossRefMATHMathSciNet
20.
go back to reference Hackbusch, W.: Integral Equations: theory and numerical treatment. Birkhäuser, Berlin (1995)CrossRefMATH Hackbusch, W.: Integral Equations: theory and numerical treatment. Birkhäuser, Berlin (1995)CrossRefMATH
21.
go back to reference Hackbusch, W., Khoromskij, B., Sauter, S.: On \({\fancyscript {H}}^{2}\)-matrices. In: Lectures on Applied Mathematics, pp. 9–29. Springer, Berlin (2002) Hackbusch, W., Khoromskij, B., Sauter, S.: On \({\fancyscript {H}}^{2}\)-matrices. In: Lectures on Applied Mathematics, pp. 9–29. Springer, Berlin (2002)
22.
go back to reference Halko, N., Martinsson, P.-G., Tropp, J.A.: Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53(2), 217–288 (2011)CrossRefMATHMathSciNet Halko, N., Martinsson, P.-G., Tropp, J.A.: Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53(2), 217–288 (2011)CrossRefMATHMathSciNet
23.
go back to reference Helsing, J.: A fast and stable solver for singular integral equations on piecewise smooth curves. SIAM J. Sci. Comput. 33, 153–174 (2011)CrossRefMATHMathSciNet Helsing, J.: A fast and stable solver for singular integral equations on piecewise smooth curves. SIAM J. Sci. Comput. 33, 153–174 (2011)CrossRefMATHMathSciNet
24.
go back to reference Helsing, J., Ojala, R.: Corner singularities for elliptic problems: integral equations, graded meshes, quadrature, and compressed inverse preconditioning. J. Comput. Phys. 227, 8820–8840 (2008)CrossRefMATHMathSciNet Helsing, J., Ojala, R.: Corner singularities for elliptic problems: integral equations, graded meshes, quadrature, and compressed inverse preconditioning. J. Comput. Phys. 227, 8820–8840 (2008)CrossRefMATHMathSciNet
25.
go back to reference Ho, K., Greengard, L.: A fast direct solver for structured linear systems by recursive skeletonization. SIAM J. Sci. Comput. 34(5), 2507–2532 (2012)CrossRefMathSciNet Ho, K., Greengard, L.: A fast direct solver for structured linear systems by recursive skeletonization. SIAM J. Sci. Comput. 34(5), 2507–2532 (2012)CrossRefMathSciNet
27.
go back to reference Martinsson, P., Rokhlin, V.: A fast direct solver for boundary integral equations in two dimensions. J. Comput. Phys. 205(1), 1–23 (2005)CrossRefMATHMathSciNet Martinsson, P., Rokhlin, V.: A fast direct solver for boundary integral equations in two dimensions. J. Comput. Phys. 205(1), 1–23 (2005)CrossRefMATHMathSciNet
28.
go back to reference Nédélec, J.-C.: Acoustic and Electromagnetic Equations: Integral Representations for Harmonic Functions. Springer, New York (2012) Nédélec, J.-C.: Acoustic and Electromagnetic Equations: Integral Representations for Harmonic Functions. Springer, New York (2012)
29.
go back to reference Sheng, Z., Dewilde, P., Chandrasekaran, S.: Algorithms to solve hierarchically semi-separable systems. In: System theory, the Schur algorithm and multidimensional analysis, vol. 176 of Oper. Theory Adv. Appl., pp. 255–294. Birkhäuser, Basel (2007) Sheng, Z., Dewilde, P., Chandrasekaran, S.: Algorithms to solve hierarchically semi-separable systems. In: System theory, the Schur algorithm and multidimensional analysis, vol. 176 of Oper. Theory Adv. Appl., pp. 255–294. Birkhäuser, Basel (2007)
30.
go back to reference Taskinen, M., Yla-Oijala, P.: Current and charge integral equation formulation. IEEE Trans. Antennas Propag. 54, 58–67 (2006)CrossRefMathSciNet Taskinen, M., Yla-Oijala, P.: Current and charge integral equation formulation. IEEE Trans. Antennas Propag. 54, 58–67 (2006)CrossRefMathSciNet
31.
go back to reference Xia, J., Chandrasekaran, S., Gu, M., Li, X.: Fast algorithms for hierarchically semiseparable matrices. Numer. Linear Algebr. Appl. 17(6), 953–976 (2010)CrossRefMATHMathSciNet Xia, J., Chandrasekaran, S., Gu, M., Li, X.: Fast algorithms for hierarchically semiseparable matrices. Numer. Linear Algebr. Appl. 17(6), 953–976 (2010)CrossRefMATHMathSciNet
32.
go back to reference Xia, J., Chandrasekaran, S., Gu, M., Li, X.S.: Superfast multifrontal method for large structured linear systems of equations. SIAM J. Matrix Anal. Appl. 31(3), 1382–1411 (2009)CrossRefMathSciNet Xia, J., Chandrasekaran, S., Gu, M., Li, X.S.: Superfast multifrontal method for large structured linear systems of equations. SIAM J. Matrix Anal. Appl. 31(3), 1382–1411 (2009)CrossRefMathSciNet
Metadata
Title
A high-order accurate accelerated direct solver for acoustic scattering from surfaces
Authors
James Bremer
Adrianna Gillman
Per-Gunnar Martinsson
Publication date
01-06-2015
Publisher
Springer Netherlands
Published in
BIT Numerical Mathematics / Issue 2/2015
Print ISSN: 0006-3835
Electronic ISSN: 1572-9125
DOI
https://doi.org/10.1007/s10543-014-0508-y

Other articles of this Issue 2/2015

BIT Numerical Mathematics 2/2015 Go to the issue

Premium Partner