Let $(x\_1 \ldots ,x\_n) \in \mathbb{R}^n$ and $f\_i = \Pi\_{j=1, j \neq i }^n ( x\_i - x\_j )$


I'm trying to evaluate $(f\_1, \ldots, f\_n)$. A trivial algorithm runs in $\mathcal{O}(n^2)$ but given the very specific form of the problem, there's got to be something faster. Maybe I've overlooked something simple, maybe a fourier transform is in order... What are your thoughts?



Fast (subquadratic) evaluation of a class of N degree polynomials over N points
The following may be of some help, if you haven't thought of it already. Let $V$ be the Vandermonde matrix with $(i,j)$th entry $x^{i-1}\_{j}$, $i,j=1,\ldots,n$. Its inverse $W$ has $(i,1)$th entry
$$
(-1)^{n} \frac{x\_1 \ldots x\_{i-1} x\_{i+1} … x\_n}{f\_i}.
$$
Hence, to find $f\_1,\ldots,f\_n$ we need to solve $V \alpha = e\_1$, where $e\_1=(1,0,\ldots,0)$. Thus, the question is, how fast can one solve a system of equations with a Vandermonde matrix? There's discussion on this topic in Nick Higham's book "Accuracy and stability of numerical algorithms" (see chpt 22). It appears that there are algorithms that are $O(n (log n)^2)$. However, it's noted that these may not be numerically stable or practical.


