2025年Freivalds算法

Freivalds算法Freivalds 算法 一 问题引出 给定三个 n x n 的矩阵 A B C 如何判断 A x B C 按照我们很自然的思维 首先需要计算出 A x B 的值 再与 C 进行比较 而这需要 O n 3

大家好,我是讯享网,很高兴认识大家。

Freivalds算法

一、问题引出:给定三个n x n 的矩阵A, B, C,如何判断A x B = C?

按照我们很自然的思维,首先需要计算出A x B的值,再与C进行比较。而这需要 O ( n 3 ) O(n^3) O(n3)的复杂度,显然,这种方法是效率很低的。

但是我们考虑到一个问题,这里并不是需要计算出A x B,而是只需要判断A x B与C是否相等,换句话说,判断他们是否相等并不是一定要计算出A x B的值。

而接下来介绍的Freivalds算法就是在不必计算出A x B的前提下判断出A x B==C?

二、Freivalds算法

首先,根据矩阵的特性我们知道,A x B = C的一个必要条件是:对于一个n x 1的向量r(r[i]=0 or 1),有A x B x r=C x r 。
如何理解上面这个必要条件呢?也就是说,由“如果A x B = C,则必然有A x B x r=C x r”,我们换成其逆否命题,即:如果A x B x r = C x r不成立,那么A × B = C就一定不成立。但是,那如果A x B x r = C x r成立,那么A × B = C就一定成立吗?,显然是不一定的,但是,幸运的是,有人证明出了
A x B x r = C x r成立,而A × B = C不成立
的概率是小于1/2的。
即: P ( A ∗ B ∗ r = C ∗ r , A ∗ B ! = C ) ≤ 1 / 2 P(A*B*r = C*r, A*B != C) ≤ 1/2 P(A∗B∗r=C∗r,A∗B!=C)≤1/2

因此,我们可以反复做出判断,重复判断k次,就可以把错误概率降低到 1 / 2 k 1/2^k 1/2k了。

比如下面这个例子:

1541259633247
讯享网

如果我们要判断上面的等式是否成立,则可以判断下面的等式是否等于零向量:

1541259721381

那么,我们可以先随机生成一个每个数值为0或者1的向量,

1541259780349

经过计算,其结果确实为零向量,但是现在如果下结论说A x B = C的话,错误的概率有1/2。于是,再随机生成一个向量:

1541259840367

经过计算,发现其结果不等于零向量了,这时候,我们便可以下结论说A x B != C了。当然,如果这一次依然等于零向量的话,则错误概率降到了1/4,如果重复很多次,则错误概率会降低到很小很小,几乎不会发生了。

因此,可以用下面的Python代码来实现。

三、Python代码

from random import randint from sys import stdin def readint(): """ 按照输入规则,输入的第一个数为矩阵的维度 """ return int(stdin.readline()) def readarray(typ): """ 读入一行数据 """ return list(map(typ, stdin.readline().split())) def readmatrix(n): """ 读入矩阵 """ M = [] for _ in range(n): row = readarray(int) assert len(row) == n M.append(row) return M def mult(M, v): """ 矩阵与向量相乘 """ n = len(M) assert len(M) == len(v) return [sum(M[i][j] * v[j] for j in range(n)) for i in range(n)] def freivalds(A, B, C): """ freivalds算法 """ n = len(A) for i in range(10000): x = [randint(0, 1) for _ in range(n)] if not mult(A, mult(B, x)) == mult(C, x): return False else: return True if __name__ == "__main__": n = readint() A = readmatrix(n) B = readmatrix(n) C = readmatrix(n) print(freivalds(A, B, C)) 

讯享网

上面的代码中有几点需要说明:

  • 上述代码可以从文件读入数据作为输入。即通过下面命令可以运行:
    讯享网python freivalds.py < input.in 

    其中,freivalds.py为Python文件名,input.in中存放的是待输入的数据。

  • 读入数据的方式不是用的常见的input()函数,而是改用stdin.readline(),其目的是加快了读取速度。
  • 经过试验证明,上述的代码还可以把freivalds(A, B, C)函数改写成如下:
def freivalds(A, B, C): """ freivalds算法 """ n = len(A) x = [randint(0, ) for _ in range(n)] return mult(A, mult(B, x)) == mult(C, x) 

即,按照上文所说,r向量里面的每一个元素必须是0或者1,如此重复多次可以降低错误率到很小,但实际上,将r里面随机数的取值范围扩大,也可以在不必重复很多次的情况下降低错误率。

小讯
上一篇 2025-03-17 21:48
下一篇 2025-02-08 08:12

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/80702.html