A Fast Nonuniform Solver for the Poisson Equation over a Disk
Abstract
We study fast numerical methods for the Poisson equation on a disk within the FFTRR (Fast Fourier Transform Radial Recurrence) framework, which is built on Green's function representations. Classical FFTRR schemes apply FFTs in the azimuthal variable and evaluate mode-by-mode radial recurrences, achieving a complexity of O(MNlog N) on an N× M uniform grid. However, they require a uniformly spaced azimuthal mesh of N points. In this work we develop a Nonuniform (NUFFTRR) solver that admits nonuniform grids in both the radial and azimuthal directions while retaining the favorable structure of the original FFTRR formulation. The azimuthal analysis-synthesis step is implemented using either a dense NUDFT least-squares solver or one of two NUFFT-based iterative schemes: a Toeplitz solver using circulant-preconditioned conjugate gradients (PCG), and a preconditioned conjugate gradient for least squares (PCGLS) solver with Pipe--Menon density compensation. These yield azimuthal complexities O(N3 + MN2) for the NUDFT variant and O(Kiter MNlog N) for the NUFFT-based variants on an N× M grid and Krylov iteration count Kiter. Numerical experiments on nonuniform meshes demonstrate that the proposed method is robust, spectrally accurate in the azimuthal variable, and competitive in runtime with existing fast Poisson solvers. We make use of vectorization and batched BLAS/GPU-accelerated linear algebra operations to eliminate explicit loops while also formulating azimuthal and radial steps entirely in terms of dense array operations, FFTs, and NUFFTs, allowing for straightforward GPU acceleration. The implementation is released as an open-source Python package at https://github.com/CharliePyle4/NUFFTRR_Poisson, and its methodology can be extended directly to related elliptic problems such as the Helmholtz equation.
Related
- A Superfast Direct Solver for 2D Type-II Inverse Nonuniform Discrete Fourier Transform Based on Hierarchically Semiseparable Matrices
- Approximate matrix exponential: a fast and accurate solver for Markov kinetic models of ion channels.
- OptiXDE: A fast optical-inspired solver for differential equations
- Vectorial lattice Boltzmann solver for compressible inviscid flows with generic equation of state
- Analysis, thermodynamics, and a numerical solver for a pressure-temperature equilibrium closure of the four-equation model
BibTeX
@misc{pyle2026fast,
title = {{A Fast Nonuniform Solver for the Poisson Equation over a Disk}},
author = {Charlie Pyle and Prabir Daripa},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.40344},
eprint = {2609.40344},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40344},
}
RIS
TY - UNPB
TI - A Fast Nonuniform Solver for the Poisson Equation over a Disk
AU - Charlie Pyle
AU - Prabir Daripa
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2609.40344
UR - https://arxiv.org/abs/2609.40344
AB - We study fast numerical methods for the Poisson equation on a disk within the FFTRR (Fast Fourier Transform Radial Recurrence) framework, which is built on Green's function representations. Classical FFTRR schemes apply FFTs in the azimuthal variable and evaluate mode-by-mode radial recurrences, achieving a complexity of O(MNlog N) on an N× M uniform grid. However, they require a uniformly spaced azimuthal mesh of N points. In this work we develop a Nonuniform (NUFFTRR) solver that admits nonuniform grids in both the radial and azimuthal directions while retaining the favorable structure of the original FFTRR formulation. The azimuthal analysis-synthesis step is implemented using either a dense NUDFT least-squares solver or one of two NUFFT-based iterative schemes: a Toeplitz solver using circulant-preconditioned conjugate gradients (PCG), and a preconditioned conjugate gradient for least squares (PCGLS) solver with Pipe--Menon density compensation. These yield azimuthal complexities O(N^3 + MN^2) for the NUDFT variant and O(K_iter MNlog N) for the NUFFT-based variants on an N× M grid and Krylov iteration count K_iter. Numerical experiments on nonuniform meshes demonstrate that the proposed method is robust, spectrally accurate in the azimuthal variable, and competitive in runtime with existing fast Poisson solvers. We make use of vectorization and batched BLAS/GPU-accelerated linear algebra operations to eliminate explicit loops while also formulating azimuthal and radial steps entirely in terms of dense array operations, FFTs, and NUFFTs, allowing for straightforward GPU acceleration. The implementation is released as an open-source Python package at https://github.com/CharliePyle4/NUFFTRR_Poisson, and its methodology can be extended directly to related elliptic problems such as the Helmholtz equation.
ER -