fourier chebyshev interpolation

[unalmis]

Can Finnuft take advantage of cosine symmetry to compute sums of the following form?

$$ \text{Real} \left( \sum_{k_1 = -K_1}^{K_1} \sum_{k_2 = 0}^{K_2} c_{k_1 k_2} \exp(i k_1 x) \frac{\exp(i k_2 y) + \exp(-i k_2 y)}{2} \right) $$

Or must we evaluate by padding the spectral coefficients and computing a larger sum:

$$ \text{Real} \left( \sum_{k_1 = -K_1}^{K_1} \sum_{k_2 = -K_2}^{K_2} c_{k_1 k_2, \text{padded}} \exp(i k_1 x) \frac{\exp(i k_2 y)}{2} \right) $$

These sums are type 2 NUFFTs where $x$ and $y$ are non-uniform and real. $c_{k_1 k_2}$ is complex.

[ahbarnett]

Hello again,
We don't have any special versions for real transforms (that would have full Hermitian coeff symmetry in all dimensions). Not many NUFFT packages do, because of the explosion of new interfaces it causes (NonuniformFFTs.jl being an exception).

Unless K_2 is very big, the padded cost may not be much higher than the "ideal" transform size of (2K_1+1)*(K_2+1), because nonuniform point operations tend to dominate (unless you have K_1K_2 >> M, the number of NU pts). So, first I suggest you benchmark the two Fourier mode sizes in your setting.

Your transform is slightly odd in that it only has Hermitian symm in the y-direction, so would not even be covered by a real transform.

You may be able to use a pair (ntransf=2) of phase-shifted transforms as in your 2D code referred to here:
https://finufft.readthedocs.io/en/latest/tutorial/realinterp1d.html

I don't think there's any other tricks I can think of... Best, Alex

[unalmis]

Hi Alex,

Thank you, I suspected that but I just wanted to confirm. And yes, I can do the phase shifting so that the computation reduces to two separate transforms at the same non-uniform points.

Your transform is slightly odd in that it only has Hermitian symm in the y-direction, so would not even be covered by a real transform.

Both directions have the symmetry but I already phase shifted to match the API finufft supports in the x direction. In reality, I am computing

$$ \text{Real} \left( \sum_{k_1 = 0}^{K_1} \sum_{k_2 = 0}^{K_2} c_{k_1 k_2} \exp(i k_1 x) \frac{\exp(i k_2 y) + \exp(-i k_2 y)}{2} \right) $$

I'll likely just pad since spreading will probably dominate cost.