Given a degree $n$ polynomial $f(x) = \sum_{i=0}^n a_i x^i, a_i \in \mathbb{R}$, and a constant vector $B \in \mathbb{R}^{n+1}$. The "evaluation" to my interest is $\langle A, B \rangle$, the inner product between the coefficient $A$ and the constant vector $B$.
Now instead of explicitly given $f$ or $A$, only a set of $n+1$ unique points $D := (x_0, f(x_0)), (x_1, f(x_1)), \cdots, (x_n, f(x_n))$ and $B$ are provided. Note, i can also choose $x_i$ to be nth root of unity or evenly spaced points in some range or any other coordinates to speed up the final "evaluation".
My question is how can i efficiently "evaluate" $f$ ? I can definitely run interpolation from $D$ to recover $A$ first, then evaluate the inner product. But I'm wondering if there are any better ways ?
Not sure if helps, there is another property in my setup, $B_i$ is $1/{n \choose i}$ the inverse of binomial coefficient.
There is a (slightly) better way. For each $j=0,1,\ldots,n$, let $\xi_j$ be the vector $(x_j^i)_{i=0}^{n} \in {\mathbb R}^{n+1}$. Note that $$\langle A,\xi_j\rangle=\sum_i a_i x_j^i= f(x_j) \,. $$ Write $B$ as a linear combination $$B=\sum_{j=0}^n \beta_j \xi_j$$ where $\beta_j$ are scalars. This is possible because the matrix $\Xi$ with columns $(\xi_j)$ for $j=0,\ldots,n$ is an invertible van der Monde matrix. (Algorithms for inverting such matrices have been studied extensively, see e.g. [1] and the references therein.) Solving a specific linear system is, in general, a bit faster than matrix inversion. Finally, $$\langle A,B \rangle =\sum_{j=0}^{n} \beta_j\langle A,\xi_j\rangle = \sum_{j=0}^{n} \beta_j f(x_j) \,.$$
[1] http://www.vesnik.math.rs/vol/mv19303.pdf