ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let AA be an odd or even associated Legendre transform matrix of size N×NN\times N, and let r(N)r(N) be the least upper bound for the ranks of the relevant non-oscillatory blocks and subblocks of the oscillatory portion of AA. The interpolative decomposition butterfly factorization has time and memory complexity O((r(N))2Nlog⁡2N)\mathcal{O}\left((r(N))^2N\log^2N\right). Rank-growth conjecture. The quantity (r(N))2(r(N))^2 grows as O(log⁡(N))\mathcal{O}\left(\log(N)\right). This conjecture is based on extensive numerical experiments. If true, the algorithm applies the associated Legendre transform in O(Nlog⁡3(N))\mathcal{O}\left(N\log^3(N)\right) operations and the spherical harmonic transform in O(N2log⁡3(N))\mathcal{O}\left(N^2\log^3(N)\right) operations, but no rigorous rank bound is supplied in the paper.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.