本文介绍了Vandermonde矩阵的概念及其在多项式求值中的应用。Vandermonde矩阵可以将多项式的系数表示转换为其在一组点上的值表示，通过矩阵乘法实现多项式在多个点上的高效求值。文章以四次单位根为例，展示了如何简化Vandermonde矩阵的计算。
范德蒙矩阵 (Vandermonde matrix) 是一个将多项式从其系数表示 (coefficient representation) 转换为其在一组点上的值表示 (value representation) 的矩阵。
对于一个多项式，具有如下 系数表示：
范德蒙矩阵在 个不同的点上，将其作为一个单一操作进行计算。
将多项式视为矩阵乘法来计算
为简单起见，我们假设，那么我们有一个阶数为的多项式。
在单点求值
多项式在点的值为：
这可以写成矩阵乘积：将包含 的连续幂的 矩阵乘以多项式系数的向量，如下所示：
在两点求值
要在两个点，和 求值，我们可以将它们表示为两个单独的矩阵乘积。相反，我们将这些行向量堆叠成一个矩阵：
其中每一行分别包含 和 的连续幂。
因此，在两个点计算多项式等价于将矩阵乘以系数向量。
在个点求值
如果我们把点扩展到个点，那么，其中（假设已经成立），得到的方程组等价于将矩阵乘以系数向量：
这个矩阵被称为 范德蒙矩阵 (Vandermonde matrix)，表示为。
上面的等式可以简写为如下：
其中是多项式系数的向量，而是其点值的向量。
将多项式在 4 次单位根处求值作为矩阵乘积
现在，考虑在 4 次 单位根，而不是在任意个点处计算多项式 。我们得到的 范德蒙矩阵 (Vandermonde matrix) 如下：
我们可以通过利用 和 的属性来简化每个大于等于的项，如下所示：
现在我们将这些简化代入矩阵：
因此，矩阵简化为以下模式：
举一个具体的例子，是有限域中的一个本原 4 次单位根（其中算术模 17），范德蒙矩阵是：
[[ 1, 1, 1, 1 ],
[ 1, 4, 16, 13 ],
[ 1, 16, 1, 16 ],
[ 1, 13, 16, 4 ]]
结论
在一个阶数为 的多项式在个点处求值等价于将 范德蒙矩阵乘以系数向量，由等式形式化。
