# Efficient algorithm for computing Vandermonde determinant

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 Is there an algorithm that computes this determinant more quickly than by trivially multiplying those $$O(n^2)$$ differences?

• See the on-line MDPI document entitled (somewhat strangely) "Recursive matrix calculation paradigm by the example of structured matrix" by Jerzy S. Respondek Commented Apr 6, 2020 at 16:08

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 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)$$