1
$\begingroup$

Let $P,Q$ two integral polynomials of height bounded by let say $H>0$ --- that is every coefficient of $p$ or $Q$ is bounded in absolute value by $H$ --- and degree at most $d$.

Let $A$ a set of $d$ reals.

I want to evaluate the sum: $$ S = \sum_{\alpha \in A} P(\alpha)Q(\alpha), $$ and more precisely I want to get the $n$ first bits of this value.

I can assert that this sum is bounded by a constant $K'>0$.

What would be the minimal number of bits of precision on the elements $\alpha\in A$ I need to be able to compute the $n$ first bits of $S$?

NB: The representation of the reals of $A$ can be whatever (fixed point, floating point, ... ) I'm able to efficiently compute them at arbitrary precision.

$\endgroup$
  • $\begingroup$ It might help to include a definition of the height of a polynomial in the question. $\endgroup$ – D.W. Oct 23 '17 at 5:56
1
$\begingroup$

I may be misunderstanding the question, but I don't think we have enough information to tell.

Consider, for example:

$$A = \left\{ \frac{1}{4}, \frac{1}{2}, \frac{3}{4} \right\}$$

and:

$$P(x) = \left( x - \frac{1}{4} - \varepsilon \right) \left( x - \frac{1}{2} + \varepsilon \right) \left( x - \frac{3}{4} - \varepsilon \right)$$ $$Q(x) = 1$$

for some small $\varepsilon$.

Assuming that $\varepsilon$ is small enough, both polynomials are height-bounded by 1.

The sum is:

$$S = - \frac{5}{16}\varepsilon + \varepsilon^3$$

The question is how you would evaluate $P$.

$$P(x) = \left(-\frac{3}{32} - \frac{5}{16}\varepsilon + \frac{1}{2}\varepsilon^2 + \varepsilon^3\right) + \left( \frac{11}{16} + \varepsilon - \varepsilon^2\right) x + \left(-\frac{3}{2} - \varepsilon\right) x^2 + x^3$$

The number of bits of precision on the elements of $A$ are not relevant here; they are precisely representable with two significant bits. It seems to me that the precision you need to do the intermediate computation is more important.

For a small enough $\varepsilon$, you are going to get catastrophic cancellation whether you use the factorised form of $P$ or you use a method such as Horner's rule. At the very least, you need enough bits to represent $-\frac{3}{32} - \frac{5}{16}\varepsilon$ such that you have $n$ significant bits in the $\varepsilon$ term, so you can subtract $-\frac{3}{32}$ to get a good enough answer.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I agree with you on the problem of "internal representation", but in your case, I have the impression that you consider that the coefficients of $P$ are approximated. Maybe I didn't make the point clear in the question, but $P$ and $Q$ are exactly known since they are integrals. $\endgroup$ – Sn0w Oct 23 '17 at 7:47
  • $\begingroup$ OK, that is important information. In numeric analysis, details matter, and I still think we probably don't have enough detail. $\endgroup$ – Pseudonym Oct 23 '17 at 23:02
  • $\begingroup$ It's the only pieces of information I have, unhopefully. $\endgroup$ – Sn0w Oct 24 '17 at 12:35

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.