Timeline for Finding all roots of a polynomial
Current License: CC BY-SA 2.5
30 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 13, 2018 at 9:46 | answer | added | Denis Serre | timeline score: 5 | |
| Aug 13, 2018 at 1:39 | comment | added | David C. Ullrich | @JacquesCarette Regarding "As far as I know, none of the CASes actually implement that (it's much too slow)": The algorithm in my answer below is guaranteed to work. And I don't see why it should be slow. It's quite fast for tiny toy polynomials; I don't see why it should be much worse than linear in the degree... | |
| Aug 12, 2018 at 19:22 | answer | added | Gerald Edgar | timeline score: 0 | |
| Aug 9, 2018 at 16:12 | answer | added | David C. Ullrich | timeline score: 12 | |
| Jul 28, 2010 at 3:14 | answer | added | Clinton Curry | timeline score: 4 | |
| Jul 28, 2010 at 1:19 | answer | added | J. M. isn't a mathematician | timeline score: 3 | |
| May 7, 2010 at 16:43 | answer | added | timur | timeline score: 2 | |
| Apr 29, 2010 at 11:44 | answer | added | Roland Bacher | timeline score: 0 | |
| Apr 29, 2010 at 9:11 | comment | added | Zsbán Ambrus | I heard you could do this with Sturm Chains, which basically give you a definite way to find the number of positive real roots of a polynomial exactly. | |
| Apr 29, 2010 at 1:11 | comment | added | Jacques Carette | @Dror: dividing out by the root you found is known as 'deflation' as is amazingly badly behaved numerically. After you've deflated out about 10 roots, what you're left with is usually a total mess (from an error analysis point of view) and in practice the 'roots' you get after deflation are useless. | |
| Apr 29, 2010 at 1:03 | answer | added | lhf | timeline score: 1 | |
| 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 18:05 | vote | accept | Chris | ||
| Apr 1, 2010 at 18:05 | |||||
| Apr 1, 2010 at 13:18 | comment | added | damiano | Probably the reference meant that Dror meant was: Dierk Schleicher, "Newton's method as a dynamical system: efficient root finding of polynomials and the Riemann $\zeta$ function" in Holomorphic dynamics and renormalization, 213--224, Fields Inst. Commun., 53, Amer. Math. Soc., Providence, RI, 2008. | |
| Apr 1, 2010 at 10:55 | comment | added | user2734 | @Dror Speiser: Well, it's not the one implemented in Matlab :) www-math.mit.edu/~edelman/homepage/papers/companion.pdf | |
| Apr 1, 2010 at 10:26 | history | edited | Charles Stewart |
edited tags
|
|
| Apr 1, 2010 at 9:10 | comment | added | Dror Speiser | @XX: If it was not obvious, you reiterate Newton-Raphson after dividing by the root you found. This is practically the most common algorithm implemented in almost all computer packages as the default algorithm. Also, I remember hearing that in 2006 someone solved the problem of when the algorithm fails to converge, but I can't remember the article title. | |
| Apr 1, 2010 at 7:16 | comment | added | Pete L. Clark | Well, from a theoretical perspective, this follows from the decidability of the theory of the real numbers as an ordered field, as proved by Tarski. I agree of course that if you want an efficient algorithm, that's a separate question. | |
| Apr 1, 2010 at 6:36 | comment | added | Kevin Buzzard | @Jacques: point taken! I agree with you. | |
| Apr 1, 2010 at 4:08 | answer | added | Will Jagy | timeline score: 4 | |
| Apr 1, 2010 at 2:17 | comment | added | user1855 | Dror, Newton-Raphson is not guaranteed to converge. Even if it does, it finds only ONE solution. The question asked for ALL solutions. | |
| Mar 31, 2010 at 23:29 | comment | added | Dror Speiser | Am I the only one here who learned Newton-Raphson in high school? (Glendowie College, Auck, NZ - rules.) | |
| Mar 31, 2010 at 22:35 | answer | added | Victor Miller | timeline score: 6 | |
| Mar 31, 2010 at 21:47 | answer | added | user1855 | timeline score: 7 | |
| Mar 31, 2010 at 21:29 | comment | added | Jacques Carette | The fact that it's implemented doesn't mean it is solved! CASes have all sorts of routines which 'solve' undecidable problems... because all undecidable problems have (often large) sub-classes which are semi-decidable. It turns out that, for this problem, there is a complete algorithm which is guaranteed to terminate and find all roots. As far as I know, none of the CASes actually implement that (it's much too slow), instead they all implement algorithms which might fail (but with extremely low probability). | |
| Mar 31, 2010 at 20:53 | comment | added | Kevin Buzzard | The answer is "yes" and modern computer algebra systems have already done this for you. I confess I don't know how---but you don't make it clear whether you want to know how or you just want to know the answer. If you have a particular polynomial in mind, fire up the free maths package pari, set the precision to 1000 with \p 1000, and then use the polroots command. | |
| Mar 31, 2010 at 20:52 | answer | added | Ryan Williams | timeline score: 8 | |
| Mar 31, 2010 at 20:38 | answer | added | Qiaochu Yuan | timeline score: 16 | |
| Mar 31, 2010 at 20:30 | history | asked | Chris | CC BY-SA 2.5 |