The second-step complexity conjecture for multivariable Chebyshev subdivision
Statement
Let be the dimension and the degree. Consider a system of degree- Chebyshev polynomials in variables, and suppose that is sufficiently large. Second-step complexity conjecture. The cost of subdivision is greatest on the second step, whose complexity is times that of the first step. The complexity then decreases at an increasing rate, becoming cheaper at each step in the limit; consequently, the arithmetic complexity of the entire algorithm is
This conjecture is motivated by the predicted degree decrease and is supported by the numerical complexity data in the paper. It describes the expected dominant cost in the subdivision algorithm for sufficiently large degrees.
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.