FAST EXPANSION INTO HARMONICS ON THE BALL

Joe Kileel; Nicholas F. Marshall; Oscar Mickelin; Amit Singer

doi:10.1137/24M1668159

FAST EXPANSION INTO HARMONICS ON THE BALL

Joe Kileel, Nicholas F. Marshall, Oscar Mickelin, Amit Singer

Research output: Contribution to journal › Article › peer-review

Abstract

We devise fast and provably accurate algorithms to transform between an N × N × N Cartesian voxel representation of a three-dimensional function and its expansion into the ball harmonics, that is, the eigenbasis of the Dirichlet Laplacian on the unit ball in ℝ³. Given ℰ > 0, our algorithms achieve relative ℓ¹-ℓ^∞ accuracy ℰ in time O(N³(log N)² + N³|log ℰ|²), while the naive direct application of the expansion operators has time complexity O(N⁶). We illustrate our methods on numerical examples.

Original language	English (US)
Pages (from-to)	A1117-A1144
Journal	SIAM Journal on Scientific Computing
Volume	47
Issue number	2
DOIs	https://doi.org/10.1137/24M1668159
State	Published - 2025

All Science Journal Classification (ASJC) codes

Computational Mathematics
Applied Mathematics

Keywords

Laplacian eigenfunctions
fast transforms
spherical Bessel
spherical harmonics

Access to Document

10.1137/24M1668159

Cite this

@article{05b26a33f67c478287edf05725d68026,

title = "FAST EXPANSION INTO HARMONICS ON THE BALL",

abstract = "We devise fast and provably accurate algorithms to transform between an N × N × N Cartesian voxel representation of a three-dimensional function and its expansion into the ball harmonics, that is, the eigenbasis of the Dirichlet Laplacian on the unit ball in ℝ3. Given ℰ > 0, our algorithms achieve relative ℓ1-ℓ∞ accuracy ℰ in time O(N3(log N)2 + N3|log ℰ|2), while the naive direct application of the expansion operators has time complexity O(N6). We illustrate our methods on numerical examples.",

keywords = "Laplacian eigenfunctions, fast transforms, spherical Bessel, spherical harmonics",

author = "Joe Kileel and Marshall, \{Nicholas F.\} and Oscar Mickelin and Amit Singer",

note = "Publisher Copyright: Copyright {\textcopyright} by SIAM.",

year = "2025",

doi = "10.1137/24M1668159",

language = "English (US)",

volume = "47",

pages = "A1117--A1144",

journal = "SIAM Journal on Scientific Computing",

issn = "1064-8275",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - FAST EXPANSION INTO HARMONICS ON THE BALL

AU - Kileel, Joe

AU - Marshall, Nicholas F.

AU - Mickelin, Oscar

AU - Singer, Amit

PY - 2025

Y1 - 2025

N2 - We devise fast and provably accurate algorithms to transform between an N × N × N Cartesian voxel representation of a three-dimensional function and its expansion into the ball harmonics, that is, the eigenbasis of the Dirichlet Laplacian on the unit ball in ℝ3. Given ℰ > 0, our algorithms achieve relative ℓ1-ℓ∞ accuracy ℰ in time O(N3(log N)2 + N3|log ℰ|2), while the naive direct application of the expansion operators has time complexity O(N6). We illustrate our methods on numerical examples.

AB - We devise fast and provably accurate algorithms to transform between an N × N × N Cartesian voxel representation of a three-dimensional function and its expansion into the ball harmonics, that is, the eigenbasis of the Dirichlet Laplacian on the unit ball in ℝ3. Given ℰ > 0, our algorithms achieve relative ℓ1-ℓ∞ accuracy ℰ in time O(N3(log N)2 + N3|log ℰ|2), while the naive direct application of the expansion operators has time complexity O(N6). We illustrate our methods on numerical examples.

KW - Laplacian eigenfunctions

KW - fast transforms

KW - spherical Bessel

KW - spherical harmonics

UR - https://www.scopus.com/pages/publications/105002332413

UR - https://www.scopus.com/inward/citedby.url?scp=105002332413&partnerID=8YFLogxK

U2 - 10.1137/24M1668159

DO - 10.1137/24M1668159

M3 - Article

AN - SCOPUS:105002332413

SN - 1064-8275

VL - 47

SP - A1117-A1144

JO - SIAM Journal on Scientific Computing

JF - SIAM Journal on Scientific Computing

IS - 2

ER -

FAST EXPANSION INTO HARMONICS ON THE BALL

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this