Timeline for Interpolating for particular coefficients
Current License: CC BY-SA 3.0
24 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 3, 2016 at 8:16 | vote | accept | Turbo | ||
| May 24, 2011 at 16:43 | vote | accept | Turbo | ||
| May 24, 2011 at 16:44 | |||||
| May 24, 2011 at 10:42 | answer | added | Emil Jeřábek | timeline score: 1 | |
| May 24, 2011 at 7:01 | answer | added | Federico Poloni | timeline score: 1 | |
| May 24, 2011 at 1:48 | history | edited | Turbo | CC BY-SA 3.0 |
added 483 characters in body
|
| May 24, 2011 at 1:43 | comment | added | Turbo | @Kevin: Say you have a polynomial of degree 3 (4 coeffcients). Evaluating at 1 and -1 and adding the results or subtracting the results, localizes the information into groups of two coefficients. My question could be can we localize further? Say I have $F(x) = A(x)B(x)$ where I know the polynomials $A(x)$ and $B(x)$ but do not know $F(x)$. I need to get only the mid coefficient of $F(x)$ while degrees of $A(x)$ and $B(x)$ are same. Can I get the mid-coefficient, by representing $A(x)$ and $B(x)$ differently? Remember: I can reduce the unknowns to half by evaluating $A(1),B(1),A(-1),B(-1)$. | |
| May 23, 2011 at 20:55 | comment | added | Kevin Buzzard | @unknown (google): in the non-symmetric case, if you evaluate your degree $2n$ polynomial $F$ at $2n$ integer points $a_1$, $a_2,\ldots,a_{2n}$ and you get zero each time, then all you know about $F$ is that it's $c\prod_i(X-a_i)$ for some integer $c$. In particular you definitely provably don't know any of the non-zero coefficients yet. To reduce the general case to this one consider the difference of two potential solutions. Isn't this a proof that you definitely need to do $2n+1$ evaluations to get one coefficient? [assuming it's non-zero...] | |
| May 23, 2011 at 18:53 | answer | added | Igor Rivin | timeline score: 0 | |
| May 23, 2011 at 18:40 | comment | added | Turbo | Hmm I am sure about the FFT wya to multiply. It gives all the coefficients. I am only seeking one coefficient. In that case may be there is a better approach. I can't believe one has to go through $O(n)$ computations to get one coefficient which is the same complexity as getting all the coefficients. | |
| May 23, 2011 at 18:36 | answer | added | Robert Israel | timeline score: 0 | |
| May 23, 2011 at 18:26 | answer | added | Aaron Meyerowitz | timeline score: 0 | |
| May 23, 2011 at 18:25 | comment | added | Emil Jeřábek | I see, so you are basically doing FFT multiplication. If the polynomials were real, then the values at any given set of $n-1$ points are insufficient to determine any single coefficient of the product (except for the constant coefficient, of course). The same holds for integer polynomials if the chosen points are rational. | |
| May 23, 2011 at 17:41 | comment | added | Turbo | I have two polynomials of degree $n-1$. I am interested in taking their product but discarding all but the mid coefficient. | |
| May 23, 2011 at 17:17 | comment | added | Emil Jeřábek | @unknown: What, exactly, do you get as the input of the algorithm? Are you only given access to evaluation of $F$ as a black box, or do you actually have some funky representation of $F$ at your disposal? | |
| May 23, 2011 at 17:11 | history | edited | Turbo | CC BY-SA 3.0 |
added 2 characters in body; deleted 1 characters in body
|
| May 23, 2011 at 17:01 | history | edited | Turbo | CC BY-SA 3.0 |
added 116 characters in body
|
| May 23, 2011 at 16:58 | comment | added | Turbo | @Kevin: VEry interesting answer but I bet the precision needed will scale $O(n^{1+\epsilon})$. | |
| May 23, 2011 at 16:54 | history | edited | Turbo | CC BY-SA 3.0 |
added 569 characters in body; added 41 characters in body; added 1 characters in body; deleted 2 characters in body
|
| May 23, 2011 at 16:48 | history | edited | Turbo | CC BY-SA 3.0 |
added 79 characters in body; added 2 characters in body
|
| May 23, 2011 at 16:34 | comment | added | Emil Jeřábek | @Kevin: $F(\pi)$ determines $F$ uniquely, and since its degree is known, I guess that an approximation with bounded precision is enough. But is there an efficient (i.e., faster than interpolating $2n$ values at integer points) algorithm to actually extract the coefficients from $F(\pi)$? | |
| May 23, 2011 at 16:26 | comment | added | Charles Matthews | Drat, 2n + 1 coefficients so I meant 2n. Why the O-notation? You might hope to get down to n + 1, which is what general position could give you. | |
| May 23, 2011 at 16:22 | comment | added | Charles Matthews | If you could get the top coefficient from evaluation at 2n - 1 points, you could actually then get all of them. So that can't work in general. On the other hand the symmetry of the coefficients is going to reduce the number of unknowns. | |
| May 23, 2011 at 16:15 | comment | added | Kevin Buzzard | If you evaluate $F$ at $\pi$ then you can figure out all of its coefficients from the answer! | |
| May 23, 2011 at 15:58 | history | asked | Turbo | CC BY-SA 3.0 |