Timeline for Analytic expression for the coefficient of a multivariate polynomial
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 31, 2022 at 0:38 | comment | added | Brendan McKay | I just multiplied the polynomials keeping only the terms needed. The $O(k^4)$ steps needed for particular $k=n$ gives all the answers for $k\le n$, so it isn't slower than $O(k^3)$ for each $k$ except by a constant. The method of summing over roots of unity modulo primes needs $O(k)$ small integers space and $O(k^4/\log k)$ operations (for one $k$). It has the advantage that all the operations are with small integers except for one application of CRT at the end, so it is hard to predict if it will be faster or slower. | |
| Mar 30, 2022 at 12:01 | comment | added | Peter Taylor | Actually, there is a further space-time tradeoff: by pushing in e.g. the sum over $t$ a precalculation in $O(k^3)$ bigint multiplications of a table of $O(k^2)$ values allows the main calculation to be reduced to $O(k^3)$ bigint multiplications. | |
| Mar 30, 2022 at 5:22 | comment | added | Brendan McKay | I also looked for a recurrence using 250 terms but no luck. | |
| Mar 29, 2022 at 22:00 | vote | accept | Fabius Wiesner | ||
| Mar 29, 2022 at 20:33 | history | answered | Peter Taylor | CC BY-SA 4.0 |