Asymptotic complexity of 2D type 2 NUFFT

[unalmis]

Let $k_x$, $k_y$ be the number of complex Fourier modes in each direction. The asymptotic complexity of a 2D FFT from $k_x \times k_y$ frequency space grid onto denser $p_x \times p_y$ points grid with $p = p_x \times p_y \gg \min(k_x, k_y)$ reduces to
$$\mathcal{O}(p \log p)$$

What is the complexity of FINUFFT's implementation of the 2D type 2 NUFFT onto p non-uniform points?
A naive extrapolation of the complexity listed for the 1D type 1 NUFFT would imply
$$\mathcal{O}[p \log(p) + k_x k_y]$$

Is that the scaling or is it like
$$\mathcal{O}[p \log(p) \log(k_x k_y) + k_x k_y]$$

I could not find this information in the published references.

[unalmis]

I just edited the question to have more consistent notation.

[ahbarnett]

Hi - The cost is usual FFT plus linear in number of NU points - this is in the refs.

…

Sent from my iPod

On Sep 20, 2025, at 7:04 AM, Kaya Unalmis ***@***.***> wrote:  Closed #731 as resolved. — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you are subscribed to this thread.