5
$\begingroup$

I want to evaluate two polynomials $f$ and $g$ simultaneously, on the same input (in a computer program). These polynomial have only coefficients $0, 1, a , b$ and their degree is less than 700. I want to compute $f(x)$ and $g(x)$ simultaneously as efficiently as possible. I'm looking for an algorithms that say me how to do that.

For example, let $f(x) = ax^3 + bx^2 + x$ and $g(x) = x^3 + ax^2 + bx$. We have $f(x) = x^2(ax + b) + x$ and $g(x) = x(x^2) + x(ax+b)$. So we first compute $x^2$ and $ax+b$ and then use them to compute $f(x)$ and $g(x)$. Here, the optimization is evaluating $x^2$ and $ax+b$ one time for both $f$ and $g$.

Is there a algorithm that can show us how we should compute $f(x)$ and $g(x)$ in fewest computations (for a computer)? In other words, the algorithm should receive $f$ and $g$ as input and then return an algorithm for computing them.

I guess we can use algebra( some ring theory, ideal,...) or graph theory to model this problem.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Are the polynomials fixed (i.e., known beforehand and you need to compute them for many values of $x$)? Do they have some special properties? Again, this will affect the candidate algorithms. $\endgroup$ – vonbrand Jan 5 '16 at 21:40
  • $\begingroup$ OK, thanks. What do you mean by "compute $f$ and $g$ themselves"? I assume the input is the coefficients of $f$, the coefficients of $g$, and a value of $x$, and the desired output is the value of $f(x)$ and the value of $g(x)$. If that's not what you want, please edit the question to list what the inputs are and the desired outputs, and give an example (an example input and what output you'd want to see). Also, please do answer vonbrand's query as well... $\endgroup$ – D.W.♦ Jan 6 '16 at 6:03
  • $\begingroup$ They are sparse. In fact we should express $f$ and $g$ such that they can be computed faster for any $x$. We don't evaluate them for specific $x$. $\endgroup$ – user57 Jan 6 '16 at 6:14
  • 1
    $\begingroup$ Any references beyond Fallah/Hosangadi/Kastner, and comments why they don't fit the bill? $\endgroup$ – greybeard Jan 6 '16 at 9:38
  • $\begingroup$ I notice your recent edit removes the statement that the polynomials are sparse from the question. Was there a reason for this? (i.e., why did you revert my edit that added that clarification, based on your comment)? Has your interest changed to dense polynomials instead of sparse ones? $\endgroup$ – D.W.♦ Jan 10 '16 at 17:54

Your Answer

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

Browse other questions tagged or ask your own question.