What is the fastest known algorithm for evaluating a homogeneous binary polynomial?

Question

This question was initially posted on math.stackexchange.com, but there is no appropriate answer, hence I have the right to publish it here again.

Let $f(x,y) = \sum_{i = 0}^d f_i x^i y^{d-i}$ be a homogeneous binary polynomial of degree $d \in \mathbb{N}$ over a field $k$. I want to evaluate $f$ at a point $P_0 = (x_0, y_0) \in k^2$. What is the fastest known algorithm (in the number of multiplications in $k$) to do that? It is well-known that the result $f(x_0, 1)$ can be found by means of Horner's scheme with $d$ multiplications in $k$. What about the point $P_0$ with the arbitrary value $y_0$? I see several simple ways to compute $f(x,y)$ with $3d$ multiplications in $k$. Is this the optimal solution in your opinion?

Answer 1

The question does not specify what is meant by “algorithm”, but based on the wording of both questions and the comments, I will assume you want to compute the polynomial by a division-free algebraic circuit (in variables $x$, $y$, $f_0,\dots,f_d$), and you measure complexity by the number of multiplication gates.

The bound can be improved to $$2d+O(\log d)$$ multiplications as follows:

• Precompute $x^{\lfloor(d+1)/2^i\rfloor}$, $x^{\lceil(d+1)/2^i\rceil}$, $y^{\lfloor(d+1)/2^i\rfloor}$, $y^{\lceil(d+1)/2^i\rceil}$ for $0<i<\log_2d$ with $O(\log d)$ multiplications by repeated squaring.

• Using the precomputed powers of $x$ and $y$, express the polynomial as $$f(x,y)=y^{\lceil(d+1)/2\rceil}g(x,y)+x^{\lfloor(d+1)/2\rfloor}h(x,y),$$ where $$\begin{align*} g(x,y)&=\sum_{i\le\lfloor(d-1)/2\rfloor}f_ix^iy^{\lfloor(d-1)/2\rfloor-i},\\ h(x,y)&=\sum_{i\le\lceil(d-1)/2\rceil}f_{\lfloor(d+1)/2\rfloor+i}x^iy^{\lceil(d-1)/2\rceil-i}. \end{align*}$$ Compute the polynomials $g$ and $h$ of degrees $\lfloor(d-1)/2\rfloor$ and $\lceil(d-1)/2\rceil$ recursively in the same way.

  We prove by induction on $d$ that this part takes $2d$ multiplications: the base case $d=0$ needs no multiplications, and for $d>0$, the recursive splitting requires $$2\lfloor(d-1)/2\rfloor+2\lceil(d-1)/2\rceil+2=2(d-1)+2=2d$$ multiplications using the induction hypothesis.