A Generalized Fast Multipole Method for Non-Oscillatory Kernels

Abstract

We present a modification of the Fast Multipole Method (FMM) in two dimensions. While previous implementations of the FMM have been designed for harmonic kernels, our algorithm works for a large class of kernels that satisfy fairly general conditions, amounting to the kernel being sufficiently smooth away from the diagonal. Our algorithm approximates appropriately chosen parts of the kernel with "tensor products" of Legendre expansions and uses the Singular Value Decomposition (SVD) to compress the resulting representations. The obtained singular function expansions replace the Taylor and Laurent expansions used in the original FMM. The algorithm requires O(N) operations, and is stable and robust. The performance of the algorithm is illustrated with numerical examples.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 31, 2000
Accession Number
ADA640378

Entities

People

  • Vladimir Rokhlin
  • Z. Gimbutas

Organizations

  • Yale University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Availability
  • Classification
  • Computer Science
  • Computers
  • Contracts
  • Decomposition
  • Information Operations
  • Instructions
  • Monitoring
  • Potential Theory
  • Security
  • Standards
  • Universities

Fields of Study

  • Computer science

Readers

  • Calculus or Mathematical Analysis
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Linear Algebra