多线性多项式：生存工具包

lambdaclass
发布于 6天前
阅读 27

本文介绍了多线性多项式的基本性质，包括定义、插值、坐标和求值、张量化以及多线性多项式乘积等。重点介绍了如何通过在超立方体上进行求值来计算多线性多项式在多线性插值基下的坐标，并提出了用于判断多线性多项式是否包含特定变量的算法，包括分治法和最低有效位优先（LSB First）的步长方法。

## 介绍

在本文中，我们将简要介绍多线性多项式的一系列基本性质，记住这些性质对于处理 Bagad、Dao、Domb 和 Thaler 的一项非常有趣的工作将非常方便：“加速 SUM-CHECK 证明”。作者专注于 SUMCHECK 协议的特定设置，这在各种上下文中都很有用：他们将注意力缩小到 SUMCHECK 声明的多项式 gg 对象可以写成 dd 个多线性多项式的乘积的情况

$$g(X)=\prod_{k=1}^{d} p_{k}(X)$$

并着手设计一系列算法，调整它们的时间和内存使用量。在深入研究他们的发现之前，也许是时候回顾一下这些类型的多项式的一些事实，以供将来使用。

## 多线性多项式：定义和基本性质

对于本文的其余部分，固定一个域 kk。多线性多项式是指 ℓ≥0ℓ≥0 变量多项式 f∈k\[X1,…Xℓ\]f∈k\[X1,…Xℓ\]，使得它的每个单项式都具有以下特征：每个变量的幂要么是 0，要么是 1。这些多项式非常有用，并且以不同的形式出现在整个域论文献中，最近又作为 Ben Diamond 和 Jim Posen 的 BINIUS 工作中的有用对象重新出现。

我们将使用 Mk\[X1,…Xℓ\]Mk\[X1,…Xℓ\] 来表示所有具有 kk 中系数的 ℓℓ 变量的多线性多项式的集合。多线性多项式例子比比皆是：

$$p(X1,X2)=2+X1+X1X2,q(X1,X2,X3)=2x3+X1X2X3+X1X2,,etc$$

应该注意的是，ℓℓ 个不定元的多线性多项式的次数以 ℓℓ 为界；自然地，Mk\[X1,…Xℓ\]Mk\[X1,…Xℓ\] 是 k\[X1,…Xℓ\]k\[X1,…Xℓ\] 的向量子空间：它是关于加法和标量乘法封闭的。

### 插值

多线性多项式的一个重要特征是，它们允许以简洁的方式替换非常特殊域上的任意函数。开门见山地说，在超立方体 {0,1}ℓ{0,1}ℓ 上定义的**任意**函数 φφ 都可以用多线性多项式进行插值。发生这种情况是因为超立方体是离散的，它允许将函数 φφ 与其图像列表 φ(x):x∈{0,1}ℓφ(x):x∈{0,1}ℓ 标识，并且至关重要的是，对于超立方体中的每个 xx，我们都有一个多线性多项式，它在 xx 上取值 1，并在其他地方求值为零。

例如，取 b=(1,0,1,1)∈{0,1}4b=(1,0,1,1)∈{0,1}4。那么

$$χb(X1,X2,X3,X4)=X1(1−X2)X3X4$$

是一个多线性多项式，在 bb 上求值为 1，在其他地方求值为 0。一般来说，对于 b∈{0,1}ℓb∈{0,1}ℓ，具有此属性的多线性多项式可以表示为

$$χb(X)=\prod_{j=1}^{\ell}(bjXj+(1−bj)(1−Xj))$$

读者可能还记得一个变量中的拉格朗日插值以及满足这种条件的 polynomials)。在密码学中，这些有时被称为“相等多项式”，通常命名为 eq(x,y)eq(x,y)。那么这种插值特性是如何工作的呢？让我们举个例子。

假设我们有函数

$$φ(X1,X2)=(1+X1)(X1+X2)$$

就其本身而言，该多项式在 X1X1 中具有 2 次，因此它不是多线性多项式。但是，可以通过使用相等或拉格朗日多项式：χbχb（bb 在布尔正方形 {0,1}2{0,1}2 中）在立方体 {0,1}2{0,1}2 上对其进行插值。

$$φ(X1,X2)=\sum_{b∈\{0,1\}^{2}} g(b)χb(x)==φ(0,0)(1−X1)(1−X2)+φ(1,0)X1(1−X2)+φ(0,1)(1−X1)X2+φ(1,1)X1X2$$

其中这种相等在功能上被理解：它是布尔超立方体上两个函数的相等，其中一个是多线性多项式。在得意忘形之前，让我们陈述一个事实

**事实 1：** MℓMℓ 是一个维度为 2ℓ2ℓ 的向量空间，其基是拉格朗日多项式

$$Lℓ=\{χb:b∈\{0,1\}^{ℓ}\}$$

按照惯例，通过第一个 2ℓ2ℓ 非负整数的二进制展开获得维度 ℓℓ 超立方体的排序：如果 0≤m≤2ℓ−10≤m≤2ℓ−1，则

$$m=m020+m121+⋯mℓ−12ℓ−1mi∈{0,1}$$

我们将第 mm 个基多项式设置为字符串 (mℓ−1,…m1,m0)(mℓ−1,…m1,m0) 的相等多项式。这将是我们采用的拉格朗日基的排序以及我们将用来获取关键信息的顺序：标准二进制顺序。对于那些不熟悉的人：

1. **第一个变量** X1X1  与**最高有效位 (MSB)** 相关联。
2. **最后一个变量** XlXl 与**最低有效位 (LSB)** 相关联。

例如，对于一个 3 变量多项式 g(X1,X2,X3)g(X1,X2,X3)，超立方体坐标的排序如下：

| **超立方体点**（二进制表示） | **多项式坐标**(X1,X2,X3)(X1,X2,X3) |
| --- | --- |
| 0002=00002=0 | (0,0,0)(0,0,0) |
| 0012=10012=1 | (0,0,1)(0,0,1) |
| 0102=20102=2 | (0,1,0)(0,1,0) |
| …… | …… |
| 1112=71112=7 | (1,1,1)(1,1,1) |

不要烦恼，这只是在立方体中行走以及我们如何考虑插值基的选择。为了清楚起见：

1. 人们可以很容易地验证基

$$L2=\{(1−X1)(1−X2),(1−X1)X2,X1(1−X2),X1X2\}$$

以 kk 次基向量在 kk 的二进制表示上取值 1 并且在其他地方取值 0 的意义上对布尔超立方体进行插值。

2. M\[X1,X2,X3\]M\[X1,X2,X3\] 的基是通过简单地从左到右依次取 L2L2 中的每个向量，首先将其乘以 (1−X31−X3)，然后其次乘以 X3X3 获得。那么 L3L3 由集合组成

