2D NUFFT: Row-Column Algorithm?

[stumarcus314]

For a 2D NUFFT of a matrix X, does FINUFFT use a row-column algorithm: first perform a 1D NUFFT of each column in X, call the result Y, and then perform a 1D NUFFT of each row of Y? Or does FINUFFT use an alternative optimized method?

[ahbarnett]

Hi Stu, It is a fully 2D method. In fact, it has to be, because a general set of NU pts in the square [0,2pi]^2 is not a Cartesian product of 1D NU coordinates, and your description would only help for the latter. It does not factorize like the 2D FFT. I suggest you write out the math of the 2D NUDFT definition to understand this... Best, Alex

…

On Sat, May 24, 2025 at 1:58 PM stumarcus314 ***@***.***> wrote: For a 2D NUFFT of a matrix X, does FINUFFT first perform a 1D NUFFT of each column in X, call the result Y, and then perform a 1D NUFFT of each row of Y? Or does FINUFFT use an alternative optimized method? — Reply to this email directly, view it on GitHub <#686>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACNZRSUYIBXRHXORHQLKS3L3ACXLJAVCNFSM6AAAAAB52ZOOH6VHI2DSMVQWIX3LMV43ERDJONRXK43TNFXW4OZYGM3DQOBZG4> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

-- *-------------------------------------------------------------------~^`^~._.~' |\ Alex Barnett Center for Computational Mathematics, Flatiron Institute | \ http://users.flatironinstitute.org/~ahb 646-876-5942