Logarithmic rank-growth conjecture for interpolative decomposition butterfly factorization
Statement
Let be an odd or even associated Legendre transform matrix of size , and let be the least upper bound for the ranks of the relevant non-oscillatory blocks and subblocks of the oscillatory portion of . The interpolative decomposition butterfly factorization has time and memory complexity . Rank-growth conjecture. The quantity grows as . This conjecture is based on extensive numerical experiments. If true, the algorithm applies the associated Legendre transform in operations and the spherical harmonic transform in 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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.