Bounding the roots of the sum of two polynomials

Question

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.

Or to put it more explicitly:

All functions $p_x(t)$ have a form like:

$p_x(t) = a_{n,x} * t^n + a_{n-1, x} * t^{n-1} + ... + a_{1,x} * t + a_{0,x}$

We can define $p_3(t) = p_1(t) + p_2(t)$

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.

Any ideas on how to approach the problem?

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.

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.

So I wanted to explore it from another direction and see if I can come up with something that works better.

Answer 1

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 $< 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.

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.

Answer 2

That's a strange question. The standard procedure for counting real roots in an interval is the Sturm Sequence, 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.

It would really help if you explained your motivations, because I feel I'm just guessing here.

Answer 3

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|<1/a,$ which is ensured by a condition on the coefficients of $Q$ (like here). 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.$

However, I share the very same feelings of slight perplexity as the other people who already answered.

Answer 4

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.

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.

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.

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.

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?

Gerhard "Ask Me About System Design" Paseman, 2010.10.08

Answer 5

drvitek's solution actually answers to your question, but the computations migth not be as simple as you hope.

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'$.

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).

If the set $\{ p_1(x_i)+p_2(y_j) \}$ takes only positive or only negative values there cannot be any root.

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):

Blockquote Solution: No matter what $p_1, p_2$ are always report "there migth be roots". This is either true, or false negative