Bounding the roots of the sum of two polynomials - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T07:09:55Z http://mathoverflow.net/feeds/question/41473 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/41473/bounding-the-roots-of-the-sum-of-two-polynomials Bounding the roots of the sum of two polynomials Jay Lemmon 2010-10-08T00:51:44Z 2010-10-08T16:59:39Z <p>Suppose I have two polynomials with real coefficients. Suppose I can perform any sort of preprocessing on them I want. I want to be able to pre-emptively say that the sum of the polynomials doesn't have any roots inside a given interval without doing any explicit calculations on the sum itself. False positives (that is, saying there aren't any roots when there are some) would be deal-breaking, but false negatives (reporting there might be roots when there aren't) would be acceptable.</p> <p>Or to put it more explicitly:</p> <p>All functions $p_x(t)$ have a form like:</p> <p>$p_x(t) = a_{n,x} * t^n + a_{n-1, x} * t^{n-1} + ... + a_{1,x} * t + a_{0,x}$</p> <p>We can define $p_3(t) = p_1(t) + p_2(t)$</p> <p>I want to determine if $p_3(t)$ might have any roots inside a given interval $[t_{min}, t_{max}]$. But I want to do it only using properties of $p_1(t)$ and $p_2(t)$, their roots, etc. and not anything that would need me to calculate anything for $p_3(t)$, its roots, etc.</p> <p>Any ideas on how to approach the problem?</p> <p>EDIT: So some motivation of what I'm doing: I have a large set of polynomials that are related to the path of a point through space over time. I want to find polynomials that intersect sometime in the "near" future, but I don't want to have to do all $\frac{n*(n-1)}{2}$ polynomial-to-polynomial evaluations. So I'm trying to build a "broad phase" that only offers up pairs of polynomials to be solved in a "narrow phase" (ie: actual root finding) if they're "pretty close" to colliding. Whatever the algorithm for the broad phase is, it can't involve iterating over all the polynomial pairs or it defeats the point.</p> <p>One sort of square-peg-round-hole solution would be to use something like bounding boxes around the polynomials and use a spatial partitioning tree to find where boxes overlap, and then do the root finding on those. But it doesn't handle cases very well where the time interval of interest is quite large, or especially if one of the interval ends is infinity or negative infinity.</p> <p>So I wanted to explore it from another direction and see if I can come up with something that works better.</p> http://mathoverflow.net/questions/41473/bounding-the-roots-of-the-sum-of-two-polynomials/41476#41476 Answer by Thierry Zell for Bounding the roots of the sum of two polynomials Thierry Zell 2010-10-08T01:19:24Z 2010-10-08T01:19:24Z <p>That's a strange question. The standard procedure for counting real roots in an interval is the <a href="http://en.wikipedia.org/wiki/Sturm_sequence" rel="nofollow">Sturm Sequence</a>, which can be performed on $p_1$ and $p_2$ and it will be exact; but it involves derivatives, so if computing $p_3$ is a deal-breaker, I'm not sure if derivatives would be acceptable for you. </p> <p>It would really help if you explained your motivations, because I feel I'm just guessing here.</p> http://mathoverflow.net/questions/41473/bounding-the-roots-of-the-sum-of-two-polynomials/41477#41477 Answer by drvitek for Bounding the roots of the sum of two polynomials drvitek 2010-10-08T01:33:27Z 2010-10-08T01:33:27Z <p>You could test if $\min{|p_1(t)|} > \max{|p_2(t)|}$ (or the reverse) over the interval $[t_{min},t_{max}]$, but this looks to be harder than computing $p_3$. This is an odd question...</p> http://mathoverflow.net/questions/41473/bounding-the-roots-of-the-sum-of-two-polynomials/41486#41486 Answer by Pietro Majer for Bounding the roots of the sum of two polynomials Pietro Majer 2010-10-08T06:36:32Z 2010-10-08T06:51:58Z <p>A sufficient condition for a polynomial $P(t)$ of degree $n$ to have no roots in $[c-a,c+a],$ is that $Q(t):=t^n P(1/t-c)$ has all roots with $|t|&lt;1/a,$ which is ensured by a condition on the coefficients of $Q$ (like <a href="http://en.wikipedia.org/wiki/Fundamental_theorem_of_algebra#Bounds_on_the_zeroes_of_a_polynomial" rel="nofollow">here</a>). Of course, if $P=p_1+p_2$ one can easily write the condition in terms of the coefficients of $p_1$ and $p_2.$ </p> <p>However, I share the very same feelings of slight perplexity as the other people who already answered.</p> http://mathoverflow.net/questions/41473/bounding-the-roots-of-the-sum-of-two-polynomials/41491#41491 Answer by Gerhard Paseman for Bounding the roots of the sum of two polynomials Gerhard Paseman 2010-10-08T08:34:20Z 2010-10-08T08:34:20Z <p>One of the simplest tests to use is to compare the sign (using preprocessed values) of the quantity p_1(tmin) + p_2(tmin) with the sign of the quantity p_1(tmax) + p_2(tmax). If the signs are different, you have a root of p_3 in the interval.</p> <p>Variations on this involve essentially lower order approximations to p_1 and p_2 and essentially yield only true positives, not true negatives. The suggestions of other posters most likely give better guarantees against false negatives.</p> <p>The restrictions as well as the notion of preprocessing on p_1 and p_2 suggest to me one of the following: This is an interesting homework problem, and you want us to do the hard thinking for you; You are given p_1 and p_2 to such precision that roundoff error is a significant factor, and thus adding coefficients will introduce too much inaccuracy for you to get a good result; You are going to do this repeatedly, and thus adding the polynomials will be more expensive than encoding them and working with the encodings; You are actually trying to solve a much harder problem, and you think that solving this one will be useful in tackling the harder problem.</p> <p>There are other scenarios that I could suggest. If you are serious about receiving help on this problem, you should say why you cannot compute the sum and use that to determine the roots, while being allowed presumably unbounded preprocessing on the summands.</p> <p>While we wait for more information, a suggestion offered half in jest. Compute exp(p_1) and exp(p_2) and multiply them, then take the log of the result. Or is that what you are actually trying to do, invert some transform?</p> <p>Gerhard "Ask Me About System Design" Paseman, 2010.10.08</p> http://mathoverflow.net/questions/41473/bounding-the-roots-of-the-sum-of-two-polynomials/41510#41510 Answer by David Harris for Bounding the roots of the sum of two polynomials David Harris 2010-10-08T13:41:39Z 2010-10-08T13:41:39Z <p>The situation doesn't seem so perplexing to me. Suppose we have N polynomials $p_1, \dots, p_N$ and we want to find pairs of polynomials $p_i + p_j$ which have roots in the interval. We don't want to test all $O(N^2)$ pairs of polynomials; instead we want a simple criterion which can reject most of these pairs, hopefully in $&lt; N^2$ work. Even if the criterion requires testing all $N^2$ pairs of polynomials, we may at least be able to do something more simple than finding roots.</p> <p>If the test admits false positives, that is OK, because any pairs $p_i + p_j$ which pass the first test may be tested individually.</p> http://mathoverflow.net/questions/41473/bounding-the-roots-of-the-sum-of-two-polynomials/41519#41519 Answer by Nick S for Bounding the roots of the sum of two polynomials Nick S 2010-10-08T16:31:24Z 2010-10-08T16:31:24Z <p>drvitek's solution actually answers to your question, but the computations migth not be as simple as you hope.</p> <p>All you have to do is find all the roots $x_1,...,x_n$ of the derivative $p'_1$ and the roots $y_1,.., y_m$ of $p_2'$.</p> <p>If the set ${ p_1(x_i)+p_2(y_j) }$ takes both positive and negative values there could be roots (could be false positive).</p> <p>If the set ${ p_1(x_i)+p_2(y_j) }$ takes only positive or only negative values there cannot be any root.</p> <p>But the problem is too vague, you need to provide more details. By the way the following "solution" actually satistfies all your requerements (but it is definitelly not what your are looking for):</p> <blockquote> <p>Blockquote Solution: No matter what $p_1, p_2$ are always report "there migth be roots". This is either true, or false negative</p> </blockquote>