How many multiplications are required for solving $P_N$ using Horner's rule?

[mathmari]

Hey!

In my book there is the following part about Multipoint Evaluation: The forward transform of evaluation-interpolation is multipoint polynomial evaluation over a field $F$. We shall focus our attention on the following

Problem $P_N$ of "size" $N$: Evaluate a polynomial $a(x)=\sum_{i=0}^{N-1}a_ix^i$ of "length" $N$ (length=degree+1) at each of a set $E_N=\{a_k\}_{k=0}^{N-1}$ of $N$ distinct points $a_k \in F$ (the "evaluation points").

The solution of $P_N$ is the collection of polynomial values $A_k=a(a_k)$ ($k=0, \dots , N-1$).

To analyze and compare algorithms for solving $P_N$, we shall count $M(N)$, the required number of multiplications over $F$. ($M(N)$ is a valid figure of merit, since multiplications dominate the arithmetic work of the algorithms to be discussed.)

To show off our more inspired solutions to $P_N$, we record the pedestrian
Proposition 1. For arbitrary evaluation points, $P_N$ can be solved in $M(N)=N^2+O(N)$.
Proof. Compute each $a(a_k)$ ($k=0, \dots , N-1$) by Horner's rule.
Could you explain to me the proposition? Why do we do $M(N)=N^2+O(N)$ multiplications when we apply Horner's rule?

Isn't the following the Horner's rule?

1.a<-0
2.i<-N-1
3.while (i>=0)
4.         a<-a_i+x*y
5.         i<-i-1

Do we not do $N$ multiplications? (Wondering)

 

[I like Serena]

Hi! (Smile)

Yep. That is Horner's rule.
It will actually do $N-1$ multiplications. (Wink)

The problem statement is not entirely clear to me, but it seems to say an length-N polynomial is evaluated for each of N distinct points.
Can you tell?
If so, that would make $M(N)=N(N-1)=N^2 + O(1)$. (Wasntme)

 

[mathmari]

The problem statement is not entirely clear to me, but it seems to say an length-N polynomial is evaluated for each of N distinct points.

Yes, it is like that.

If so, that would make $M(N)=N(N-1)=N^2 + O(1)$. (Wasntme)

So, it is $M(N)=N(N-1)=N^2-N=N^2+O(N)$ because for each point we do $N-1$ multiplications and we have $N$ points, right? (Wondering)

 

[I like Serena]

So, it is $M(N)=N(N-1)=N^2-N=N^2+O(N)$ because for each point we do $N-1$ multiplications and we have $N$ points, right? (Wondering)

That how I interpret it yes - depending on what is meant exactly with a "point". (Nod)

 

[mathmari]

depending on what is meant exactly with a "point"

What could be meant? (Wondering)

$a_k$ is an evaluation point of $F$, where $F$ is a field.

 

[I like Serena]

What could be meant? (Wondering)

$a_k$ is an evaluation point of $F$, where $F$ is a field.

I think a problem $P_N$ has as its inputs:

1. a polynomial $a(x)$ with coefficients $\alpha_0, ..., \alpha_{N-1}$ that are elements of $F$.
2. A set of elements $a_0, ..., a_{N-1}$ in $F$ called points.
   Each point is an element of $F$ and is used to be substituted for $x$ in the polynomial, which is why it's called an evaluation point.
   I think these points are intended to be different from the coefficients, which is why I wrote the coefficients using the alpha ($\alpha$) symbol.

Then the solution of the problem is the collection $a(a_0), ..., a(a_{N-1})$. (Wasntme)

 

[mathmari]

I think a problem $P_N$ has as its inputs:

1. a polynomial $a(x)$ with coefficients $\alpha_0, ..., \alpha_{N-1}$ that are elements of $F$.
2. A set of elements $a_0, ..., a_{N-1}$ in $F$ called points.
   Each point is an element of $F$ and is used to be substituted for $x$ in the polynomial, which is why it's called an evaluation point.
   I think these points are intended to be different from the coefficients, which is why I wrote the coefficients using the alpha ($\alpha$) symbol.

Then the solution of the problem is the collection $a(a_0), ..., a(a_{N-1})$. (Wasntme)

I see... (Nerd)

 

[mathmari]

After that we impose some structure on the evaluation points to speedup the solution to $P_N$.

Definition. Let $N=2n$ be even. A collectionn of $N$ distinct points $E_N=\{a_k\}_{k=0}^{N-1}$ is said to have Property $S$ if $E_N$ can be written as $E_N=\{\pm a_k\}_{k=0}^{n-1}$.
('S' thus stands for symmetry of sign; if $\beta$ is in $E_N$, then so is $-\beta$.)

Let $E_N$ have Property $S$. Then, since $(-\beta)^2=(+\beta)^2$, we see that only $\frac{N}{2}$ of the squares of points in $E_N$ are distinct. This little observation is the key to speeding up multipoint evaluation.

