Timeline for Finding all roots of a polynomial
Current License: CC BY-SA 4.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 10, 2018 at 17:53 | history | edited | Michael Hardy | CC BY-SA 4.0 |
added 6 characters in body
|
| Aug 10, 2018 at 17:43 | comment | added | David C. Ullrich | @AndrejBauer Good point. Except sometimes $|p(z)|$ small does imply there's a root nearby. See new and improved answer below... | |
| May 7, 2010 at 18:17 | comment | added | Pace Nielsen | @Qiaochu: I didn't notice that. Thank you. There are methods, in the more general case, that avoid the issue I brought up. But with integer coefficients, one can compute multiple zeros more easily. | |
| Apr 30, 2010 at 11:11 | comment | added | Roland Bacher | Another method to speed up things: Search (approximatively) all $2n$ zeroes of the real part of $f$ restricted to the circle of radius $\rho=R+1$ and follow these zeroes (meeting at zeroes of the derivative) by decreasing $\rho$ until hitting roots . | |
| Apr 29, 2010 at 19:47 | comment | added | Qiaochu Yuan | @Pace: the original problem specified integer coefficients. But I understand your concern. | |
| Apr 29, 2010 at 19:27 | comment | added | Pace Nielsen | @damiano: I imagine that the coefficients of the polynomial are not perfectly understood, and can only be computed to arbitrary accuracy. I believe that in that case it is impossible to prove that a polynomial is non-zero. Hence, it is impossible to tell if the gcd is non-constant. | |
| Apr 29, 2010 at 16:07 | comment | added | damiano | @Andrej Bauer: this is true, but maybe it can be fixed as follows. First, reduce to the case in which the roots are simple (by dividing by the gcd with the derivative). So now we know how many roots we are looking for. Fix a precision and start with Qiaochu's strategy. As you decrease the size of $\epsilon$, the sets (not nec connected) of squares will start zooming in on the set of zeros, leaving out the "far-away" regions where there is no zero. When you found an $\epsilon$ such that, within your precision, you only have $\deg(f)$ "basins" for your candidate roots, you stop. | |
| Apr 29, 2010 at 15:31 | comment | added | Qiaochu Yuan | Thanks, Andrej. Do you know if Dror's improvement avoids this problem? | |
| Apr 29, 2010 at 15:31 | history | edited | Qiaochu Yuan | CC BY-SA 2.5 |
added 74 characters in body
|
| Apr 29, 2010 at 11:59 | comment | added | Andrej Bauer | The proposed answer does not work. If the task is to list all the zeroes then the algorithm must decide which squares of side length $\epsilon$ contain zeroes and which do not. How is it supposed to do that? Just because an approximate value at a point in the mesh is close to zero does not mean there is an actual zero there. What you are proposing is to compute a sequence of nested compact sets (finite unions of squares) whose intersection is the set of zeroes. But the trouble is that some of the squares may "disappear" after a while, so it's hard to tell where the zeroes actuall are. | |
| Apr 1, 2010 at 18:05 | vote | accept | Chris | ||
| Apr 1, 2010 at 18:05 | vote | accept | Chris | ||
| Apr 1, 2010 at 18:05 | |||||
| Apr 1, 2010 at 14:00 | comment | added | Dror Speiser | A somewhat similar idea, due to Mike Meylan, follows: bound the circle in a square. Then, recursively, subdivide the square into 4 squares. Now approximately compute the argument principle integral around each square, and zoom in on any square that had a value larger than 0. This reduces the complexity dependence on $R$ from quadratic to linear. | |
| Mar 31, 2010 at 23:27 | comment | added | Dror Speiser | :) It really is terrible... | |
| Mar 31, 2010 at 23:04 | comment | added | Ryan Budney | To speed up your "Now subdivide..." argument you'd compute some Lipschitz bounds for the polynomial's derivative on your subdivisions and apply Kantorovich's theorem (using Newton's method to find the roots). In practice this is very fast. | |
| Mar 31, 2010 at 21:52 | history | edited | Qiaochu Yuan | CC BY-SA 2.5 |
deleted 24 characters in body
|
| Mar 31, 2010 at 21:45 | history | edited | Qiaochu Yuan | CC BY-SA 2.5 |
added 232 characters in body
|
| Mar 31, 2010 at 20:49 | history | edited | Qiaochu Yuan | CC BY-SA 2.5 |
added 9 characters in body
|
| Mar 31, 2010 at 20:44 | history | edited | Qiaochu Yuan | CC BY-SA 2.5 |
added 194 characters in body
|
| Mar 31, 2010 at 20:38 | history | answered | Qiaochu Yuan | CC BY-SA 2.5 |