Overview
Research focused on developing fast numerical methods for the Poisson equation within a disk geometry. The work introduces a Nonuniform (NUFFTRR) solver, expanding upon the established FFTRR (Fast Fourier Transform Radial Recurrence) framework. This NUFFTRR solver addresses a limitation of classical FFTRR schemes by enabling the use of nonuniform grids in both radial and azimuthal dimensions.
Research Context
Classical FFTRR schemes are designed to solve the Poisson equation on a disk. These schemes operate by applying Fast Fourier Transforms (FFTs) in the azimuthal variable and then evaluating radial recurrences mode-by-mode, resulting in a computational complexity of $O(MN\log N)$ for an $N \times M$ uniform grid. A key requirement for these classical methods is a uniformly spaced azimuthal mesh comprising $N$ points.
Approach
The developed NUFFTRR solver retains the structural characteristics of the original FFTRR formulation. It extends its applicability to nonuniform grids in both the radial and azimuthal directions. The azimuthal analysis-synthesis step, central to the method, is implemented using one of three distinct approaches:
- A dense NUDFT (Nonuniform Discrete Fourier Transform) least-squares solver.
- Two iterative schemes based on NUFFT (Nonuniform Fast Fourier Transform): a Toeplitz solver utilizing circulant-preconditioned conjugate gradients (PCG), and a preconditioned conjugate gradient for least squares (PCGLS) solver incorporating Pipe--Menon density compensation.
For an $N \times M$ grid, these implementations yield different azimuthal complexities:
- $O(N^3 + MN^2)$ for the NUDFT variant.
- $O(K_{\mathrm{iter}} MN\log N)$ for the NUFFT-based variants, where $K_{\mathrm{iter}}$ represents the Krylov iteration count.
The implementation incorporates vectorization and batched BLAS (Basic Linear Algebra Subprograms) or GPU-accelerated linear algebra operations to remove explicit loops. Both azimuthal and radial computational steps are formulated using dense array operations, FFTs, and NUFFTs. This design facilitates straightforward GPU acceleration.
Findings
Numerical experiments conducted on nonuniform meshes demonstrated specific attributes of the proposed method:
- It is robust.
- It exhibits spectral accuracy in the azimuthal variable.
- Its runtime is competitive with existing fast Poisson solvers.
Potential Applications
The methodology developed for the NUFFTRR solver can be directly extended to other related elliptic problems, such as the Helmholtz equation.
Implementation and Accessibility
The implementation of this NUFFTRR solver is released as an open-source Python package. It is available at https://github.com/CharliePyle4/NUFFTRR_Poisson.