Skip to main content
SpringerLink
Log in

Low-rank approximation of integral operators by using the Green formula and quadrature

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

Approximating integral operators by a standard Galerkin discretisation typically leads to dense matrices. To avoid the quadratic complexity it takes to compute and store a dense matrix, several approaches have been introduced including \(\mathcal {H}\)-matrices. The kernel function is approximated by a separable function, this leads to a low rank matrix. Interpolation is a robust and popular scheme, but requires us to interpolate in each spatial dimension, which leads to a complexity of \(m^d\) for \(m\)-th order. Instead of interpolation we propose using quadrature on the kernel function represented with Green’s formula. Due to the fact that we are integrating only over the boundary, we save one spatial dimension compared to the interpolation method and get a complexity of \(m^{d-1}\).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Anderson, C.R.: An implementation of the fast multipole method without multipoles. SIAM J. Sci. Stat. Comput. 13, 923–947 (1992)

    Article  MATH  Google Scholar 

  2. Bebendorf, M.: Approximation of boundary element matrices. Numer. Math. 86(4), 565–589 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bebendorf, M., Rjasanow, S.: Adaptive low-rank approximation of collocation matrices. Computing 70(1), 1–24 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  4. Börm, S.: Efficient Numerical Methods for Non-local Operators: \({\mathcal H}^2\)-Matrix Compression, Algorithms and Analysis. EMS Tracts in Mathematics, vol. 14. EMS (2010)

  5. Börm, S., Grasedyck, L.: Low-rank approximation of integral operators by interpolation. Computing 72, 325–332 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  6. Börm, S., Grasedyck, L.: Hybrid cross approximation of integral operators. Numer. Math. 101, 221–249 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  7. Börm, S., Grasedyck, L., Hackbusch,W.: Introduction to hierarchical matrices with applications. Eng. Anal. Bound. Elem. 27, 405–422 (2003)

    Article  MATH  Google Scholar 

  8. Cheng, H., Gimbutas, Z., Martinsson, P.-G., Rokhlin, V.: On the compression of low rank matrices. SIAM J. Sci. Comput. 26(4), 1389–1404 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  9. Dahmen,W., Schneider, R.:Wavelets on manifolds I: construction and domain decomposition. SIAM J. Math. Anal. 31, 184–230 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  10. Goreinov, S.A., Tyrtyshnikov, E.E., Zamarashkin, N.L.: A theory of pseudoskeleton approximations. Linear Algebra Appl. 261, 1–22 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  11. Goreinov, S.A., Zamarashkin, N.L., Tyrtyshnikov, E.E.: Pseudo-skeleton approximations by matrices of maximal volume. Math. Notes 62, 515–519 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  12. Green, G.: An essay on the application of mathematical analysis to the theories of electricity and magnetism. Nottingham (1828)

  13. 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)

    Article  MathSciNet  MATH  Google Scholar 

  14. Greengard, L., Rokhlin, V.: A fast algorithm for particle simulations. J. Comput. Phys. 73, 325–348 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  15. Greengard, L., Rokhlin, V.: A new version of the fast multipole method for the laplace in three dimensions. In: Acta Numerica 1997, pp. 229–269. Cambridge University Press, Cambridge, MA (1997)

  16. Hackbusch, W.: Elliptic Differential Equations. Theory and Numerical Treatment. Springer-Verlag, Berlin (1992)

    MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  18. Hackbusch, W.: Hierarchische Matrizen—Algorithmen und Analysis. Springer, New York (2009)

    Book  MATH  Google Scholar 

  19. Hackbusch, W., Khoromskij, B.N.: A sparse matrix arithmetic based on \(\mathcal {H}\)-matrices. Part II: Application to multi-dimensional problems. Computing 64, 21–47 (2000)

    MathSciNet  MATH  Google Scholar 

  20. Hackbusch, W., Khoromskij, B.N., Sauter, S.A.: On \(\mathcal {H}^2\)-matrices. In: Bungartz, H., Hoppe, R., Zenger, C. (eds.) Lectures on Applied Mathematics, pp. 9–29. Springer-Verlag, Berlin (2000)

  21. Hackbusch, W., Nowak, Z.P.: On the fast matrix multiplication in the boundary element method by panel clustering. Numer. Math. 54, 463–491 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  22. Makino, J.: Yet another fast multipole method without multipoles—pseudoparticle multipole method. J. Comput. Phys. 151, 910–920 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  23. Martinsson, P.-G., Rokhlin, V.: A fast direct solver for boundary integral equations in two dimensions. J. Comput. Phys. 205, 1–23 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  24. Tyrtyshnikov, E.E.: Incomplete cross approximation in the mosaic-skeleton method. Computing 64, 367–380 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  25. Ying, L., Biros, G., Zorin, D.: A kernel-independent adaptive fast multipole algorithm in two and three dimensions. J. Comput. Phys. 196(2), 591–626 (2004)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Christian-Albrechts-Universität zu Kiel, Kiel, Schleswig-Holstein, Germany

    Steffen Börm & Jessica Gördes

Authors
  1. Steffen Börm
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jessica Gördes
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jessica Gördes.

Additional information

Part of this research was funded by the Deutsche Forschungsgemeinschaft in project BO 3289/2-1.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Börm, S., Gördes, J. Low-rank approximation of integral operators by using the Green formula and quadrature. Numer Algor 64, 567–592 (2013). https://doi.org/10.1007/s11075-012-9679-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-012-9679-2

Keywords

Search

Navigation