8
$\begingroup$

I am writing a piece of software and I'm trying to avoid root finding polynomials for efficiency purposes. I have two polynomials with complex coefficients, where the roots of both polynomials are known. In fact, the internal representation I use just stores the complex roots and a complex scaling factor, not the polynomial coefficients themselves, although it's trivial to compute these. Essentially, my goal is to sum the two polynomials and express the result in the same internal representation which I use for the addends. The mathematical challenge here is then to find the roots of the sum (and the scaling factor, which is trivial). As I've mentioned, I would very much like to find a way to do this more efficiently than just finding the coefficients of the sum and computing the roots from there - although I will resort to this method as a last resort if what I'm asking for isn't possible.

EDIT: I am putting a bounty on this question, so I want to clarify my standard for a good answer. A good answer will either:

  • Explain or overview an algorithm which accomplishes my task, preferably with references to relevant papers with more information.
  • Give an explanation for why the task is infeasible, possibly with references or suggestions for another angle of attack, but this is not necessary.
$\endgroup$
  • $\begingroup$ Vieta's formulas might help. Check out en.wikipedia.org/wiki/Vieta's_formulas. $\endgroup$ – SalmonKiller May 17 '16 at 18:26
  • 3
    $\begingroup$ There are results which can bound the location of the roots of $p(z)+q(z)$ given information about $p(z)$ and $q(z)$, the most notable of which is Rouché's theorem. Some other more advanced (and more complicated) results relevant to your question can be found in Marden's Geometry of Polynomials, section 17. There is very likely no result which will give you the exact locations of the roots of $p(z)+q(z)$. (...) $\endgroup$ – Antonio Vargas May 25 '16 at 1:40
  • 1
    $\begingroup$ (...) As Robert Israel's answer shows, at the very least there is no algebraic formula into which you can plug the roots of $p(z)$ and $q(z)$ and out of which come the roots of $p(z)+q(z)$. $\endgroup$ – Antonio Vargas May 25 '16 at 1:40
9
+50
$\begingroup$

There is no nice formula to get the roots of $P+Q$ from the roots of $P$ and of $Q$. For example, the roots of $x^5$ and $2x+1$ are easy to find, but the sum of these polynomials is $x^5 + 2 x + 1$, an irreducible quintic whose roots can't be expressed in radicals.

EDIT: In the case of a polynomial with three or four terms, we can express it as the sum of two polynomials with one or two terms, and then there is only trivial "additional information about the polynomials". Any "analytic method" is going to have to find roots of polynomials with three or four terms. And then once you have those roots, you can apply your "method" again to find roots of polynomials with five to eight terms...

$\endgroup$
  • $\begingroup$ Yes - there's no formula for roots of quintics. Yes - the roots that I will get cannot be expressed as radicals. However, this does not necessarily imply that there is not some analytic method (versus iterative method) to find the roots given my additional information about the polynomials. I know the roots of the addends. I'm not convinced without a more rigorous examination of the problem that I cannot use this information to my advantage. $\endgroup$ – Void Star May 24 '16 at 0:40
  • $\begingroup$ It's trivial to find the roots of a polynomial with one or two terms. This doesn't help in finding the roots of a polynomial with three terms! $\endgroup$ – Robert Israel May 24 '16 at 17:01
  • $\begingroup$ Yes, but what does that have to do with what I just said? $\endgroup$ – Void Star May 24 '16 at 17:03
  • 1
    $\begingroup$ So in the case of polynomials with three or four terms, there is only trivial "additional information about the polynomials". Any "analytic method" is going to have to find roots of polynomials with three or four terms. And then once you have those roots, you can apply your "method" again to find roots of polynomials with five or six terms... $\endgroup$ – Robert Israel May 24 '16 at 20:24
  • $\begingroup$ Ah, there it is. Thanks. $\endgroup$ – Void Star May 25 '16 at 7:29
0
$\begingroup$

My best guess would be that the way of finding the roots of the sums of polynomials would be a combination of both. You could use the fact that if your 2 polynomials $P \text{ and } Q$ have a common root $z$, then it's also the root of $P+Q$. Then you could use Vieta's formulas (https://en.wikipedia.org/wiki/Vieta's_formulas) to get some information about the sum of your new roots. From there, you could either use trial and error or some other method that I'm not aware of.

$\endgroup$
  • $\begingroup$ Unfortunately, for my application, P and Q are guaranteed not to have any common roots... But, I am pondering these Vieta's formulas. $\endgroup$ – Void Star May 18 '16 at 2:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.