Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

A Fast Direct Solver for a Class of Elliptic Partial Differential Equations

  • Published:
Journal of Scientific Computing Aims and scope Submit manuscript

Abstract

We describe a fast and robust method for solving the large sparse linear systems that arise upon the discretization of elliptic partial differential equations such as Laplace’s equation and the Helmholtz equation at low frequencies. While most existing fast schemes for this task rely on so called “iterative” solvers, the method described here solves the linear system directly (to within an arbitrary predefined accuracy). The method is described for the particular case of an operator defined on a square uniform grid, but can be generalized other geometries. For a grid containingN points, a single solve requiresO(Nlog 2N) arithmetic operations and\(O(\sqrt{N}\log N)\) storage. Storing the information required to perform additional solves rapidly requiresO(Nlog N) storage. The scheme is particularly efficient in situations involving domains that are loaded on the boundary only and where the solution is sought only on the boundary. In this environment, subsequent solves (after the first) can be performed in\(O(\sqrt{N}\log N)\) operations. The efficiency of the scheme is illustrated with numerical examples. For instance, a system of size 106×106 is directly solved to seven digits accuracy in four minutes on a 2.8 GHz P4 desktop PC.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Börm, S.:H2-matrix arithmetics in linear complexity. Computing77(1), 1–28 (2006)

    Article MATH MathSciNet  Google Scholar 

  2. Börm, S.: Approximation of solution operators of elliptic partial differential equations by H andH2-matrices. Tech. Report 85/2007, Max Planck Institute for Mathematics in the Sciences (2007)

  3. Chandrasekaran, S., Gu, M., Li, X.S., Xia, J.: Some fast algorithms for hierarchically semiseparable matrices. Private Communication (2007)

  4. Chandrasekaran, S., Gu, M., Li, X.S., Xia, J.: Superfast multifrontal method for structured linear systems of equations. Private Communication (2007)

  5. Chandrasekaran, S., Gu, M., Lyons, W.: A fast adaptive solver for hierarchically semiseparable representations. Calcolo42(3–4), 171–185 (2005)

    Article MATH MathSciNet  Google Scholar 

  6. Chandrasekaran, S., Gu, M., Pals, T.: A fast ULV decomposition solver for hierarchically semiseparable representations. SIAM J. Matrix Anal. Appl.28(3), 603–622 (2006). (Electronic)

    Article MATH MathSciNet  Google Scholar 

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

    Article MATH MathSciNet  Google Scholar 

  8. Grasedyck, L., Kriemann, R., Le Borne, S.: Domain-decomposition basedH-matrix preconditioners. In: Proceedings of DD16. LNSCE, vol. 55, pp. 661–668. Springer, Berlin (2006)

    Google Scholar 

  9. Hackbusch, W.: A sparse matrix arithmetic based onH-matrices. I. Introduction toH-matrices. Computing62(2), 89–108 (1999)

    Article MATH MathSciNet  Google Scholar 

  10. Hackbusch, W., Khoromskij, B., Sauter, S.A.: OnH2-matrices. In: Lectures on Applied Mathematics (Munich, 1999), pp. 9–29. Springer, Berlin (2000)

    Google Scholar 

  11. Hoffman, A.J., Martin, M.S., Rose, D.J.: Complexity bounds for regular finite difference and finite element grids. SIAM J. Numer. Anal.10, 364–369 (1973)

    Article MATH MathSciNet  Google Scholar 

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

    Article MATH MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Applied Mathematics, University of Colorado at Boulder, Boulder, CO, 80309-0526, USA

    Per-Gunnar Martinsson

Authors
  1. Per-Gunnar Martinsson

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toPer-Gunnar Martinsson.

Rights and permissions

About this article

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp