Locally Corrected Multidimensional Quadrature Rules for Singular Functions
Author:
- John StrainJSJohn Strain
- 1 July 1995
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 16 (4) , 992-1017
Abstract
Accurate numerical integration of singular functions usually requires either adaptivity or product integration. Both interfere with fast summation techniques and thus hamper large-scale computations. This paper presents a method for computing highly accurate quadrature formulas for singular functions which combine well with fast summation methods. Given the singularity and the N nodes, we first construct weights which integrate smooth functions with order-k accuracy. Then we locally correct a small number of weights near the singularity, to achieve order-k accuracy on singular functions as well. The method is highly efficient and runs in $O(Nk^{2d} + N\log ^2 N)$ time and $O(k^{2d} + N)$ space. We derive precise error bounds and time estimates and confirm them with numerical results which demonstrate the accuracy and efficiency of the method in large-scale computations. As part of our implementation, we also construct a new adaptive multidimensional product Gauss quadrature routine with an effective error estimate, and compare it with a standard package. The approach generalizes to interpolate and differentiate scattered data and to integrate singular functions over curves and surfaces in several dimensions.
Keywords
This publication has 21 references indexed in Scilit:
- Numerical Integration1992
- An adaptive algorithm for the approximate calculation of multiple integralsACM Transactions on Mathematical Software, 1991
- The Fast Gauss TransformSIAM Journal on Scientific and Statistical Computing, 1991
- A fast algorithm for the evaluation of heat potentialsCommunications on Pure and Applied Mathematics, 1990
- Multilevel matrix multiplication and fast solution of integral equationsJournal of Computational Physics, 1990
- On the fast matrix multiplication in the boundary element method by panel clusteringNumerische Mathematik, 1989
- A Fast Adaptive Multipole Algorithm for Particle SimulationsSIAM Journal on Scientific and Statistical Computing, 1988
- A method of local corrections for computing the velocity field due to a distribution of vortex blobsJournal of Computational Physics, 1986
- The boundary problems of physical geodesyArchive for Rational Mechanics and Analysis, 1976
- Numerical study of slightly viscous flowJournal of Fluid Mechanics, 1973