Proposition 2. Let $N$ be even, $N=2n$, and let $E_N=\{a_k\}_k$ have property $S$. Then $P_N$ can be solved in $M(N)=\frac{N^2}{2}+O(N)$.

(At the proof the Binary splitting scheme is used:

Step 1. Compute $\beta_k=a_k^2$ ($k=0, \dots , n-1$).

Step 2. With $b(y),c(y)$ given by $\alpha (x)=\sum_{i=0}^{N-1}\alpha_ix^i=b(y)+xc(y)$ where $y=x^2$, use Horner's rule to compute $B_k=b(\beta_k), C_k=c(\beta_k)$ ($k=0, \dots , n-1$).

Step 3. Return $A_k=B_k+a_kC_k, A_{-k}=B_k-a_kC_k$ ($k=0, \dots , n-1$).
)

To speed up also the solution to the two subproblems we make the leap to a very special class of evaluation points.

We refer to the $N$ distinct integral powers of a primitive $N$th root of unity $\omega$, $[\omega]=\{1, \omega , \dots , \omega^{N-1}\}$, as a set of $N$ Fourier points. These are the points that we shall choose fou our multipoint evaluation problem. (We shall shortly elucidate their connection with Fourier Transforms.) Let us call a multipoint evaluation problem $P_N$ at $N$ Fourier points a Fourier evaluation problem $F_N$ (of size $N$).

Lemma 1. Let $N=2n$, $\omega$ a primitive $N$th root of unity. Then the $N$ Fourier points $[\omega]$ have Property $S$, with $\omega^{k+n}=-\omega^k$ ($k=0, \dots , n-1$).

Consequence. We can apply the binary splitting scheme to solve a Fourier evaluation problem $F_N$.

Now for the crucial additional property of Fourier points that will let us speed up the solution to the subproblems arising in step 2 of the binary splitting scheme.

Lemma 2. Let $N=2n$, $\omega$ a primitive $N$th root of unity. Then $\omega^2$ is a primitive $\frac{N}{2}$th root of unity.

If we choose $N=2^m$, then the binary splitting scheme an be carried out (through $m$ levels of recursion) until a trivial problem is reached: the evaluation of a polynomial of length one at one point.

This lead to the abstract recursive FFT procedure of Algorithm for evaluationg a polynomial of length $N$ at $N$ Fourier points. [m]Algorithm (FFT - fast Fourier transform).

Input arguments.
$ \ \ $ integer $N=2^m$
$ \ \ $ polynomial $\alpha (x)=\sum_{i=0}^{N-1}\alpha_i x^i$
$ \ \ $ primitive $N$th root of unity $\omega$

Ouput argument.
$ \ \ $ array $\textbf{A}=(A_0, \dots , A_{N-1})$ where $A_k=\alpha(\omega^k)$

Auxiliary data.
$ \ \ $ integer $n=\frac{N}{2}$
$ \ \ $ polynomials $b(x)=\sum_{i=0}^{n-1}b_ix^i, c(x)=\sum_{i=0}^{n-1}c_ix^i$
$ \ \ $ arrays $\textbf{B}=(B_0, \dots , B_{n-1}), \textbf{C}=(C_0, \dots , C_{n-1})$[/m] [m]procedure FFT($N, \alpha (x), \omega , \textbf{A}$);
$ \ \ $ if N=1
$ \ \ \ \ $ then
$ \ \ \ \ \ \ \ \ $ {Basis.} $A_0 :=\alpha_0$
$ \ \ \ \ $ else
$ \ \ \ \ $ begin
$ \ \ \ \ \ \ \ \ $ {Binary split.}
$ \ \ \ \ \ \ \ \ \ \ $ $n:=\frac{N}{2};$
$ \ \ \ \ \ \ \ \ \ \ $ $b(x):=\sum_{i=0}^{n-1}\alpha_{2i}x^i;$
$ \ \ \ \ \ \ \ \ \ \ $ $c(x):=\sum_{i=0}^{n-1} \alpha_{2i+1}x^i;$
$ \ \ \ \ \ \ \ \ $ {Recursive calls.}
$ \ \ \ \ \ \ \ \ \ \ $ FFT($n, b(x), \omega^2, \textbf{B}$);
$ \ \ \ \ \ \ \ \ \ \ $ FFT($n, c(x), \omega^2 , \textbf{C}$);
$ \ \ \ \ \ \ \ \ $ {Combine.}
$ \ \ \ \ \ \ \ \ \ \ $ for $k:=0$ until $n-1$ do
$ \ \ \ \ \ \ \ \ \ \ $ begin
$ \ \ \ \ \ \ \ \ \ \ \ \ $ $A_k:=B_k+\omega^k \times C_k;$
$ \ \ \ \ \ \ \ \ \ \ \ \ $ $A_{k+n}:=B_b-\omega^k \times C_k$
$ \ \ \ \ \ \ \ \ \ \ $ end
end[/m] Why do we call $[\omega]$ the set of Fourier points?

