The Fast Gauss Transform

Abstract

Many problems in applied mathematics require the evaluation of the sum of N Gaussians at M points in space. The work required for direct evaluation grows like N M as N and M increase; this makes it very expensive to carry out such calculations on a large scale. In this paper, we present an algorithm which evaluates the sum of N Gaussians at M arbitrarily distributed points in C (dot) (N + M) work, where C depends only on the precision required. When N = M = 100, 000, our algorithm is several thousand times faster than direct evaluation. It is based on a divide and conquer strategy, combined with the manipulation of Hermite expansions and Taylor series. Keywords: Gauss transform; Hermite polynomials; Fast algorithms.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1989
Accession Number
ADA211287

Entities

People

  • J. Strain
  • L. Greengard

Organizations

  • Yale University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Boundary Value Problems
  • Boxes
  • Coefficients
  • Computational Complexity
  • Computer Science
  • Convolution
  • Equations
  • Far Field
  • Inequalities
  • Polynomials
  • Precision
  • Test And Evaluation
  • Truncation
  • Two Dimensional
  • Universities

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Statistical inference.

Technology Areas

  • Space