- (1−X1)(1−X2)(1−X3)(1−X1)(1−X2)(1−X3)
- (1−X1)(1−X2)X3(1−X1)(1−X2)X3
- (1−X1)X2(1−X3)(1−X1)X2(1−X3)
- (1−X1)X2X3(1−X1)X2X3
- X1(1−X2)(1−X3)X1(1−X2)(1−X3)
- X1(1−X2)X3X1(1−X2)X3
- X1X2(1−X3)X1X2(1−X3)
- X1X2X3X1X2X3

以这种特定顺序。

### 坐标和求值：黄金纽带

我们刚刚在前一节中讨论的内容已经将多线性多项式及其基与其他集合置于不同的基础上。例如，在线性代数中，将向量表示为基集的线性组合涉及构建（和求解!）一个线性方程组。尽管我们非常喜欢线性方程组，但是找到向量的坐标需要求解系统，这会明显花费时间和内存。因此，某些基比其他基更受欢迎：找到向量的坐标应该尽可能容易。

具体来说，如果我们想将 v=(2,3)v=(2,3) 表示为 (1,2)(1,2) 和 (5,−7)(5,−7) 的组合，我们将需要首先构建一个方程组，然后其次，解决它处理涉及的所有数值复杂性（这是一个小例子，但考虑具有 21282128 个元素的向量......）。

如果现在我们想要使用的向量是 (1,0)(1,0) 和 (0,1)(0,1)（规范基），结果将完全不同。现在这个问题几乎可以通过观察或直接评估 vv 的内容来轻松解决：

$$v=2⋅(1,0)+3⋅(0,1)$$

> 这正是我们与相等多项式的情况：现在此基中的坐标只是我们想要插值的函数的求值。这是个好消息，因为计算机喜欢求值。

这个对话产生了

> **事实 2：** 在布尔超立方体 {0,1}ℓ{0,1}ℓ 上定义的函数 ff 相对于拉格朗日基 LℓLℓ 的坐标只是其求值：

$$coords(f)=[f(b)]_{b∈\{0,1\}^{ℓ}}$$

例如，对于多线性多项式

$$g(X1,X2)=1+X1+X1X2$$

那么它在插值基中的坐标只是

$$g⟷coords(g)=[1,1,2,3]=[g(0),g(1),g(2),g(3)]$$

我们利用了立方体的排序，并且随意地“在整数 0≤n≤22−10≤n≤22−1 处评估 gg”。

### 在这种情况下的张量化

我们在高中学习的多项式运算之一是多项式乘法：例如，当给定多项式

$$X+1 和 2+Y$$

我们使用分配律计算它们的乘积，并列不定元并使用幂来缩写并列的相等符号：

$$(X+1)(2+Y)=2X+XY+2+Y$$

并假设单项式中符号的顺序无关紧要。当将多项式视为向量时，我们需要一种形式来描述这种精确的运算。这种形式称为张量积，它允许向量乘法，正如我们所知; 研究张量积的领域称为多线性代数，并且显然是线性代数的哥哥。向量 v∈Vv∈V 和 w∈Ww∈W 的张量积的常用符号是

$$v⊗w∈V⊗W$$

我们注意到 V⊗WV⊗W 是一个新的向量空间，由 VV 和 WW 构建，显然称为它们的张量积。此乘积具有我们想要抽象的所有属性，分配律对于我们的需求至关重要：

$$v⊗w+2v.u⊗w=(3v+u)⊗w$$

所有这些在我们的设置中都很自然：如果我们将 VV 设置为在不定元 X1X1 中次数最多为 1 的多项式的向量空间，并将 WW 设置为在不定元 X2X2 中次数最多为 1 的多项式的向量空间，则

$$V⊗W=M[X1]⊗M[X2]=M2[X1,X2]$$

更重要的是，对基的张量积会产生张量积的基。一般理论保证，每当 BB 和 CC 分别是 VV 和 WW 的基时，则

$$B⊗C={vi⊗wj:1≤i≤dim(V),1≤j≤dim(W)}$$

是新向量空间的基。但是，必须为这些向量选择顺序。为了我们的利益，以与二进制展开兼容的方式对基向量的张量积进行排序是很方便的；在 dim(V)=dim(W)=2dim(V)=dim(W)=2 的情况下，我们将要看的基很简单

$$B⊗C=v1⊗w1,v1⊗w2,v2⊗w1,v2⊗w2$$

通常称为字典顺序。从这个意义上讲，这个基工作得很好：假设你选择 z∈V⊗Wz∈V⊗W 例如

$$z=2(v1⊗w1)+5(v1⊗w2)+3(v2⊗w1)−1(v2⊗w2)$$

它的坐标向量结果是 \[2,5,3,−1\]\[2,5,3,−1\]。此外，由于张量与分配律兼容，因此我们允许重新组合这些项：

$$z=(2w1+5w2)⊗v1+(3w1−1w2)⊗v2$$

该组合的系数是 VV 的以下元素：

- **v1v1 的系数**：c1=2w1+5w2c1=2w1+5w2
- **v2v2 的系数**：c2=3w1−1w2c2=3w1−1w2

这些系数，用为 WW 选择的基的坐标表示，就是 \[2,5\]\[2,5\] 和 \[3,−1\]\[3,−1\]。选择张量基的顺序是为了重现以下事实：

$$concat(coords(c1),coords(c2))=concat([2,5],[3,−1])=[2,5,3,−1]$$

在多线性多项式的上下文中，此讨论清楚地表明，可以通过递归地张量化不同变量中次数最多为 1 的多项式的向量空间来获得这些多项式：我们具有多线性多项式向量空间的代数特征

$$Mℓ[X1,…Xℓ]=Mℓ[X1,…Xℓ−1]⨂M[Xℓ]$$

而且，利用张量积的结合律，我们得出一个非常自然的事实：

> **事实 3：** 设 {1,2,…,ℓ}=J⋃I{1,2,…,ℓ}=J⋃I (J,I 为不相交集合)。那么具有不定元 X1,…XℓX1,…Xℓ 的多线性多项式可以被视为具有不定元 Xj∈JXj∈J 的多线性多项式，并且系数是不定元 Xi∈IXi∈I 中的多线性多项式。

为了固定这个想法，请看一下多项式

$$h=X1+X1X3+2X2X3X4+2X4$$

由于它们最多升为 1 次幂，因此这自然是 X3X3 和 X4X4 中的多线性多项式。使用变量 X3X3 和 X4X4 中的多线性多项式的拉格朗日基

$$\{(1−X3)(1−X4),(1−X3)X4,X3(1−X4),X3X4\}$$

我们利用我们已经讨论的内容找到相应的系数：系数将是剩余变量 X1X1 和 X2X2 中的多项式，通过在 X3X3 和 X4X4 的超立方体的四个点处评估原始多项式 hh 获得。

- **(1−X3)(1−X4)(1−X3)(1−X4) 的系数：** 我们在 (X3=0,X4=0)(X3=0,X4=0) 处评估 hh。

