范德蒙矩阵

范德蒙矩阵 (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 ]]

结论

在一个阶数为 的多项式在个点处求值等价于将 范德蒙矩阵乘以系数向量，由等式形式化。

• 原文链接： rareskills.io/post/vande...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～