# 如何快速验证矩阵乘法的正确性

# 问题

找到「矩阵乘法」的高效算法是计算机科学长久以来的一个研究课题，对于两个$n \times n$的矩阵，平凡的矩阵乘法算法的时间复杂度为$\mathcal{O}(n^3)$。之后经过计算机科学家半个多世纪的努力（Strassen算法，Coppersmith-Winograd算法，laser方法等），最前沿算法的时间复杂度已经降低为$\mathcal{O}\left(n^{2.37286}\right)$。

但本文要探讨的并非计算矩阵乘法本身的高效算法，而是**检验矩阵乘法计算正确性**的高效算法，换句话说，我们提出如下问题：

> 是否存在比已知最好的矩阵乘法算法更快的**检验矩阵乘法计算正确性**的算法？即给定三个$n \times n$的矩阵$A,B,C$，高效地判定$A\times B \stackrel{?}{=} C$ 的算法。
>
# Freivalds 算法

Freivalds在1977年给出了一个时间复杂度为$\mathcal{O}(n^2)$的随机化算法，对上述问题给出了一个肯定的答案。注意到仅仅读入输入$A,B,C$就需要$\mathcal{O}(n^2)$了，所以Freivalds算法只比读入输入增加了常数多的额外开销，远远快于最快的计算矩阵乘法的算法。

- Freivalds 算法

首先，随机选择 $r \in \mathbb{F}_{p}$，令 $x=\left(1, r, r^{2}, \ldots, r^{n-1}\right)$。
接着计算 $y=C x$ 和 $z=A(Bx)$，
如果 $y=z$ 输出 YES， 否则输出NO。

# 分析
- 生成向量$x$：$\mathcal{O}(n)$
- 矩阵-向量乘法：$\mathcal{O}(n^2)$
- 计算$y$和$z$分别需要一个和两个矩阵-向量乘法：$\mathcal{O}(n^2)$
- 故**总时间复杂度**：$\mathcal{O}(n^2)$

令$D=AB$， $[n] := \{1,2, \ldots, n\}$
- **完备性**：如果 $C=D$,则对所有向量$x$有$C x=D x$， 算法对于所有可能的$r$都输出YES。
- **可靠性**：哪怕只有一个$(i, j) \in[n] \times[n]$ 使得$C_{i, j} \neq D_{i, j}$, 则算法输出NO的概率至少为 $1-(n-1) / p$。

可靠性证明：

假设 $C \neq D$, 令 $C_{i}$ 和 $D_{i}$ 分别为$C$ 和 $D$ 的第$i$行。显然，因为$C \neq D$，存在行$i$使得$C_{i} \neq D_{i}$。 观察到$(C x)_{i}$即为$p_{C_{i}}(r)$，$C_{i}$的Reed-Solomon编码，类似的$(A \cdot B \cdot x)_{i}=p_{D_{i}}(r)$。因此$(C x)_{i} \neq(A \cdot B \cdot x)_{i}$的概率至少为$1-(n-1) / p$（简单应用[Schwartz-Zippel 引理](https://hackmd.io/@Kurt-Pan/Bkq-tZGL5))，该概率即为算法输出NO的概率。

# 实现
- https://github.com/0xSage/freivald
- https://github.com/maxgillett/thaler_reading_group/tree/master/week1-frievalds
- https://github.com/Ethan-000/freivalds_algorithm
- https://github.com/mmagician/freivalds
- https://github.com/thor314/pazk/tree/ch2/2-freivalds