- #1
mathmari
Gold Member
MHB
- 5,049
- 7
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?
Do we not do $N$ multiplications? (Wondering)
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?
Code:
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)