Fast Multipole Method for Multivariable Integrals

We give a fast numerical algorithm to evaluate a class of multivariable integrals. A direct numerical evaluation of these integrals costs$N^m$, where m is the number of variables and N is the number of the quadrature points for each variable. For m = 2 and m = 3 and for only one-dimensional variable...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on numerical analysis 2005-01, Vol.42 (5), p.2098-2117
Main Authors: BOKANOWSKI, Olivier, LEMOU, Mohammed
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Charged particles
Children
Classical and quantum physics: mechanics and fields
Computer science
control theory
systems
Cost estimates
Exact sciences and technology
Integral equations
Integrals
Mathematical analysis
Mathematical integrals
Mathematics
Methods
Multipole expansion
Multipoles
Particle interactions
Physics
Sciences and techniques of general use
Theoretical computing
Theory of quantized fields
Total cost assessment
Total costs
Variables
Wave functions
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We give a fast numerical algorithm to evaluate a class of multivariable integrals. A direct numerical evaluation of these integrals costs$N^m$, where m is the number of variables and N is the number of the quadrature points for each variable. For m = 2 and m = 3 and for only one-dimensional variables, we present an algorithm which is able to reduce this cost from$N^m$to a cost of the order of$O((-\log \epsilon)^{\mu_m}N)$, where ε is the desired accuracy and μmis a constant that depends only on m. Then, we make some comments about possible extensions of such algorithms to number of variables m ≥ 4 and to higher dimensions. This recursive algorithm can be viewed as an extension of "fast multipole methods" to situations where the interactions between particles are more complex than the standard case of binary interactions. Numerical tests illustrating the efficiency and the limitation of this method are presented.
ISSN:0036-1429
1095-7170
DOI:10.1137/S0036142902409690