Massive Algorithms: Freivalds' algorithm

随机的力量(2) - 矩阵比较

最直接的想法，当然是先进行矩阵乘法得到矩阵D = A×B，然后再一一比较矩阵C和矩阵D是否相同？

比较两个n×n矩阵是否相同的时间复杂度为O(N^2)，而矩阵乘法直接算法时间复杂度是O(N^3), 目前最快的矩阵乘法的时间复杂度是O(N^2.376)。综合来看，时间复杂度接近O(N^3)。

是否存在更快的方法呢？答案是肯定的，下面我们介绍一种技术 - Freivalds技术

先来看一个A*B=C的必要条件： 对于n×1向量r， A*B*r = C*r

注意，这并不是充分条件。如果A*B*r = C*r, 并不能推导出A*B一定等于C。但如果A*B*r = C*r不成立，那么A×B=C就一定不成立。

随机产生一个n×1向量r，r[i] = 0或1，A*B*r = C*r 但A*B不等于C的概率是多大呢？

可以证明，P{A*B*r = C*r, A*B != C} <= 1/2

Freivalds技术就是基于上述的必要条件和概率估计，采用Monto Carlo算法， 算法逻辑可以参考以下伪代码。

// 判断A*B=C是否成立

bool IsIdentical(A, B, C) {

       for (int iter = 0; iter < K; iter++) {

               r = RandomVector()

               // 判断A*B*r = C*r是否成立

               if(false == IsIdentical(A, B, C, r)) {

                       // 不满足必要条件，必定不成立

                       return false;

}

}

       return true;

}

每次必要条件测试A*B*r = C*r的计算时间复杂度为O(N^2)。（计算A*B*r = A*(B*r)采取从右往左计算顺序）

每次测试的错误概率小于等于1/2, 那么采取Monto Carlo算法后，K次都错误的概率会下降到1/(2^K)。

综合来看，时间复杂度为O(K*N^2), 而准确概率提升到1 - 1/(2^K)

http://www.sanfoundry.com/java-program-implement-coppersmith-freivald/

check whether the multiplication of matrix A and B equals the given matrix C. It does it by checking A*(B*r)-(C*r) where r is any random column vector consisting only 0/1 as its elements. If this value is zero algorithm prints Yes, No otherwise.

        //random generation of the r vector containing only 0/1 as its elements

        double [][]r = new double[n][1];

```
        Random random = new Random();
```
```
        for(int i=0; i<n; i++)
```
```
        {
```

            r[i][0] = random.nextInt(2);

```
        }
```
```
        //test A * (b*r) - (C*) = 0
```

        double br[][] = new double[n][1];

        double cr[][] = new double[n][1];

        double abr[][] = new double[n][1];

```
        br = multiplyVector(b, r, n);
```
```
        cr = multiplyVector(c, r, n);
```
```
        abr = multiplyVector(a, br, n);
```
```
 
```
```
        //check for all zeros in abr
```
```
        boolean flag = true; 
```
```
        for(int i=0; i<n; i++)
```
```
        {
```
```
            if(abr[i][0] == 0)
```
```
                continue;
```
```
            else
```
```
                flag = false;
```
```
        }
```
```
        if(flag == true)
```
```
            System.out.println("Yes");
```
```
        else
```
```
            System.out.println("No");
```

    public static double[][] multiplyVector(double[][] a, double[][] b, int n)

```
    {
```

        double result[][] = new double[n][1];

```
        for (int i = 0; i < n; i++) 
```
```
        {
```

            for (int j = 0; j < 1; j++)

```
            {
```

                for (int k = 0; k < n; k++)

```
                {  
```

                    result[i][j] = result[i][j] + a[i][k] * b[k][j];

```
                }
```
```
            }
```
```
        }
```
```
        return result;
```
```
    }
```

Freivalds' algorithm

Labels

Popular Posts