Fast Expansion Into Harmonics on the Ball

We devise fast and provably accurate algorithms to transform between an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>N</mml:mi> <mml:mo>×</mml:mo> <mml:mi>N</mml:mi> <mml:mo>×</mml:mo> <mml:mi>N</mml:mi></mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup><mml:mrow><mml:mi>R</mml:mi></mml:mrow> <mml:mrow><mml:mn>3</mml:mn></mml:mrow> </mml:msup> </mml:math> . Given <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ε</mml:mi> <mml:mo>></mml:mo> <mml:mn>0</mml:mn></mml:math> , our algorithms achieve relative <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup><mml:mrow><mml:mo>ℓ</mml:mo></mml:mrow> <mml:mrow><mml:mn>1</mml:mn></mml:mrow> </mml:msup> <mml:mo>-</mml:mo> <mml:msup><mml:mrow><mml:mo>ℓ</mml:mo></mml:mrow> <mml:mrow><mml:mi>∞</mml:mi></mml:mrow> </mml:msup> </mml:math> accuracy <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ε</mml:mi></mml:math> in time <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>𝒪</mml:mi> <mml:mo>(</mml:mo> <mml:mrow> <mml:msup><mml:mrow><mml:mi>N</mml:mi></mml:mrow> <mml:mrow><mml:mn>3</mml:mn></mml:mrow> </mml:msup> <mml:mo>(</mml:mo> <mml:mi>l</mml:mi> <mml:mi>o</mml:mi> <mml:mi>g</mml:mi> <mml:mspace></mml:mspace> <mml:mi>N</mml:mi> <mml:msup><mml:mrow><mml:mo>)</mml:mo></mml:mrow> <mml:mrow><mml:mn>2</mml:mn></mml:mrow> </mml:msup> <mml:mo>+</mml:mo> <mml:msup><mml:mrow><mml:mi>N</mml:mi></mml:mrow> <mml:mrow><mml:mn>3</mml:mn></mml:mrow> </mml:msup> <mml:mo>|</mml:mo> <mml:mi>l</mml:mi> <mml:mi>o</mml:mi> <mml:mi>g</mml:mi> <mml:mspace></mml:mspace> <mml:mi>ε</mml:mi> <mml:msup><mml:mrow><mml:mo>|</mml:mo></mml:mrow> <mml:mrow><mml:mn>2</mml:mn></mml:mrow> </mml:msup> </mml:mrow> <mml:mo>)</mml:mo></mml:math> , while the naive direct application of the expansion operators has time complexity <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>𝒪</mml:mi> <mml:mfenced> <mml:mrow> <mml:msup><mml:mrow><mml:mi>N</mml:mi></mml:mrow> <mml:mrow><mml:mn>6</mml:mn></mml:mrow> </mml:msup> </mml:mrow> </mml:mfenced> </mml:math> . We illustrate our methods on numerical examples.