Source-linked AI summary
"Truncated Fourier Filtering" method for fast and high-order evaluation of integrals and convolutions in general domains
Oscar P. Bruno, Ambuj Pandey, Krishna Y. Poojara
TL;DR
The paper addresses fast, high-order evaluation of integrals and convolutions for discontinuous piecewise-smooth data on general multidimensional domains. It introduces TFF, which Fourier-approximates the domain characteristic function on an extended periodic domain and then applies Cartesian-grid trapezoidal quadrature. TFF achieves O(N) standard-integral and O(N log N) convolution costs after preprocessing, with superalgebraic convergence for sufficiently smooth data.
Problem
Trapezoidal-rule accuracy can degrade for non-periodic integrands and boundary-misaligned grids, while prior methods may fail for nonsmooth domain boundaries or densities that do not decay smoothly at the boundary.
Method
TFF replaces the integration-domain characteristic function with a truncated Fourier representation on an extended periodic domain and evaluates the resulting integrals by Cartesian-grid trapezoidal quadrature.
Results
For N points, TFF costs O(N) for standard integrals and O(N log N) for convolutions after one-time O(N log N) preprocessing, while sufficiently smooth data achieve superalgebraic convergence.
Takeaways & Limitations
TFF provides high-order evaluation for complex geometries and discontinuous integrands, including domains with corners, cusps, or other non-Lipschitz features.
Takeaways & Limitations
The theoretical contribution does not describe or analyze the more efficient FFT-based algorithm for computing characteristic-function Fourier coefficients, which is deferred to future implementation work.
Abstract
from arXiv · showhide
This paper introduces and analyzes a novel algorithm---Truncated Fourier Filtering (TFF)---for the fast, high-order accurate evaluation of standard integrals and convolutions involving piecewise-smooth (possibly discontinuous) integrands over general $m$-dimensional domains ($m \ge 1$) employing an $m$-dimensional Cartesian grid. For an $N$-point discretization, the method runs at a computational cost of $\mathcal{O}(N)$ operations for standard integrals and $\mathcal{O}(N \log N)$ operations for convolutions, following, in either case, a one-time $\mathcal{O}(N \log N)$ precomputation step (not required in dimension $m = 1$). The core idea underlying TFF is to approximate the characteristic function of the integration domain by a truncated Fourier expansion of it over a suitably extended periodic domain, and to evaluate the resulting integrals via trapezoidal quadrature on a Cartesian grid with an appropriately chosen discretization size. Despite its conceptual simplicity, TFF attains high-order accuracy even for complex, possibly non-smooth or even non-Lipschitz geometries. A complete theoretical analysis is provided that establishes the superalgebraic convergence (i.e., convergence faster than any negative power of $N$) of the overall approach.
1 Introduction
Truncated Fourier Filtering (TFF) targets fast, high-order integration and convolution on Cartesian grids for discontinuous integrands and complex domains. It replaces the domain characteristic function with a truncated Fourier representation, achieving favorable complexity and superalgebraic convergence under smooth-data conditions.
- Contribution: The method addresses standard and convolution integrals with piecewise-smooth, possibly discontinuous integrands over general m-dimensional domains.The targeted domains may have complex geometries and non-Lipschitz features such as corners, edges, and cusps.
- Contribution: TFF evaluates standard integrals in O(N) time and convolutions in O(N log N) time after one-time O(N log N) preprocessing, except in one dimension.The method uses an m-dimensional Cartesian grid and applies to general compact domains with piecewise-smooth boundaries, including corners and cusps.
- Method: TFF replaces the integration-domain characteristic function by a truncated Fourier expansion on an extended periodic domain and applies trapezoidal quadrature on a Cartesian grid.In one dimension, the original interval is embedded strictly inside a larger periodic interval before filtering and quadrature.
- Accuracy: TFF retains high-order accuracy for non-periodic integrands in dimensions m > 1, where prior trapezoidal-rule approaches may fail when densities do not decay smoothly at domain boundaries.The paper extends an earlier one-dimensional O(log F/F^3) result to piecewise-smooth functions on arbitrary m-dimensional domains.
- Accuracy: For smooth functions, the resulting algorithm converges superalgebraically despite the slow convergence of the Fourier series of the characteristic function.Superalgebraic convergence means that the error decays faster than any negative power of the discretization size N.
- Computational cost: Once the characteristic-function coefficients are precomputed, each new function requires O(N) work without a per-function FFT, supporting large-scale parallel implementation.A direct Fourier expansion of each periodic function would instead cost O(N log N) per function.
2 Integration via Truncated Fourier Filtering (TFF)
TFF evaluates integrals by replacing a domain characteristic function with a truncated Fourier expansion on an enclosing periodic rectangle, then applying Cartesian-grid trapezoidal quadrature. The construction extends to piecewise-smooth functions and achieves superalgebraic convergence under stated coefficient-accuracy and discretization conditions.
- Domain and function assumptions: TFF assumes compact domains decomposable into finitely many disjoint components with Lipschitz or suitably piecewise-smooth boundaries, including corners and cusps.The nonsmooth boundary set may have Hausdorff (m−1)-measure zero.
- Periodic extension: A smooth function on the domain is extended periodically to an enclosing hyper-rectangle, optionally using a window function that equals one on the domain and vanishes outside the rectangle.For piecewise-smooth functions, the construction applies the same procedure componentwise using smooth periodic extensions.
- TFF construction: The method substitutes each domain characteristic function with a truncated Fourier expansion and evaluates the resulting integral using the multidimensional trapezoidal rule on a Cartesian mesh.The Fourier coefficients must be computed accurately because their errors limit convergence.
- Accuracy: Superalgebraic convergence holds for smooth functions when Fourier coefficients are accurate and each truncation order F_r grows no faster than a fixed fraction of the corresponding grid resolution n_r.The theorem also establishes superalgebraic convergence for the broader piecewise-smooth setting.
- Piecewise-smooth extension: For piecewise-smooth functions, TFF decomposes the integral over domain components, extends each restricted function smoothly and periodically, and sums the componentwise approximations.Each component uses its own characteristic function and truncated Fourier expansion.
3 Convergence Analysis
The convergence analysis decomposes TFF error into Fourier truncation and trapezoidal-rule contributions, then bounds both under smooth periodic extensions and admissible piecewise-smooth geometries. These estimates establish superalgebraic decay of the total approximation error under the theorem’s discretization conditions.
- Fourier coefficient estimates: Smooth periodic extensions have Fourier coefficients that decay superalgebraically fast in the frequency index.This supplies the high-order decay needed for the truncation-error estimate.
- Total error: The total TFF error combines the truncation and quadrature estimates through the Fourier truncation range and grid-size parameters.The proof substitutes the separate bounds into the total-error decomposition.
- Fourier coefficient estimates: For compact domains with Lipschitz or piecewise-smooth, possibly non-Lipschitz boundaries, characteristic-function coefficients satisfy an inverse-frequency bound.The estimate is obtained using the divergence theorem and applies to geometries that may include singular boundary features.
- Trapezoidal-rule error: The trapezoidal-rule error is bounded for smooth periodic extensions when each truncation parameter satisfies F_r ≤ a n_r with 0 < a < 1.The bound holds for any integer p ≥ 2, supporting arbitrarily high algebraic orders in the discretization parameters.
- Main convergence theorem: For every positive integer p, the theorem bounds the total TFF approximation error by a corresponding inverse-power expression under F_r ≤ a n_r.If additionally 2 ≤ n_r/F_r ≤ M, the theorem provides the stated strengthened bound with constants independent of the discretization sizes.
4 Numerical Results
The numerical experiments report superalgebraic or spectral convergence for TFF integration and convolution, including discontinuous integrands and domains with corners or cusps, alongside the stated computational costs.
- Overall results: Superalgebraic convergence is observed for the integration and convolution experiments using Fourier coefficients computed by the divergence-theorem-based procedure.The experiments are described as confirming Theorem 1.
- Integration: Superalgebraic convergence is achieved for a piecewise smooth but discontinuous one-dimensional function, while the trapezoidal rule exhibits first-order convergence.The test uses K = [−1.2, 1.2] and R = [−1.5, 1.5].
- Integration: TFF maintains high-order convergence on a unit disc and an astroid, reaching machine precision at moderate resolutions and engineering accuracies with coarse discretizations.The astroid example uses a geometry with greater complexity than the disc.
- Integration: High-order convergence persists for the oscillatory integrand f3 with ω = 80 on the disc and astroid domains.This behavior is reported in Table 3.
- Convolutions: O(N log N) computational complexity and high-order convergence are confirmed for TFF convolution evaluations on disc and astroid domains.The reported convolution timings exclude precomputation for the characteristic-function Fourier coefficients.
- Fourier coefficients: Fourier-coefficient errors converge rapidly under mesh refinement and can approach machine precision for disc, rotated-square, and astroid geometries.The examples include smooth boundaries, corners, and cusps.
- Fourier coefficients: Measured coefficient-generation timings remain below the asymptotic O(N log N) growth over the tested range because auxiliary stages still dominate execution time.The FFT-dominated asymptotic regime is therefore not fully visible in these measurements.
B Window functions
The numerical experiments use a smooth ERFC-based window function that vanishes outside a prescribed interval and is controlled by a sharpness parameter. Although formally discontinuous, it is treated as infinitely differentiable up to a small tolerance.
- The experiments employ an ERFC-based complementary-error-function window.The window is specified piecewise near the interval endpoints.
- The window vanishes outside (α, β), with sharpness s constrained by 0 < s < β − α.
- ρ controls the discontinuity tolerance through the inverse error function, and the experiments use ρ = 5.805.
- Strictly speaking, the window is discontinuous rather than infinitely differentiable.It may be regarded as infinitely differentiable only up to a small tolerance.
- At the stated endpoint condition, α,β(β) equals 1.1 × 10^-16, described as half the IEEE 754 machine-precision tolerance.