Timeline for Computing remainders modulo $\prod_{i\in S} (x-x_i)$ fast using FFT
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S May 1, 2018 at 21:11 | history | bounty ended | CommunityBot | ||
| S May 1, 2018 at 21:11 | history | notice removed | CommunityBot | ||
| Apr 24, 2018 at 12:30 | comment | added | Alin Tomescu | Computing $\prod _{j\neq i}(x-x_j),\forall i$ can be done in $O(n)$ time (for a fixed $x$). Computing $g'(x_i),\forall i$ takes $O(n^2)$ time, unfortunately. Even if that could be done faster (which is what I'm trying to do via FFT multipoint evaluation), computing $f(x_i),\forall i$ would still take $O(n^2)$ time (or can be sped up using FFT multipoint evaluation, which reduces to computing remainders fast). | |
| Apr 24, 2018 at 2:50 | comment | added | Venkataramana | Ah, too bad! I thought computing $\prod _{j\neq i}(x-x_j)$ and $, f(x_i), g'(x_i)$ may be easier. | |
| Apr 24, 2018 at 2:19 | comment | added | Alin Tomescu | Oh, I see. It's basically the Lagrange formula applied to $f(x) \bmod \prod (x-x_i)$. Never saw it stated in this way before. Thank you! Unfortunately, not sure how I can make use of it. The reason I'm asking about computing remainders fast is precisely because I want to speed up Lagrange interpolation itself. Computing your formula naively would take $O(n^2)$ time when $\deg{g} = n$. Computing it asymptotically faster reduces to computing remainders fast! | |
| Apr 24, 2018 at 2:07 | history | edited | Alin Tomescu | CC BY-SA 3.0 |
added 11 characters in body
|
| Apr 24, 2018 at 2:06 | comment | added | Venkataramana | In the first formula above I should have written $(\partial _i g)(x)$ and not $(\partial _i g)(x_i)$ | |
| Apr 24, 2018 at 2:00 | comment | added | Venkataramana | Thje product $g(x)=\prod (x-x_i)$ may be viewed as a function of $x,x_1,\cdots,x_n$ in $(n+1)$ variables. $(\partial _i g)(x)$ is the derivative with respect to the variable $x_i$ . | |
| Apr 24, 2018 at 1:58 | comment | added | Alin Tomescu | Thank you! Can you please clarify the $(\partial _i g)(x_i)$ notation? I'm assuming $g'(x_i)$ is the formal derivative of $g$ evaluated at $x_i$, but what is $(\partial _i g)(x_i)$? Is $\partial_i$ the $i$th Lagrange coefficient? Are you composing it with $g$? | |
| Apr 24, 2018 at 1:47 | comment | added | Venkataramana | If $g(x)=\prod (x-x_i)$ with $x_i$ all distinct, and $f$ is any polynomial, then the remainder of $f$ upon division by $g$ is (by Lagrange Interpolation) $$ \sum f(x_i) \frac{(\partial _i g)(x_i)}{g'(x_i)}.$$ I don't know if that is convenient to you. | |
| S Apr 23, 2018 at 19:36 | history | bounty started | Alin Tomescu | ||
| S Apr 23, 2018 at 19:36 | history | notice added | Alin Tomescu | Draw attention | |
| Apr 23, 2018 at 19:34 | history | edited | Alin Tomescu | CC BY-SA 3.0 |
added 188 characters in body
|
| Apr 18, 2018 at 18:40 | comment | added | Alin Tomescu | Thank you! I messed up but updated the post: The $x_i$'s can be an $\ell$th root of unity for some $\ell > k$ but they won't always be the $i$th $\ell$th root of unity. In other words, it's possible to have $x_1 = \omega^2, x_2 = \omega^5, x_3 = \omega^7, \dots$. | |
| Apr 18, 2018 at 18:36 | history | edited | Alin Tomescu | CC BY-SA 3.0 |
oops, clarified what the x_i's can be
|
| Apr 18, 2018 at 4:04 | comment | added | Max Alekseyev | If $x_i$ are the $k$-th power roots of unity, then $N(x)=x^k-1$ and $N'(x)=kx^{k-1}$ can be trivially evaluated at any point. | |
| Apr 18, 2018 at 3:03 | review | First posts | |||
| Apr 18, 2018 at 3:50 | |||||
| Apr 18, 2018 at 3:00 | history | asked | Alin Tomescu | CC BY-SA 3.0 |