$$h(X1,X2,0,0)=X1+X1(0)+2X2(0)(0)+2(0)=X1$$

这是第一个基多项式的系数。
- **(1−X3)X4(1−X3)X4 的系数：** 我们在 (X3=0,X4=1)(X3=0,X4=1) 处评估 hh。

$$h(X1,X2,0,1)=X1+X1(0)+2X2(0)(1)+2(1)=X1+2$$

这是第二个基多项式的系数。
- **X3(1−X4)X3(1−X4) 的系数：** 我们在 (X3=1,X4=0)(X3=1,X4=0) 处评估 hh。

$$h(X1,X2,1,0)=X1+X1(1)+2X2(1)(0)+2(0)=X1+X1=2X1$$

这是第三个基多项式的系数。
- **X3X4X3X4 的系数：** 我们在 (X3=1,X4=1)(X3=1,X4=1) 处评估 hh。

$$h(X1,X2,1,1)=X1+X1(1)+2X2(1)(1)+2(1)=X1+X1+2X2+2=2X1+2X2+2$$

这是第四个基多项式的系数。

总之，hh 的坐标被视为变量 X3X3 和 XrXr 中的多线性多项式很简单

$$[X1,2+X1,2X1,2+2X1+2X2]$$

正如读者可能已经在考虑的那样“但是我们也可以计算坐标的坐标”，是的，这就是我们将要进行的：一种递归算法来生成多线性多项式的坐标，或者以不同的视角来看：一种使用求值字符串的协议。

> **事实 4：** 同样，在某些变量的子集中评估多线性多项式会产生剩余变量中的多线性多项式。

## 多线性插值的冒险

我们刚刚讨论的内容可以看作是**多线性插值**的一个案例。通过 ℓℓ 个变量中的多线性多项式的插值基的性质，如果以有组织的方式处理，可以迭代此过程并有效地计算坐标。

### 算法：MultilinearCoordinates/ InterpolationBasis(g, l)

此算法采用 ll 个变量中的多线性多项式 gg，并返回一个 2l2l 坐标的向量，该向量表示多线性插值基中的 gg。

1. **基本情况：**
   - **如果** l=0l=0：

i. 多项式 gg 是一个常数。

ii. **返回**具有单一坐标 \[g\]\[g\] 的向量。

- **如果**l=1l=1：

i. 多项式 gg 是一个变量 X1X1 中的多线性多项式。

ii. 坐标是 g(0)g(0) 和 g(1)g(1) 的求值。

iii. **返回**向量 \[g(0),g(1)\]\[g(0),g(1)\]。
2. **递归步骤：**
   - **如果** l>1l>1：

i. 将 gg 表示为变量 XlXl 中的多项式，其系数是前 l−1l−1 个变量中的多线性多项式：

$$g(X)=C0(X1,…,Xl−1)(1−Xl)+C1(X1,…,Xl−1)Xl$$

ii. 通过在 XlXl 的极值点处评估 gg 来计算系数 C0C0 和 C1C1：

$$C0(X<l)=g(X<l,0)$$
     $$C1(X<l)=g(X<l,1)$$

iii. **递归调用**该算法以找到这两个新多项式在 l−1l−1 个变量中的坐标：

a. coords0←coords0←`MultilinearCoordinatesInterpolationBasis(C_0, l - 1)`

b. coords1←coords1←`MultilinearCoordinatesInterpolationBasis(C_1, l - 1)`

iv. 原始多项式 gg 的坐标是向量coords0coords0 和 coords1coords1 的串联。

v. **返回** concat(coords0,coords1)concat(coords0,coords1)

该算法利用了以下事实：在相应的插值基上，坐标只是多项式在超立方体中指定点的求值，就像上一节中一样。

为了说明这一点，让我们举个之前的例子。对于我们的玩具多项式

$$h=X1+X1X3+2X2X3X4+2X4$$

我们在变量 X3,X4X3,X4 中的插值基中计算了其坐标，得到：

$$[X1,2+X1,2X1,2+2X1+2X2]$$

现在我们继续通过获得变量 X1X1 和 X2X2 的多线性插值基中每个多项式的坐标：

- **X1X1 的坐标：** 我们在布尔正方形的每个点处评估 X1X1，得到

$$X1⟷[0,1,0,1]$$

- **2+X12+X1 的坐标：** 我们在布尔正方形的每个点处评估 2+X12+X1，得到

$$2+X1⟷[2,3,2,3]$$

- **2X12X1 的坐标：** 重复这个想法，我们得到

$$2X1⟷[0,2,0,2]$$

- **2+2X1+2X22+2X1+2X2 的坐标：** 最后，在二进制顺序的布尔正方形的点处评估

$$2+2X1+2X2⟷[2,4,4,6]$$

这些最终坐标的串联给了我们多项式 hh 在超立方体 0,140,14 上的 16 个求值：

$$coords(h)=concat([0,1,0,1],[2,3,2,3],[0,2,0,2],[2,4,4,6])$$

也就是

$$coords(h)=[0,1,0,1,2,3,2,3,0,2,0,2,2,4,4,6]$$

正如我们可以轻松验证 hh 的直接求值一样。我们已经向前展示了这个过程，但这为我们提供了一种通过简单地观察原始坐标字符串中的子向量来快速查看坐标的方法。稍后会详细介绍。

## 多线性多项式的乘积

正如我们已经看到的，ℓℓ 个变量中的多线性多项式的集合确实是基域上的向量空间。然而，通常来说，多线性多项式的乘积不是多线性多项式。

假设现在

$$g=\prod_{k=1}^{d} pk$$

其中因子 pkpk 都是 X1,…XℓX1,…Xℓ 中的多线性多项式。通过选择变量 XiXi，我们可以将乘积视为 XiXi 中的一般多项式，并且系数在剩余变量中的多项式环中。

> **事实 4：** gg 作为 XiXi 中多项式的次数是每个因子 pkpk 作为 XiXi 中多项式的次数之和；这可以通过确定多项式 pkpk 是否具有 XiXi 作为变量来确定。

因此，如果我们想确定 gg 在 XiXi 变量中的次数，我们需要检查每个多线性因子是否包含此变量。我们可以使用一个基于简单求值的测试的简陋算法来确定这一事实：当你将 XkXk 的值从 0 更改为 1 时，多线性多项式 p(X1,…,Xℓ)p(X1,…,Xℓ) **不**包含变量 XkXk，前提是其值保持不变，同时保持所有其他变量不变。也就是说，如果

> **事实 5：**
>
> $$p(x1,…,xk−1,0,xk+1,…,xℓ)=p(x1,…,xk−1,1,xk+1,…,xℓ)$$
>
> 对于所有 xj∈{0,1}xj∈{0,1} (j≠kj≠k) ⟺⟺ pp 不依赖于 XkXk。

为了说明这个事实，假设我们有

$$p(X1,X2,X3)=X1(X2+X3)$$

