## Wednesday, January 13, 2016

### Freivalds' algorithm

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;
}

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.
1. `        //random generation of the r vector containing only 0/1 as its elements`
2. `        double [][]r = new double[n][1];`
3. `        Random random = new Random();`
4. `        for(int i=0; i<n; i++)`
5. `        {`
6. `            r[i][0] = random.nextInt(2);`
7. `        }`
8. `        //test A * (b*r) - (C*) = 0`
9. `        double br[][] = new double[n][1];`
10. `        double cr[][] = new double[n][1];`
11. `        double abr[][] = new double[n][1];`
12. `        br = multiplyVector(b, r, n);`
13. `        cr = multiplyVector(c, r, n);`
14. `        abr = multiplyVector(a, br, n);`
15. ` `
16. `        //check for all zeros in abr`
17. `        boolean flag = true; `
18. `        for(int i=0; i<n; i++)`
19. `        {`
20. `            if(abr[i][0] == 0)`
21. `                continue;`
22. `            else`
23. `                flag = false;`
24. `        }`
25. `        if(flag == true)`
26. `            System.out.println("Yes");`
27. `        else`
28. `            System.out.println("No");`
29.

30. `    public static double[][] multiplyVector(double[][] a, double[][] b, int n)`
31. `    {`
32. `        double result[][] = new double[n][1];`
33. `        for (int i = 0; i < n; i++) `
34. `        {`
35. `            for (int j = 0; j < 1; j++) `
36. `            {`
37. `                for (int k = 0; k < n; k++)`
38. `                {  `
39. `                    result[i][j] = result[i][j] + a[i][k] * b[k][j];`
40. `                }`
41. `            }`
42. `        }`
43. `        return result;`
44. `    }`