An Accelerated Kernel-Independent Fast Multipole Method in One Dimension

Abstract

A version of the fast multipole method (FMM) is described for charge distributions on the line. Previously published schemes of this type relied either on analytical representations of the potentials to be evaluated (multipoles, Legendre expansions, Taylor series, etc.), or on the Singular Value Decomposition (SVD); in contrast, the algorithm of this paper utilizes the matrix compression scheme described in H. Cheng, Z. Gimbutas, P. G. Martinsson, and V. Rokhlin. "On the compression of low rank matrices" SIAM J. Sci. Comput. 26{4):1389-1404, 2005., resulting in substantial improvements in the CPU time requirements. Furthermore, the scheme of this paper is applicable to a wide variety of potentials; in this respect, it is similar to the SVD-based FMMs. The performance of the scheme is illustrated with several numerical examples.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 10, 2006
Accession Number
ADA639971

Entities

People

  • P. G. Martinsson
  • Vladimir Rokhlin

Organizations

  • Yale University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Applied Mathematics
  • Availability
  • Classification
  • Colorado
  • Compression
  • Contracts
  • Contrast
  • Decomposition
  • Information Operations
  • Instructions
  • Mathematics
  • Monitoring
  • Universities

Readers

  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Linear Algebra