我们想测试这个多项式是否包含变量 **X3X3**。该测试要求我们检查对于 (X1,X2)∈{0,1}2(X1,X2)∈{0,1}2 的所有可能组合，是否 p(X1,X2,0)=p(X1,X2,1)p(X1,X2,0)=p(X1,X2,1)。

1. **首先，我们检查 (x1,x2)=(0,0)(x1,x2)=(0,0)：**- p(0,0,0)=0(0+0)=0
- p(0,0,1)=0(0+1)=0
- 等式成立，并观察到如果算法在这里停止，它会错误地得出结论，即多项式不依赖于X3X3。检查超立方体所有点的等式是必要的。

2. **现在检查 (x1,x2)=(1,0)(x1,x2)=(1,0):**

- p(1,0,0)=1(0+0)=0
- p(1,0,1)=1(0+1)=1
- 等式**不成立**。

因为等式在至少一种情况下不成立，所以比较评估的算法正确地得出结论，即变量X3X3**包含**在多项式中。

既然我们花了一些时间讨论超立方体上的评估与多元线性插值基上的坐标之间的联系 - 我们如何利用我们已经知道的东西？

> 具体来说，我们能否提出一种算法来确定某个多元线性多项式是否包含一个特定的变量，该算法以一种利用多元线性插值基中坐标的递归性质和超立方体的排序的方式？

由于评估不过是多元线性插值基中的坐标，因此执行我们之前提到的测试相当于检查坐标向量中的不同条目。

这怎么可能呢？嗯，第一步是意识到坐标向量中的位置和变量XiXi的值之间存在关系。例如，取多项式g(X1,X2,X3)=X1+X3g(X1,X2,X3)=X1+X3，它显然不依赖于X2X2。它的坐标向量是:

coords(g)=\[0,1,0,1,1,2,1,2\]

向量的前半部分对应于X1=0X1=0的超立方体上的评估，后半部分对应于X1=1X1=1的评估。这样，我们将坐标分成两个大小减半的块，并比较这些字符串：

coordsgX1=0=\[0,1,0,1\],coordsgX1=1=\[1,2,1,2\]

> **简要说明：值得一提的是，这些新的评估字符串对应于作为gg的系数的多元线性多项式的坐标，如前几节所述：它们是等式g(X1,X2,X3)=C10(X2,X3)(1−X1)+C11(X2,X3)X1g(X1,X2,X3)=C01(X2,X3)(1−X1)+C11(X2,X3)X1中C10(X2,X3)C01(X2,X3)和C11(X2,X3)C11(X2,X3)的坐标**

但让我们坚持坐标。我们现在扫描这些片段：由于它们在第一个位置不同，我们正确地得出结论gg依赖于X1X1。

接下来，我们的任务是确定X2X2是否存在于gg中：现在我们可以将这两个子向量识别为变量X2X2和X3X3的多元线性插值基中的系数，并在两个片段上再次调用此测试。我们将两者都分成两半，分别对应于评估X2=0X2=0和X2=1X2=1：

- C10(X2,X3)C01(X2,X3)的坐标是coords(c10)=\[0,1,0,1\]，并分成\[0,1\]和\[0,1\]
- C11(X2,X3)C11(X2,X3)的坐标是coords(c11)=\[1,2,1,2\]，并分成\[1,2\]和\[1,2\]

在这两种情况下，子向量都重合，这意味着实际上，X2X2不存在于gg中。

最后，为了确定X3X3，我们对上一步获得的4个片段中的每一个执行相同的测试。很容易看出，分割\[0,1\]会产生标量向量。

\[0\]和\[1\]

它们显然是不同的，因此gg有效地包含变量X3X3。

在这个例子中，我们以“分而治之”的方式组织了例程，通过从最高有效位 (MSB) 开始检查等式，通过将字符串大小减半来处理最低有效位 (LSB) X3X3 已经很吸引人了。然而，这并不是唯一的检查方式，事实上，出于内存访问的原因，按**重要性的相反顺序**评估变量更方便。一方面，这消除了分而治之的方法，但产生了更好的性能结果：现代计算机以连续块（缓存）访问内存，而我们讨论的“分而治之”方法比较了原始向量中相距很远的位置：g(0)g(0) 与 g(5)g(5) 比较，g(1)g(1) 与 g(6)g(6) 比较，依此类推，这在性能方面代价很高。我们如何设计一种利用连续性的方法？

利用连续性的一个好方法是使用**步长**。坐标向量按字典顺序排序，这意味着元素的索引对应于整数的二进制表示，从 0 到 2l−12l−1。按照此约定，每个多项式变量 XkXk 都与坐标的二进制表示中的特定位相关联。

变量 XkXk 的 **步长** 只是其位在二进制表示中的**位置权重**：换句话说，第 k−thk−th 位对超立方体中的位置贡献了多少。对于一个多项式

g(X1,X2,X3)

具有 8 个元素的坐标向量，**步长** 与每个变量的检查对齐：

- **对于 X3X3 (LSB)：** 要将 X3X3 的值从 0 更改为 1，我们只需要更改最低有效位。该位的权重为 20=120=1。因此，X3X3 的 **步长** 为 **1**。该测试比较相邻坐标对，例如 v0v0 与 v1v1（对应于 000和 001001）。
- **对于 X2X2：** 要将 X2X2 的值从 0 更改为 1，我们需要更改中间位。该位的权重为 21=221=2。因此，X2X2 的 **步长** 为 **2**。该测试比较相隔 2 个位置的坐标对，例如 v0v0 与 v2v2（对应于 000和 010010）。
- **对于 X1X1 (MSB)：** 要将 X1X1 的值从 0 更改为 1，我们需要更改最高有效位。该位的权重为 22=422=4。因此，X1X1 的 **步长** 为 **4**。该测试比较相隔 4 个位置的坐标对，例如 v0v0 与 v4v4（对应于 000和 100100）。

> **步长** 是一种算法捷径，通过利用二进制编码的结构，找到仅在你正在测试的变量中不同的坐标对。

通过使用每个变量的步长，现在我们有一种以有效的方式扫描坐标向量的方法。这种算法的伪代码并不复杂：

**输入：**

- _coords_：多项式gg在超立方体0,1l0,1l上的 2l2l 坐标（评估）的向量。
- _l_：多项式中变量的总数（X1X1 到 XlXl）。

**中间参数：**

- _stride_：被比较的坐标之间的步长或距离。它的值对于变量 XkXk 是 2l−k2l−k。
- _block length_：每个迭代块的大小。它的值是 2k−12k−1。

> 算法 _DecideDependence\_LSBFirst(coords, l)_ 的执行方式如下：

