ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let nn be the dimension and dd the degree. Consider a system of nn degree-dd Chebyshev polynomials in nn variables, and suppose that dd is sufficiently large. Second-step complexity conjecture. The cost of subdivision is greatest on the second step, whose complexity is 2n−1\sqrt{2}^{n-1} times that of the first step. The complexity then decreases at an increasing rate, becoming 50%50\% cheaper at each step in the limit; consequently, the arithmetic complexity of the entire algorithm is

O(ndn+12n−1).O(nd^{n+1}\sqrt{2}^{n-1}).

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 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.