I tried to implement the FFT algorithm at an example but I got stuck...

We have the polynmial $\alpha (x)=x^3+2x^2+5x+3$. ($N=2^2$)

[m]FFT($4, \alpha (x), \omega \textbf{A}$)
$ \ \ \ \ $ $n=2$
$ \ \ \ \ $ $b(x)=3+2x$
$ \ \ \ \ $ $c(x)=5+x$
$ \ \ \ \ $ FFT($2, b(x), \omega^2, \textbf{B}$)
$ \ \ \ \ \ \ \ \ $ $n=1$
$ \ \ \ \ \ \ \ \ $ $b(x)=3$
$ \ \ \ \ \ \ \ \ $ $c(x)=2$
$ \ \ \ \ \ \ \ \ $ FFT($1, b(x), \omega^2, \textbf{B}$)
$ \ \ \ \ \ \ \ \ \ \ \ \ $ $B_0=3$
$ \ \ \ \ \ \ \ \ $ FFT($1, c(x), \omega^2, \textbf{C}$)
$ \ \ \ \ \ \ \ \ \ \ \ \ $ $C_0=2$
$ \ \ \ \ \ \ \ \ $ $k=0$
$ \ \ \ \ \ \ \ \ \ \ \ \ $ $B_0=B_0+\omega^0 \cdot C_0=5$
$ \ \ \ \ \ \ \ \ \ \ \ \ $ $B_2=B_0-\omega^0 \cdot C_0=1$
$ \ \ \ \ \ \ \ \ $ $k=1$
$ \ \ \ \ \ \ \ \ \ \ \ \ $ $B_1=B_1+\omega^1 \cdot C_1$[/m]

Is it correct so far? (Wondering)

 

[I like Serena]

Why do we call $[\omega]$ the set of Fourier points?

Because it says:

We refer to the $N$ distinct integral powers of a primitive $N$th root of unity $\omega$, $[\omega]=\{1, \omega , \dots , \omega^{N-1}\}$, as a set of $N$ Fourier points.​

More specifically, the Fourier transform is $$A_n = \sum_{k=0}^{N-1} a_k e^{2\pi i n k / N} = \sum_{n=0}^{N-1} a_k \omega^{n k}$$.

I tried to implement the FFT algorithm at an example but I got stuck...

Is it correct so far? (Wondering)

I think it should be:

[m]FFT($4, \alpha (x), \omega, \textbf{A}$)
$ \ \ \ \ $ $n=2$
$ \ \ \ \ $ $b(x)=3+2x$
$ \ \ \ \ $ $c(x)=5+x$
$ \ \ \ \ $ FFT($2, b(x), \omega^2, \textbf{B}$)
$ \ \ \ \ \ \ \ \ $ $n=1$
$ \ \ \ \ \ \ \ \ $ $b(x)=3$
$ \ \ \ \ \ \ \ \ $ $c(x)=2$
$ \ \ \ \ \ \ \ \ $ FFT($1, b(x), \omega^4, \textbf{B'}$)
$ \ \ \ \ \ \ \ \ \ \ \ \ $ $B'_0=3$
$ \ \ \ \ \ \ \ \ $ FFT($1, c(x), \omega^4, \textbf{C'}$)
$ \ \ \ \ \ \ \ \ \ \ \ \ $ $C'_0=2$
$ \ \ \ \ \ \ \ \ $ $k=0$
$ \ \ \ \ \ \ \ \ \ \ \ \ $ $B_0=B'_0+(\omega^2)^0 \cdot C'_0=5$
$ \ \ \ \ \ \ \ \ \ \ \ \ $ $B_2=B'_0-(\omega^2)^0 \cdot C'_0=1$
$ \ \ \ \ \ \ \ \ $ $k=1$
$ \ \ \ \ \ \ \ \ \ \ \ \ $ $B_1=B'_0+(\omega^2)^1 \cdot C'_0 \\= 3 + (i^2)^1 \cdot 2 = 1$
[/m]

Note that $\omega$ is a primitive 4-root of unity, for which we'll pick $\omega=e^{i\pi/2} = i$.

 

[I like Serena]

We have the polynmial $\alpha (x)=x^3+2x^2+5x+3$. ($N=2^2$)

Oh, and we can verify by evaluating the Fourier transform: (Thinking)
$$A_n = \sum_{k=0}^{N-1} a_k\cdot i^{nk}$$
So:
\begin{cases}
A_0 &= \sum_{k=0}^{3} a_k\cdot i^{0\cdot k} &= \sum a_k &= 3+5+2+1 &= 11\\
A_1 &= \sum_{k=0}^{3} a_k\cdot i^{1\cdot k} &&= 3+5i-2-1i &= 3+4i\\
...
\end{cases}

Indeed it is the same as substituting respectively $x=1,i,-1,-i$ in $\alpha(x)$. (Mmm)