The Algorithm Magic of Polynomial
- Polynomials
- The Root of Polynomial
- A Delete Channel
- Polynomials for Finding Maximum Matchings
Polynomials 多项式
一个 d d d 次多项式可以用一个 d + 1 d+1 d+1 元组 c i {c_i} ci 表达。在这种情况下，两个多项式相加的时间复杂度是 O ( d ) O(d) O(d) ，而两个多项式相乘的实践复杂度是 O ( d log d ) O(d \log d) O(dlogd) 。
快速地估计一个多项式的值的方法：对应给定值b，循环执行将当前式子乘b,加下一项。这个方法叫做霍纳规则。流程如下：
c
d
c
d
×
b
+
c
d
−
1
(
c
d
×
b
+
c
d
−
1
)
×
b
+
c
d
−
2
c_d c_d \times b + c_{d-1} (c_d \times b + c_{d-1}) \times b +c_{d-2}
cdcd×b+cd−1(cd×b+cd−1)×b+cd−2
该算法的时间复杂度是
O
(
d
)
O(d)
O(d)。
多项式的根
对于一个多项式 P ( x ) P(x) P(x)，令 P ( x ) = 0 P(x)=0 P(x)=0 的值 x ′ x' x′ 被称作多项式的根。
根据代数基本定理，一个d次多项式一定有d个根。
Unique Reconstruction Theorem 唯一重构定理
唯一重构定理告诉我们，给定d个点 ( x 1 , y 1 ) , ( x 2 , y 2 ) ⋱ , ( x d , y d ) (x_1,y_1),(x_2,y_2) \ddots, (x_d,y_d) (x1,y1),(x2,y2)⋱,(xd,yd), 总有一个多项式 P ( x ) P(x) P(x) 使得这些点都在多项式上。
事实上，唯一重构定理告诉我们如何构造这样一个多项式满足条件。
首先我们构造这样一组多项式
R
i
(
x
)
R_i(x)
Ri(x) 满足：
R
i
(
x
i
)
=
1
R
i
(
x
j
)
=
0
,
j
≠
i
R_i(x_i) = 1 R_i(x_j) = 0, j \neq i
Ri(xi)=1Ri(xj)=0,j=i
结果如下：
Π
j
≠
i
(
x
−
x
j
)
Π
j
≠
i
(
x
i
−
x
j
)
\quad{\Pi _{j\neq i}(x-x_j)}\over{\Pi _{j\neq i}(x_i-x_j)}
Πj=i(xi−xj)Πj=i(x−xj)
那么
P
(
x
)
=
y
0
R
0
(
x
)
+
y
1
R
1
(
x
)
+
⋯
+
y
d
R
d
(
x
)
P(x) = y_0 R_0(x) + y_1 R_1(x) + \cdots +y_d R_d(x)
P(x)=y0R0(x)+y1R1(x)+⋯+ydRd(x)
举个例子：有三个点
(
5
,
1
)
,
(
6
,
2
)
,
(
7
,
9
)
(5,1),(6,2),(7,9)
(5,1),(6,2),(7,9)，现在找出经过这三个点的多项式。
R
1
(
x
)
=
(
x
−
6
)
(
x
−
7
)
(
5
−
6
)
(
5
−
7
)
=
1
2
(
x
2
−
13
x
+
42
)
R
2
(
x
)
=
(
x
−
5
)
(
x
−
7
)
(
6
−
5
)
(
6
−
7
)
=
−
1
2
(
x
2
−
12
x
+
35
)
R
3
(
x
)
=
(
x
−
5
)
(
x
−
6
)
(
7
−
6
)
(
7
−
5
)
=
1
2
(
x
2
−
11
x
+
30
)
P
(
x
)
=
R
1
(
x
)
+
2
R
2
(
X
)
+
9
R
3
(
x
)
=
4
x
2
−
50
x
+
R_1(x) = \frac{(x-6)(x-7)}{(5-6)(5-7)} = \frac{1}{2} (x^2 -13x +42) R_2(x) = \frac{(x-5)(x-7)}{(6-5)(6-7)} = -\frac{1}{2} (x^2 -12x +35) R_3(x) = \frac{(x-5)(x-6)}{(7-6)(7-5)} = \frac{1}{2} (x^2 -11x +30) P(x) = R_1(x) + 2R_2(X) + 9R_3(x) = 4x^2-50x +
R1(x)=(5−6)(5−7)(x−6)(x−7)=21(x2−13x+42)R2(x)=(6−5)(6−7)(x−5)(x−7)=−21(x2−12x+35)R3(x)=(7−6)(7−5)(x−5)(x−6)=21(x2−11x+30)P(x)=R1(x)+2R2(X)+9R3(x)=4x2−50x+
A Deletion Channel 丢失频道
下面是另一个问题，假设在上面构造多项式的情景中，Alice要向Bob传d+1个数，但是在传输的过程中总会有k个数丢失，那么怎么才能保证Bob一定收的到这d+1个数呢？
一种很笨的方法是，将每个数据发送k+1次就可以了。但是这需要发送 d × ( k + 1 ) d\times (k+1) d×(k+1) 个数据，有没有更好的方法呢？
一种好方法是构造一个多项式
P
(
x
)
=
Σ
c
i
x
i
P(x) =\Sigma c_i x_i
P(x)=Σcixi，然后发送
P
(
0
)
,
P
(
1
)
,
⋱
,
P
(
d
+
k
)
P(0),P(1),\ddots,P(d+k)
P(0),P(1),⋱,P(d+k)，这样Bob至少可以收到d+1个多项式的值，根据唯一重构定理，Bob可以计算出这个多项式从而得出所有的c。
这种做法的时间复杂度是
O
(
d
+
k
+
1
)
O(d+k+1)
O(d+k+1)，比上面的做法少传输很多数据。（注意，不用担心乱序的问题，因为是一个一个传的,而如果出错会传乱码而不是什么也不做）。
General Error Correction 误码纠错
假设现在不是传输丢失，而是传输一个错误的数字，那么在同样的背景下，需要进行怎样的传输呢？
很明显，答案是需要传输 d + 2 k + 1 d+2k+1 d+2k+1个数字，其中 d + k + 1 d+k+1 d+k+1是正确的多项式的值。因为 k + 1 > k k+1>k k+1>k，所以我们从理论上确认了Bob可以通过这种方式找到正确的多项式。
那么实际上应该怎么找到那个正确的多项式呢？
假设Bob收到的数据是
r
0
,
r
1
,
⋱
,
r
d
+
2
k
r_0,r_1,\ddots,r_{d+2k}
r0,r1,⋱,rd+2k，Z是其中错误信息的集合，那么我们声明一个错误项多项式
E
(
x
)
=
Π
i
∈
Z
(
x
−
i
)
E(x) = \Pi_{i\in Z}(x-i)
E(x)=Πi∈Z(x−i)
那么对于Bob收到的所有项都满足以下等式，因为要么
E
(
x
)
=
0
E(x)=0
E(x)=0，要么
P
(
x
)
=
r
x
P(x) = r_x
P(x)=rx
P
(
x
)
⋅
E
(
x
)
=
r
x
⋅
E
(
x
)
P(x)\cdot E(x) = r_x \cdot E(x)
P(x)⋅E(x)=rx⋅E(x)
Berlekamp-Welch Algorithm BW算法
BW算法是一种用于误码纠错的算法，其运行规律基于上文所述，我们假设
E
(
x
)
=
x
k
+
e
k
−
1
x
k
−
1
+
⋯
+
e
0
(
i
f
d
e
g
r
e
e
(
E
(
x
)
)
i
s
k
)
P
(
x
)
⋅
E
(
x
)
=
f
d
+
k
x
d
+
k
+
f
d
+
k
−
1
x
d
+
k
−
1
+
⋯
+
f
0
E(x) = x^k +e_{k-1}x^{k-1} + \cdots + e_0 (if degree(E(x)) is k) P(x) \cdot E(x) = f_{d+k}x^{d+k} + f_{d+k-1}x^{d+k-1} + \cdots + f_0
E(x)=xk+ek−1xk−1+⋯+e0(ifdegree(E(x))isk)P(x)⋅E(x)=fd+kxd+k+fd+k−1xd+k−1+⋯+f0
这种情况下，我们分别将
x
=
0
,
1
,
⋯
,
d
+
2
k
x = 0,1,\cdots, d+2k
x=0,1,⋯,d+2k带入方程
P
(
x
)
⋅
E
(
x
)
=
r
x
⋅
E
(
x
)
P(x) \cdot E(x) = r_x \cdot E(x)
P(x)⋅E(x)=rx⋅E(x)
左边是一堆参数f相加，右边是一堆e相加，f和e未知数的总和是d+2k+1个，而带入d+2k+1个x的值对应d+2k+1个方程，而且方程必定有解，因此就可以解出所有的e和f。
已知 P ( x ) ⋅ E ( x ) P(x) \cdot E(x) P(x)⋅E(x) 和 E ( x ) E(x) E(x) ，相除就可以求出 P ( x ) P(x) P(x)。
Polynomials for Finding Maximum Matching 多项式在最大匹配中的应用
Schwarz-Zippel Lemma Schwarz-Zippel 引理
这个引理的内容是：假设
P
P
P是一个非零
m
m
m元
d
d
d次多项式，假设
S
S
S是有限域
F
F
F的一个子集。如果从
S
S
S中随机抽取
m
m
m个数
x
1
,
x
2
,
⋯
,
x
m
{x_1,x_2,\cdots,x_m}
x1,x2,⋯,xm，那么
P
r
[
P
(
x
1
,
⋯
,
x
m
)
=
0
]
≤
d
∣
S
∣
Pr[P(x_1,\cdots,x_m)=0] \leq \frac{d}{|S|}
Pr[P(x1,⋯,xm)=0]≤∣S∣d
健全性检查：当
m
=
1
m=1
m=1时，因为d次多项式最多有
d
d
d个根，因此概率很明显就是
d
∣
S
∣
\frac{d}{|S|}
∣S∣d。
这个引理可以用来解决下文提到的图的匹配问题。
Tutte Matrix
每个顶点数
v
v
v的简单无向图都对应一个Tutte Matrix
M
(
G
)
M(G)
M(G)，简单来说如图所示：
Tutte Determinant Theorem Tutte行列式定理
一个图有完美匹配当且仅当
M
(
G
)
M(G)
M(G)的行列式不是零多项式。
（注：匹配指的找到图中一组边集，其中任意两条边都没有公共点。如果这组边集包括了图中所有的顶点，那么就说该匹配是完美匹配。）
那么剩下的就是选取 F F F的大小了， F F F的基数越大，这张图有完美匹配的概率就越高。
Finding a Perfect Matching
上面我们知道了有完美匹配的概率，但是我们如何找到一个完美匹配呢？下面是一个方法:
对于每个边，将图中的该边删去，判断剩下的图中是否还存在完美匹配。如果没有完美匹配，那么将该边加回来；否则丢弃该边。
最后一定剩下
V
2
\frac{V}{2}
2V条边，这些边就是一个完美匹配。
