Efficient algorithm for computing Vandermonde determinant

Question

The determinant of Vandermonde matrix $$V=\left[\begin{matrix} 1 & x_1 & x_1^2 & \cdots & x_1^{n-1} \\ 1 & x_2 & x_2^2 & \cdots & x_2^{n-1} \\ 1 & x_3 & x_3^2 & \cdots & x_3^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & \cdots & x_n^{n-1} \\ \end{matrix}\right]$$ can be represented as a product of pairwise differences between $x_i$s: $$\det(V)=\prod_{i<j}x_j-x_i.$$ Is there an algorithm that computes this determinant more quickly than by trivially multiplying those $O(n^2)$ differences?

Answer 1

In this answer, I will provide a sub-quadratic algorithm.

Assumptions & Definitions

• Let $\mathbb{F}$ be some field
• Let $M(n)$ be the cost of a polynomial multiplication algorithm over $\mathbb{F}.$ And suppose that : $$ 2M(\tfrac{n}{2}) \le M(n) $$

We will define $\Phi(x_1,\dots,x_n)$ as the determinant of the Vandermonde matrix $V:$ $$ V=\begin{pmatrix} 1 & x_1 & \dots & x_1^{n-1} \\ 1 & x_2 & \dots & x_2^{n-1} \\ \vdots & \vdots& \ddots &\vdots \\ 1& x_{n} & \dots & x_{n}^{n-1} \end{pmatrix} $$

---

Algorithm

• Let $n\in\mathbb{N},$ and let $m=\lfloor \tfrac{n}{2} \rfloor$

• Let $\boldsymbol{x}\in \mathbb{F}^n.$

• We will assume that $x_1,\dots,x_n$ are pairwise distinct as otherwise, $\Phi(\boldsymbol{x})=0.$

1. Recursion

We have the following: $$ \begin{align*} \Phi(\boldsymbol{x}) &= \prod_{1\le i<j \le n} x_j-x_i \\ &= \Phi(x_1,\dots,x_m) \times \Phi(x_{m+1},\dots,x_n) \times \prod_{i=1}^{m}\prod_{j=m+1}^{n}x_j-x_i \\ &=\Phi(\boldsymbol{x}') \times \Phi(\boldsymbol{x''}) \times \chi(\boldsymbol{x}',\boldsymbol{x''}) \end{align*} $$ Where $\boldsymbol{x}'=(x_1,\dots,x_m)$ and $\boldsymbol{x}''=(x_{m+1},\dots,x_n)$

2. Calculating $\chi$

Now we arrived to two recursive calculations of $\Phi$ plus one evaluation of the term: $$ \chi(\boldsymbol{x}',\boldsymbol{x}'')=\prod_{i=1}^{m}\prod_{j=m+1}^{n}x_j-x_i $$ This term has to be efficiently calculated to get a sub-quadratic complexity. Fortunately, This is in fact possible

To demonstrate this, We will define the polynomial $H$ as follows: $$ H(t)=\chi(\boldsymbol{x}',t)=\prod_{i=1}^{m}t-x_i $$ Now it is very clear that $\chi(\boldsymbol{x}',\boldsymbol{x}'') = \prod_{j=m+1}^{n} H(x_j).$ And with that, we only have to evaluate the polynomial $H$ at the $n-m$ points. This can be done in $\mathcal{O}(M(n) \log n)$ using fast multi-point evaluation

3. Complexity

Now, let $T_n$ the cost of Algorithm 1 at the worst-case scenario: $$ T_n = T_{m} + T_{n-m} + \mathcal{O}(M(n) \log n) $$

With that, we can easily deduce that: $$ T_n = \mathcal{O}\left(M(n)\cdot (\log n)^2\right) $$

If $\mathbb{F}$ allows a $\mathcal{O}(n \log n)$ polynomial multiplication algorithm (FFT-based), we get: $$ T_n= \mathcal{O}(n (\log n)^3) $$

---