pcfft documentation

PCFFT is a MATLAB library for fast N-body summation of translation-invariant kernels in \(\mathbb{R}^2\) and \(\mathbb{R}^3\). It can approximate sums of the form:

\[f(y_i) = \sum_{j=1}^N k(y_i, x_j) \mu_j, \tag{1}\]

\[g(y_i) = \sum_{j=1}^N \partial_{\boldsymbol{n}_i} \partial_{\boldsymbol{n}_j} k(y_i, x_j) \mu_j. \tag{2}\]

and more at a large number of source points \(x_j\) and target points \(y_i\) efficiently. The code is designed to be easy to use and adaptable to a wide range of kernels, allowing the user to rapidly prototype large-scale numerical computations. In particular:

• The method applies to a broad class of smooth translation-invariant kernels \(k(y, x) = k(y - x)\), not just kernels arising from the Green’s function of an elliptic PDE.

• Analytical knowledge of the Fourier transform of the kernel is not required.

• After a one-time precomputation step, the apply step uses Fast Fourier Transforms and sparse linear algebra, making it very fast for large problems.

The precorrected FFT method is ideal for when the sources and targets with a quasi-uniform distribution and will slow down if points are adaptively clustered.

Example usage 1 provides a brief introduction to using the package to evaluate sums of the form \((1)\), and Example usage 2 shows how to evaluate sums of the form \((2)\). More examples are being built at https://github.com/meliao/pcfft/tree/main/demos.

This package involves solving many poorly conditioned least squares problems. The warnings that this generates can be suppressed by running warning(‘off’,’MATLAB:rankDeficientMatrix’);.

Source repository

Available on GitHub at https://github.com/meliao/pcfft.

Installation and Dependencies

PCFFT can be installed from source:

git clone https://github.com/meliao/pcfft.git --recurse-submodules

The package depends on Kenneth Ho’s package FLAM, available at https://github.com/fastalgorithms/FLAM.

Contents:

• Example usage 1
• Example usage 2
• PCFFT API

Related work

The precorrected FFT algorithm was introduces in Phillips and White [PW97] and further developed to solve Laplace’s, Helmholtz’s, and Maxwell’s equations in Bruno and Kunyansky [BK01], Li et al. [LCF17], Nie et al. [NLYY02], Yan and Liu [YL11].

Recently, the authors of Askham et al. [AGH+25] used the proxy shell method to compute the equivalent grid charges, enabling this application of the precorrected FFT method to kernels that are not a Green’s function in the ambient space. A proof that the proxy shell method gives accurate results for kernels that are derivatives of logarithm in three dimensions is given in Goodwill et al. [GHGW26].

[AGH+25]

Travis Askham, Tristan Goodwill, Jeremy G. Hoskins, Peter Nekrasov, and Manas Rachh. Surface layers and linearized water waves: a boundary integral equation framework. arXiv preprint, October 2025. URL: http://arxiv.org/abs/2510.22748, doi:10.48550/arXiv.2510.22748.

[BK01]

Oscar P. Bruno and Leonid A. Kunyansky. A fast, high-order algorithm for the solution of surface scattering problems: basic implementation, tests, and applications. Journal of Computational Physics, 169(1):80–110, May 2001. doi:10.1006/jcph.2001.6714.

[GHGW26]

Tristan Goodwill, Jeremy Hoskins, Zydrunas Gimbutas, and Bowei Wu. A parametrix for the surface stokes equation. arXiv preprint arXiv:2602.20395, 2026.

[LCF17]

Weiwei Li, Wen Chen, and Zhuojia Fu. Precorrected-fft accelerated singular boundary method for large-scale three-dimensional potential problems. Communications in Computational Physics, 22(2):460–472, 2017.

[NLYY02]

Xiaochun Nie, Le-Wei Li, Ning Yuan, and Tat Soon Yeo. Fast analysis of scattering by arbitrarily shaped three-dimensional objects using the precorrected-fft method. Microwave and Optical Technology Letters, 34(6):438–442, 2002. doi:10.1002/mop.10488.

[PW97]

Joel R Phillips and Jacob K White. A precorrected-fft method for electrostatic analysis of complicated 3-D structures. IEEE Transactions on computer-aided design of integrated circuits and systems, 16(10):1059–1072, 1997.

[YL11]

Hongmei Yan and Yuming Liu. An efficient high-order boundary element method for nonlinear wave–wave and wave-body interactions. Journal of Computational Physics, 230(2):402–424, 2011.