```
1.  对于每个变量 XkXk（从 k=lk=l 迭代到 11）：
2.  计算 _stride_ =2l−k=2l−k。
3.  将标志 _depends_ 设置为 _FALSE_。
4.  从 j=0j=0 迭代到 j=2l−1j=2l−1，步长为 2⋅stride2⋅stride。
5.  在每次迭代中，比较坐标 _coords\[j\]_ 和 _coords\[j + stride\]_。
6.  如果发现 _coords\[j\]_ ≠≠ _coords\[j + stride\]_，则将 _depends_ 设置为 _TRUE_ 并退出内部循环。
7.  报告变量 XkXk 的 _depends_ 结果。
```

作为一个绝对没有惊喜的例子，这是应用到多项式 g(X−1,X2,X3)=X1+X3g(X−1,X2,X3)=X1+X3

我们将对 gg 使用相同的 8 元素坐标向量：

coords(g)=\[0,1,0,1,1,2,1,2\]

### 1\. X3X3 的决策 (k=3k=3)

```
1.  _stride_ = 23−3=123−3=1。
2.  该算法比较 j=0,…,6j=0,…,6 的坐标对 _(coords\[j\], coords\[j+1\])_，步长为 2。
3.  对于 j=0j=0：_coords\[0\] (0)_ vs. _coords\[1\] (1)_。因为 0≠10≠1，所以测试失败。
4.  **结论：** gg **依赖**于 X3X3。
```

### 2\. X2X2 的决策 (k=2k=2)

```
1.  _stride_ = 23−2=223−2=2。
2.  该算法比较 j=0,…,6j=0,…,6 的坐标对 _(coords\[j\], coords\[j+2\])_，步长为 4。
3.  对于 j=0j=0：_coords\[0\]} (0)_ vs. _coords\[2\] (0)_。它们相等。
4.  对于 j=1j=1：_coords\[1\]} (1)_ vs. _coords\[3\] (1)_。它们相等。
5.  对于 j=4j=4：_coords\[4\]} (1)_ vs. _coords\[6\] (1)_。它们相等。
6.  对于 j=5j=5：_coords\[5\]} (2)_ vs. _coords\[7\] (2)_。它们相等。
7.  **结论：** gg **不依赖**于 X2X2。
```

### 3\. X1X1 的决策 (k=1k=1)

```
1.  _stride_ = 23−1=423−1=4。
2.  该算法比较 j=0,…,3j=0,…,3 的坐标对 _(coords\[j\], coords\[j+4\])_。
3.  对于 j=0j=0：_coords\[0\] (0)_ vs. _coords\[4\] (1)_。
4.  因为 0≠10≠1，所以测试失败。
5.  **结论：** gg **依赖**于 X1X1。
```

这显然与上述结果相同，但是比较的执行方式使该算法更可取。

## 接下来是什么

接下来将利用这些想法来理解 Bagad、Dao、Domb 和 Thaler 在他们最近的文章“加速 SUMCHECK 证明”中提出的算法，他们在该文章中探索了SUMCHECK协议的不同实现方式，用于刚刚描述的这种形状的多项式：多元线性多项式的乘积。他们研究并利用了在协议的每个步骤中基域元素和随机域元素之间的交互中涉及的不同乘法和加法成本，这显然涉及对多元线性多项式及其性质的巧妙操作和理解。

