Freivalds Algorithm

Freivalds’ algorithm is a probabilistic randomized algorithm used to verify matrix multiplication. Given three n × n matrices A, B, and C, a general problem is to verify whether A*B=C

Complexity

  • Time:

References

Implementations

  • 1

    # TODO: Implement in Python

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

    const A = [[2, 3], [3, 4]];
const B = [[1, 0], [1, 2]];
const C = [[6, 5], [8, 7]];

function FreivaldsAlgorithm() {
  let k = 5;
  let i;
  let j;
  let tmp;
  let tmpB;
  let tmpC;
  const n = A.length;

  while (k--) {
    
    console.log(`Iterations remained: #${k}`);

    // Generate random vector
    const r = [];

    let P = [];
    for (i = 0; i < n; i++) {
      P.push(-1);
      r.push((Math.random() < 0.5) << 0);
    }

    // Compute Br, Cr
    const Br = [];

    const Cr = [];
    for (i = 0; i < n; i++) {
      tmpB = 0;
      tmpC = 0;
      for (j = 0; j < n; j++) {
        tmpB += r[j] * B[j][i];
        tmpC += r[j] * C[j][i];
      }
      Br.push(tmpB);
      Cr.push(tmpC);
    }

    // Compute A * Br - Cr
    P = [];
    for (i = 0; i < n; i++) {
      tmp = 0;
      for (j = 0; j < n; j++) {
        tmp += (A[i][j] * Br[i]) - Cr[i];
      }
      P.push(tmp);
    }

    for (i = 0; i < n; i++) {
      if (P[i] !== 0) {
        
        console.log(`P[${i}] !== 0 (${P[i]}), exit`);
        
        return false;
      }
    }

    console.log('Result vector is identity, continue...');
    
  }

  return true;
}

FreivaldsAlgorithm();