Fourier Based Fast Multipole Method for the Helmholtz Equation

Abstract

The multilevel fast multipole method (MLFMM) is an algorithm that has had great success in reducing the computational time required to find the solution to the Galerkin boundary integral form of the Helmholtz equation. We present a new formulation of the MLFMM using Fourier basis functions rather than spherical harmonics in order to accelerate and simplify the time-critical stages of the algorithm. With modifications to the transfer function in the precomputation stage of the MLFMM, the interpolation and anterpolation algorithms become straightforward applications of FFT interpolations only. Using spectral methods, constructive algorithms are derived to determine a near-optimal quadrature for a given level in the algorithm and an a-priori estimate of the integration error.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 2008
Accession Number
ADA505797

Entities

People

  • C. Cecka
  • E. Darve

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Boundaries
  • Computations
  • Equations
  • Fourier Series
  • Frequency
  • Harmonics
  • Helmholtz Equations
  • Integrals
  • Interpolation
  • Plane Waves
  • Spherical Harmonics
  • Standards
  • Transfer Functions
  • Wave Equations
  • Wave Functions

Readers

  • Approximation Theory.
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)