>- 原文链接： [blog.lambdaclass.com/mul...](https://blog.lambdaclass.com/multilinear-polynomials-survival-kit)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

介绍

$$g(X)=\prod{k=1}^{d} p{k}(X)$$

多线性多项式：定义和基本性质

对于本文的其余部分，固定一个域 kk。多线性多项式是指 ℓ≥0ℓ≥0 变量多项式 f∈k[X1,…Xℓ]f∈k[X1,…Xℓ]，使得它的每个单项式都具有以下特征：每个变量的幂要么是 0，要么是 1。这些多项式非常有用，并且以不同的形式出现在整个域论文献中，最近又作为 Ben Diamond 和 Jim Posen 的 BINIUS 工作中的有用对象重新出现。

我们将使用 Mk[X1,…Xℓ]Mk[X1,…Xℓ] 来表示所有具有 kk 中系数的 ℓℓ 变量的多线性多项式的集合。多线性多项式例子比比皆是：

$$p(X1,X2)=2+X1+X1X2,q(X1,X2,X3)=2x3+X1X2X3+X1X2,,etc$$

应该注意的是，ℓℓ 个不定元的多线性多项式的次数以 ℓℓ 为界；自然地，Mk[X1,…Xℓ]Mk[X1,…Xℓ] 是 k[X1,…Xℓ]k[X1,…Xℓ] 的向量子空间：它是关于加法和标量乘法封闭的。

插值

多线性多项式的一个重要特征是，它们允许以简洁的方式替换非常特殊域上的任意函数。开门见山地说，在超立方体 {0,1}ℓ{0,1}ℓ 上定义的任意函数 φφ 都可以用多线性多项式进行插值。发生这种情况是因为超立方体是离散的，它允许将函数 φφ 与其图像列表 φ(x):x∈{0,1}ℓφ(x):x∈{0,1}ℓ 标识，并且至关重要的是，对于超立方体中的每个 xx，我们都有一个多线性多项式，它在 xx 上取值 1，并在其他地方求值为零。

例如，取 b=(1,0,1,1)∈{0,1}4b=(1,0,1,1)∈{0,1}4。那么

$$χb(X1,X2,X3,X4)=X1(1−X2)X3X4$$

是一个多线性多项式，在 bb 上求值为 1，在其他地方求值为 0。一般来说，对于 b∈{0,1}ℓb∈{0,1}ℓ，具有此属性的多线性多项式可以表示为

$$χb(X)=\prod_{j=1}^{\ell}(bjXj+(1−bj)(1−Xj))$$

假设我们有函数

$$φ(X1,X2)=(1+X1)(X1+X2)$$

$$φ(X1,X2)=\sum_{b∈{0,1}^{2}} g(b)χb(x)==φ(0,0)(1−X1)(1−X2)+φ(1,0)X1(1−X2)+φ(0,1)(1−X1)X2+φ(1,1)X1X2$$

其中这种相等在功能上被理解：它是布尔超立方体上两个函数的相等，其中一个是多线性多项式。在得意忘形之前，让我们陈述一个事实

事实 1： MℓMℓ 是一个维度为 2ℓ2ℓ 的向量空间，其基是拉格朗日多项式

$$Lℓ={χb:b∈{0,1}^{ℓ}}$$

按照惯例，通过第一个 2ℓ2ℓ 非负整数的二进制展开获得维度 ℓℓ 超立方体的排序：如果 0≤m≤2ℓ−10≤m≤2ℓ−1，则

$$m=m020+m121+⋯mℓ−12ℓ−1mi∈{0,1}$$

第一个变量 X1X1 与最高有效位 (MSB) 相关联。
最后一个变量 XlXl 与最低有效位 (LSB) 相关联。

例如，对于一个 3 变量多项式 g(X1,X2,X3)g(X1,X2,X3)，超立方体坐标的排序如下：

超立方体点（二进制表示）	多项式坐标(X1,X2,X3)(X1,X2,X3)
0002=00002=0	(0,0,0)(0,0,0)
0012=10012=1	(0,0,1)(0,0,1)
0102=20102=2	(0,1,0)(0,1,0)
……	……
1112=71112=7	(1,1,1)(1,1,1)

不要烦恼，这只是在立方体中行走以及我们如何考虑插值基的选择。为了清楚起见：

人们可以很容易地验证基

$$L2={(1−X1)(1−X2),(1−X1)X2,X1(1−X2),X1X2}$$

以 kk 次基向量在 kk 的二进制表示上取值 1 并且在其他地方取值 0 的意义上对布尔超立方体进行插值。

M[X1,X2,X3]M[X1,X2,X3] 的基是通过简单地从左到右依次取 L2L2 中的每个向量，首先将其乘以 (1−X31−X3)，然后其次乘以 X3X3 获得。那么 L3L3 由集合组成

(1−X1)(1−X2)(1−X3)(1−X1)(1−X2)(1−X3)
(1−X1)(1−X2)X3(1−X1)(1−X2)X3
(1−X1)X2(1−X3)(1−X1)X2(1−X3)
(1−X1)X2X3(1−X1)X2X3
X1(1−X2)(1−X3)X1(1−X2)(1−X3)
X1(1−X2)X3X1(1−X2)X3
X1X2(1−X3)X1X2(1−X3)
X1X2X3X1X2X3

以这种特定顺序。

坐标和求值：黄金纽带

如果现在我们想要使用的向量是 (1,0)(1,0) 和 (0,1)(0,1)（规范基），结果将完全不同。现在这个问题几乎可以通过观察或直接评估 vv 的内容来轻松解决：

$$v=2⋅(1,0)+3⋅(0,1)$$

这正是我们与相等多项式的情况：现在此基中的坐标只是我们想要插值的函数的求值。这是个好消息，因为计算机喜欢求值。

这个对话产生了

事实 2： 在布尔超立方体 {0,1}ℓ{0,1}ℓ 上定义的函数 ff 相对于拉格朗日基 LℓLℓ 的坐标只是其求值：

$$coords(f)=[f(b)]_{b∈{0,1}^{ℓ}}$$

例如，对于多线性多项式

$$g(X1,X2)=1+X1+X1X2$$

那么它在插值基中的坐标只是

$$g⟷coords(g)=[1,1,2,3]=[g(0),g(1),g(2),g(3)]$$

我们利用了立方体的排序，并且随意地“在整数 0≤n≤22−10≤n≤22−1 处评估 gg”。

在这种情况下的张量化

我们在高中学习的多项式运算之一是多项式乘法：例如，当给定多项式

$$X+1 和 2+Y$$

我们使用分配律计算它们的乘积，并列不定元并使用幂来缩写并列的相等符号：

$$(X+1)(2+Y)=2X+XY+2+Y$$

$$v⊗w∈V⊗W$$

$$v⊗w+2v.u⊗w=(3v+u)⊗w$$

$$V⊗W=M[X1]⊗M[X2]=M2[X1,X2]$$

更重要的是，对基的张量积会产生张量积的基。一般理论保证，每当 BB 和 CC 分别是 VV 和 WW 的基时，则

$$B⊗C={vi⊗wj:1≤i≤dim(V),1≤j≤dim(W)}$$

$$B⊗C=v1⊗w1,v1⊗w2,v2⊗w1,v2⊗w2$$

通常称为字典顺序。从这个意义上讲，这个基工作得很好：假设你选择 z∈V⊗Wz∈V⊗W 例如

$$z=2(v1⊗w1)+5(v1⊗w2)+3(v2⊗w1)−1(v2⊗w2)$$

它的坐标向量结果是 [2,5,3,−1][2,5,3,−1]。此外，由于张量与分配律兼容，因此我们允许重新组合这些项：

$$z=(2w1+5w2)⊗v1+(3w1−1w2)⊗v2$$

该组合的系数是 VV 的以下元素：

v1v1 的系数：c1=2w1+5w2c1=2w1+5w2
v2v2 的系数：c2=3w1−1w2c2=3w1−1w2

这些系数，用为 WW 选择的基的坐标表示，就是 [2,5][2,5] 和 [3,−1][3,−1]。选择张量基的顺序是为了重现以下事实：

$$concat(coords(c1),coords(c2))=concat([2,5],[3,−1])=[2,5,3,−1]$$

$$Mℓ[X1,…Xℓ]=Mℓ[X1,…Xℓ−1]⨂M[Xℓ]$$

而且，利用张量积的结合律，我们得出一个非常自然的事实：

事实 3： 设 {1,2,…,ℓ}=J⋃I{1,2,…,ℓ}=J⋃I (J,I 为不相交集合)。那么具有不定元 X1,…XℓX1,…Xℓ 的多线性多项式可以被视为具有不定元 Xj∈JXj∈J 的多线性多项式，并且系数是不定元 Xi∈IXi∈I 中的多线性多项式。

为了固定这个想法，请看一下多项式

$$h=X1+X1X3+2X2X3X4+2X4$$

由于它们最多升为 1 次幂，因此这自然是 X3X3 和 X4X4 中的多线性多项式。使用变量 X3X3 和 X4X4 中的多线性多项式的拉格朗日基

$${(1−X3)(1−X4),(1−X3)X4,X3(1−X4),X3X4}$$

(1−X3)(1−X4)(1−X3)(1−X4) 的系数： 我们在 (X3=0,X4=0)(X3=0,X4=0) 处评估 hh。

$$h(X1,X2,0,0)=X1+X1(0)+2X2(0)(0)+2(0)=X1$$

这是第一个基多项式的系数。

(1−X3)X4(1−X3)X4 的系数： 我们在 (X3=0,X4=1)(X3=0,X4=1) 处评估 hh。

$$h(X1,X2,0,1)=X1+X1(0)+2X2(0)(1)+2(1)=X1+2$$

这是第二个基多项式的系数。

X3(1−X4)X3(1−X4) 的系数： 我们在 (X3=1,X4=0)(X3=1,X4=0) 处评估 hh。

$$h(X1,X2,1,0)=X1+X1(1)+2X2(1)(0)+2(0)=X1+X1=2X1$$

这是第三个基多项式的系数。

X3X4X3X4 的系数： 我们在 (X3=1,X4=1)(X3=1,X4=1) 处评估 hh。

$$h(X1,X2,1,1)=X1+X1(1)+2X2(1)(1)+2(1)=X1+X1+2X2+2=2X1+2X2+2$$

这是第四个基多项式的系数。

总之，hh 的坐标被视为变量 X3X3 和 XrXr 中的多线性多项式很简单

$$[X1,2+X1,2X1,2+2X1+2X2]$$

事实 4： 同样，在某些变量的子集中评估多线性多项式会产生剩余变量中的多线性多项式。

多线性插值的冒险

我们刚刚讨论的内容可以看作是多线性插值的一个案例。通过 ℓℓ 个变量中的多线性多项式的插值基的性质，如果以有组织的方式处理，可以迭代此过程并有效地计算坐标。

算法：MultilinearCoordinates/ InterpolationBasis(g, l)

此算法采用 ll 个变量中的多线性多项式 gg，并返回一个 2l2l 坐标的向量，该向量表示多线性插值基中的 gg。

基本情况：
- 如果 l=0l=0：
  
  i. 多项式 gg 是一个常数。
  
  ii. 返回具有单一坐标 [g][g] 的向量。
- 如果l=1l=1：
  
  i. 多项式 gg 是一个变量 X1X1 中的多线性多项式。
  
  ii. 坐标是 g(0)g(0) 和 g(1)g(1) 的求值。
  
  iii. 返回向量 [g(0),g(1)][g(0),g(1)]。
递归步骤：
- 如果 l>1l>1：
  
  i. 将 gg 表示为变量 XlXl 中的多项式，其系数是前 l−1l−1 个变量中的多线性多项式：
  
  $$g(X)=C0(X1,…,Xl−1)(1−Xl)+C1(X1,…,Xl−1)Xl$$
  
  ii. 通过在 XlXl 的极值点处评估 gg 来计算系数 C0C0 和 C1C1：
  
  $$C0(X<l)=g(X<l,0)$$ $$C1(X<l)=g(X<l,1)$$
  
  iii. 递归调用该算法以找到这两个新多项式在 l−1l−1 个变量中的坐标：
  
  a. coords0←coords0←MultilinearCoordinatesInterpolationBasis(C_0, l - 1)
  
  b. coords1←coords1←MultilinearCoordinatesInterpolationBasis(C_1, l - 1)
  
  iv. 原始多项式 gg 的坐标是向量coords0coords0 和 coords1coords1 的串联。
  
  v. 返回 concat(coords0,coords1)concat(coords0,coords1)

该算法利用了以下事实：在相应的插值基上，坐标只是多项式在超立方体中指定点的求值，就像上一节中一样。

为了说明这一点，让我们举个之前的例子。对于我们的玩具多项式

$$h=X1+X1X3+2X2X3X4+2X4$$

我们在变量 X3,X4X3,X4 中的插值基中计算了其坐标，得到：

$$[X1,2+X1,2X1,2+2X1+2X2]$$

现在我们继续通过获得变量 X1X1 和 X2X2 的多线性插值基中每个多项式的坐标：

X1X1 的坐标： 我们在布尔正方形的每个点处评估 X1X1，得到

$$X1⟷[0,1,0,1]$$

2+X12+X1 的坐标： 我们在布尔正方形的每个点处评估 2+X12+X1，得到

$$2+X1⟷[2,3,2,3]$$

2X12X1 的坐标： 重复这个想法，我们得到

$$2X1⟷[0,2,0,2]$$

2+2X1+2X22+2X1+2X2 的坐标： 最后，在二进制顺序的布尔正方形的点处评估

$$2+2X1+2X2⟷[2,4,4,6]$$

这些最终坐标的串联给了我们多项式 hh 在超立方体 0,140,14 上的 16 个求值：

$$coords(h)=concat([0,1,0,1],[2,3,2,3],[0,2,0,2],[2,4,4,6])$$

也就是

$$coords(h)=[0,1,0,1,2,3,2,3,0,2,0,2,2,4,4,6]$$

多线性多项式的乘积

正如我们已经看到的，ℓℓ 个变量中的多线性多项式的集合确实是基域上的向量空间。然而，通常来说，多线性多项式的乘积不是多线性多项式。

假设现在

$$g=\prod_{k=1}^{d} pk$$

事实 4： gg 作为 XiXi 中多项式的次数是每个因子 pkpk 作为 XiXi 中多项式的次数之和；这可以通过确定多项式 pkpk 是否具有 XiXi 作为变量来确定。

因此，如果我们想确定 gg 在 XiXi 变量中的次数，我们需要检查每个多线性因子是否包含此变量。我们可以使用一个基于简单求值的测试的简陋算法来确定这一事实：当你将 XkXk 的值从 0 更改为 1 时，多线性多项式 p(X1,…,Xℓ)p(X1,…,Xℓ) 不包含变量 XkXk，前提是其值保持不变，同时保持所有其他变量不变。也就是说，如果

事实 5：

$$p(x1,…,xk−1,0,xk+1,…,xℓ)=p(x1,…,xk−1,1,xk+1,…,xℓ)$$

对于所有 xj∈{0,1}xj∈{0,1} (j≠kj≠k) ⟺⟺ pp 不依赖于 XkXk。

为了说明这个事实，假设我们有

$$p(X1,X2,X3)=X1(X2+X3)$$

我们想测试这个多项式是否包含变量 X3X3。该测试要求我们检查对于 (X1,X2)∈{0,1}2(X1,X2)∈{0,1}2 的所有可能组合，是否 p(X1,X2,0)=p(X1,X2,1)p(X1,X2,0)=p(X1,X2,1)。

首先，我们检查 (x1,x2)=(0,0)(x1,x2)=(0,0)：- p(0,0,0)=0(0+0)=0
- p(0,0,1)=0(0+1)=0
- 等式成立，并观察到如果算法在这里停止，它会错误地得出结论，即多项式不依赖于X3X3。检查超立方体所有点的等式是必要的。
现在检查 (x1,x2)=(1,0)(x1,x2)=(1,0):

p(1,0,0)=1(0+0)=0
p(1,0,1)=1(0+1)=1
等式不成立。

因为等式在至少一种情况下不成立，所以比较评估的算法正确地得出结论，即变量X3X3包含在多项式中。

既然我们花了一些时间讨论超立方体上的评估与多元线性插值基上的坐标之间的联系 - 我们如何利用我们已经知道的东西？

具体来说，我们能否提出一种算法来确定某个多元线性多项式是否包含一个特定的变量，该算法以一种利用多元线性插值基中坐标的递归性质和超立方体的排序的方式？

由于评估不过是多元线性插值基中的坐标，因此执行我们之前提到的测试相当于检查坐标向量中的不同条目。

coords(g)=[0,1,0,1,1,2,1,2]

向量的前半部分对应于X1=0X1=0的超立方体上的评估，后半部分对应于X1=1X1=1的评估。这样，我们将坐标分成两个大小减半的块，并比较这些字符串：

coordsgX1=0=[0,1,0,1],coordsgX1=1=[1,2,1,2]

简要说明：值得一提的是，这些新的评估字符串对应于作为gg的系数的多元线性多项式的坐标，如前几节所述：它们是等式g(X1,X2,X3)=C10(X2,X3)(1−X1)+C11(X2,X3)X1g(X1,X2,X3)=C01(X2,X3)(1−X1)+C11(X2,X3)X1中C10(X2,X3)C01(X2,X3)和C11(X2,X3)C11(X2,X3)的坐标

但让我们坚持坐标。我们现在扫描这些片段：由于它们在第一个位置不同，我们正确地得出结论gg依赖于X1X1。

C10(X2,X3)C01(X2,X3)的坐标是coords(c10)=[0,1,0,1]，并分成[0,1]和[0,1]
C11(X2,X3)C11(X2,X3)的坐标是coords(c11)=[1,2,1,2]，并分成[1,2]和[1,2]

在这两种情况下，子向量都重合，这意味着实际上，X2X2不存在于gg中。

最后，为了确定X3X3，我们对上一步获得的4个片段中的每一个执行相同的测试。很容易看出，分割[0,1]会产生标量向量。

[0]和[1]

它们显然是不同的，因此gg有效地包含变量X3X3。

在这个例子中，我们以“分而治之”的方式组织了例程，通过从最高有效位 (MSB) 开始检查等式，通过将字符串大小减半来处理最低有效位 (LSB) X3X3 已经很吸引人了。然而，这并不是唯一的检查方式，事实上，出于内存访问的原因，按重要性的相反顺序评估变量更方便。一方面，这消除了分而治之的方法，但产生了更好的性能结果：现代计算机以连续块（缓存）访问内存，而我们讨论的“分而治之”方法比较了原始向量中相距很远的位置：g(0)g(0) 与 g(5)g(5) 比较，g(1)g(1) 与 g(6)g(6) 比较，依此类推，这在性能方面代价很高。我们如何设计一种利用连续性的方法？

利用连续性的一个好方法是使用步长。坐标向量按字典顺序排序，这意味着元素的索引对应于整数的二进制表示，从 0 到 2l−12l−1。按照此约定，每个多项式变量 XkXk 都与坐标的二进制表示中的特定位相关联。

变量 XkXk 的步长只是其位在二进制表示中的位置权重：换句话说，第 k−thk−th 位对超立方体中的位置贡献了多少。对于一个多项式

g(X1,X2,X3)

具有 8 个元素的坐标向量，步长与每个变量的检查对齐：

对于 X3X3 (LSB)： 要将 X3X3 的值从 0 更改为 1，我们只需要更改最低有效位。该位的权重为 20=120=1。因此，X3X3 的步长为 1。该测试比较相邻坐标对，例如 v0v0 与 v1v1（对应于 000和 001001）。
对于 X2X2： 要将 X2X2 的值从 0 更改为 1，我们需要更改中间位。该位的权重为 21=221=2。因此，X2X2 的步长为 2。该测试比较相隔 2 个位置的坐标对，例如 v0v0 与 v2v2（对应于 000和 010010）。
对于 X1X1 (MSB)： 要将 X1X1 的值从 0 更改为 1，我们需要更改最高有效位。该位的权重为 22=422=4。因此，X1X1 的步长为 4。该测试比较相隔 4 个位置的坐标对，例如 v0v0 与 v4v4（对应于 000和 100100）。

步长是一种算法捷径，通过利用二进制编码的结构，找到仅在你正在测试的变量中不同的坐标对。

通过使用每个变量的步长，现在我们有一种以有效的方式扫描坐标向量的方法。这种算法的伪代码并不复杂：

输入：

coords：多项式gg在超立方体0,1l0,1l上的 2l2l 坐标（评估）的向量。
l：多项式中变量的总数（X1X1 到 XlXl）。

中间参数：

stride：被比较的坐标之间的步长或距离。它的值对于变量 XkXk 是 2l−k2l−k。
block length：每个迭代块的大小。它的值是 2k−12k−1。

算法 DecideDependence_LSBFirst(coords, l) 的执行方式如下：

1.  对于每个变量 XkXk（从 k=lk=l 迭代到 11）：
2.  计算 _stride_ =2l−k=2l−k。
3.  将标志 _depends_ 设置为 _FALSE_。
4.  从 j=0j=0 迭代到 j=2l−1j=2l−1，步长为 2⋅stride2⋅stride。
5.  在每次迭代中，比较坐标 _coords\[j\]_ 和 _coords\[j + stride\]_。
6.  如果发现 _coords\[j\]_ ≠≠ _coords\[j + stride\]_，则将 _depends_ 设置为 _TRUE_ 并退出内部循环。
7.  报告变量 XkXk 的 _depends_ 结果。

作为一个绝对没有惊喜的例子，这是应用到多项式 g(X−1,X2,X3)=X1+X3g(X−1,X2,X3)=X1+X3

我们将对 gg 使用相同的 8 元素坐标向量：

coords(g)=[0,1,0,1,1,2,1,2]

1. X3X3 的决策 (k=3k=3)

1.  _stride_ = 23−3=123−3=1。
2.  该算法比较 j=0,…,6j=0,…,6 的坐标对 _(coords\[j\], coords\[j+1\])_，步长为 2。
3.  对于 j=0j=0：_coords\[0\] (0)_ vs. _coords\[1\] (1)_。因为 0≠10≠1，所以测试失败。
4.  **结论：** gg **依赖**于 X3X3。

2. X2X2 的决策 (k=2k=2)

1.  _stride_ = 23−2=223−2=2。
2.  该算法比较 j=0,…,6j=0,…,6 的坐标对 _(coords\[j\], coords\[j+2\])_，步长为 4。
3.  对于 j=0j=0：_coords\[0\]} (0)_ vs. _coords\[2\] (0)_。它们相等。
4.  对于 j=1j=1：_coords\[1\]} (1)_ vs. _coords\[3\] (1)_。它们相等。
5.  对于 j=4j=4：_coords\[4\]} (1)_ vs. _coords\[6\] (1)_。它们相等。
6.  对于 j=5j=5：_coords\[5\]} (2)_ vs. _coords\[7\] (2)_。它们相等。
7.  **结论：** gg **不依赖**于 X2X2。

3. X1X1 的决策 (k=1k=1)

1.  _stride_ = 23−1=423−1=4。
2.  该算法比较 j=0,…,3j=0,…,3 的坐标对 _(coords\[j\], coords\[j+4\])_。
3.  对于 j=0j=0：_coords\[0\] (0)_ vs. _coords\[4\] (1)_。
4.  因为 0≠10≠1，所以测试失败。
5.  **结论：** gg **依赖**于 X1X1。

这显然与上述结果相同，但是比较的执行方式使该算法更可取。

接下来是什么

原文链接： blog.lambdaclass.com/mul...

登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

本文参与登链社区写作激励计划，好文好收益，欢迎正在阅读的你也加入。

多线性多项式：生存工具包

介绍

多线性多项式：定义和基本性质

插值

坐标和求值：黄金纽带

在这种情况下的张量化

多线性插值的冒险

算法：MultilinearCoordinates/ InterpolationBasis(g, l)

多线性多项式的乘积

1. X3X3 的决策 (k=3k=3)

2. X2X2 的决策 (k=2k=2)

3. X1X1 的决策 (k=1k=1)

接下来是什么

0 条评论

文章目录