�ݺ�ߣ

Beyond Problem Solving
2022. 09. 30(금)
18:00 ~ 21:00

Freivalds Algorithm
0
0
1
0
1
1
1
0
1 2 3 15 -1 -5 -2 8 9 0
1 6 8 -4 2 5 -1 9 9 9
7 7 7 7 7 7 7 7 7 7
-8 -1 7 8 5 8 9 28 9 1
X =
?
?
?
?
𝑂𝑂(𝑛𝑛2)
Freivalds Algorithm은 행렬 A,B 그리고 C가 있을 때,
AB=C가 True/False인지 𝑂𝑂(𝑛𝑛2
)의 시간복잡도로 판별하는 알고리즘이다.

Freivalds Algorithm
A
M
K
B
K
N
M C
N
X =
r
1
N r
1
N
X X
( )
A
M
K
B
K
N
M C
N
X = 𝑂𝑂(𝑛𝑛3
)
𝑂𝑂(𝑛𝑛2
) 𝑂𝑂(𝑛𝑛2
)

Freivalds Algorithm
A
M
K
B
K
N
M C
N
X =
r
1
N r
1
N
X X
( )
𝑂𝑂(𝑛𝑛2
) 𝑂𝑂(𝑛𝑛2)
A
M
K
Br
K
1
M Cr
1
X =
𝑂𝑂(𝑛𝑛2
)

Freivalds Algorithm
A
M
K
Br
K
1
M Cr
1
X =
𝑂𝑂(𝑛𝑛2
)
ABr
M
1
M Cr
1
=
𝑂𝑂(𝑛𝑛)
𝐴𝐴 𝐵𝐵𝐵𝐵 = 𝐶𝐶𝐶𝐶 인지 k번 검사한다.

Freivalds Algorithm
𝐴𝐴𝐴𝐴 = 𝐶𝐶 이라면 당연히 𝐴𝐴 𝐵𝐵𝐵𝐵 = 𝐶𝐶𝐶𝐶 이다.

Freivalds Algorithm
1 2 3 -15
1 6 8 -4
7 7 7 7
1 2 3
1 6 8
7 7 7
-8 -1 7
X
24 35 40 -2
63 94 107 17
63 105 126 -84
40 27 17 173
=
M
K
N
K M
N
1
0
1
1
X
-11
5
21
62
187
105
230
24 35 40 -2
63 94 107 17
63 105 126 -84
40 27 17 173
1
0
1
1
X
1 2 3
1 6 8
7 7 7
-8 -1 7
X
1 2 3 -15
1 6 8 -4
7 7 7 7
62
187
105
230
=

Freivalds Algorithm
그렇다고 𝐴𝐴 𝐵𝐵𝐵𝐵 = 𝐶𝐶𝐶𝐶 일 때 𝐴𝐴𝐴𝐴 = 𝐶𝐶 는 아니다!

Freivalds Algorithm
그렇지만 𝐴𝐴 𝐵𝐵𝐵𝐵 ≠ 𝐶𝐶𝐶𝐶 이라면 𝐴𝐴𝐴𝐴 ≠ 𝐶𝐶 이다.
그렇다고 𝐴𝐴 𝐵𝐵𝐵𝐵 = 𝐶𝐶𝐶𝐶 일 때 𝐴𝐴𝐴𝐴 = 𝐶𝐶 는 아니다!

Freivalds Algorithm
𝐷𝐷 = 𝐴𝐴𝐴𝐴 − 𝐶𝐶 라고 정의한다.
𝐷𝐷 ≠ 0 (𝐴𝐴𝐴𝐴 ≠ 𝐶𝐶 이므로 D는 영행렬이 아니다)
𝐷𝐷𝐷𝐷 = 0 이지만 𝐷𝐷 ≠ 0 경우와 확률을 찾아야 한다.

Freivalds Algorithm
𝐷𝐷 ≠ 0 (D가 영행렬이 아니므로 D의 원소 𝑑𝑑𝑖𝑖𝑖𝑖 중 하나 이상은 반드시 0이 아니다.

Freivalds Algorithm
하지만 𝐷𝐷𝐷𝐷 = 0 이기 때문에 ∑𝑗𝑗=0
𝑁𝑁
𝑑𝑑𝑖𝑖𝑖𝑖 � 𝑟𝑟
𝑗𝑗 = 0이 되어야 한다.

Freivalds Algorithm
𝑁𝑁
P(𝐷𝐷𝐷𝐷 = 0) 은 열벡터 모두가 0이 될 확률
P(∑𝑗𝑗=0
𝑁𝑁
𝑗𝑗 = 0)은 열벡터의 원소 1개가 0일 확률

Freivalds Algorithm
𝑁𝑁
P(∑𝑗𝑗=0
𝑁𝑁
P 𝐷𝐷𝐷𝐷 = 0 < P(�
𝑗𝑗=0
𝑁𝑁
𝑗𝑗 = 0)
열벡터 모두가 0이 될 확률보다 하나만 0일 확률이 더 높다.

Freivalds Algorithm
𝑁𝑁
P(∑𝑗𝑗=0
𝑁𝑁
P 𝐷𝐷𝐷𝐷 = 0 < P(�
𝑗𝑗=0
𝑁𝑁
𝑗𝑗 = 0)
여기서 우측항을 𝑟𝑟
𝑗𝑗에 대한 식으로 바꾸어 보면 위와 같다.
P 𝐷𝐷𝐷𝐷 = 0 < P(𝑟𝑟
𝑗𝑗 =
(∑𝑗𝑗=0
𝑁𝑁
𝑗𝑗) − 𝑑𝑑𝑖𝑖𝑖𝑖 � 𝑟𝑟
𝑗𝑗
𝑑𝑑𝑖𝑖𝑖𝑖
)

Freivalds Algorithm
𝑁𝑁
P(∑𝑗𝑗=0
𝑁𝑁
이는 𝑟𝑟
𝑗𝑗 가 어떠한 값을 가질 확률인데 r은 0또는 1만 가능하다.
𝑗𝑗 =
(∑𝑗𝑗=0
𝑁𝑁
𝑗𝑗
)
P(𝑟𝑟
𝑗𝑗)
P(𝑟𝑟
𝑗𝑗 = 0), P 𝑟𝑟
𝑗𝑗 = 1 모두 각각
1
2
이다.

Freivalds Algorithm
𝑁𝑁
P(∑𝑗𝑗=0
𝑁𝑁
이는 𝑟𝑟
𝑗𝑗 가 어떠한 값을 가질 확률인데 r은 0또는 1만 가능하다.
𝑗𝑗 =
(∑𝑗𝑗=0
𝑁𝑁
𝑗𝑗
)
P(𝑟𝑟
𝑗𝑗)
P(𝑟𝑟
𝑗𝑗 = 0), P 𝑟𝑟
𝑗𝑗 = 1 모두 각각
1
2
이다.
P 𝐷𝐷𝐷𝐷 = 0 <
1
2
이고 이를 K번 반복하면 오답률은
1
2𝑘𝑘 로 줄어든다.

Matrix multiply(Matrix& A, Matrix& B) {
int M = A.size();
int K = B.size();
int N = B[0].size();
Matrix C(M, vector<int>(N, 0));
for (int m = 0; m < M; m++) {
for (int n = 0; n < N; n++) {
int c = 0;
for (int k = 0; k < K; k++) {
c += A[m][k] * B[k][n];
}
C[m][n] = c;
}
}
return C;
}
C++
Freivalds Algorithm Matrix create_random_matrix(int rows, int cols) {
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<int> rand_int(-100,100);
Matrix mat(rows, vector<int>(cols, 0));
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
mat[y][x] = rand_int(gen);
}
}
return mat;
}
C++
bool Freivalds(Matrix& A, Matrix& B, Matrix& C) {
int t = 20;
const int K = B.size();
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<int> rand_int(0,1);
while (t--) {
vector<int> r(K);
generate(r.begin(), r.end(), [&]()->int {return rand_int(gen); });
vector<int> Br(K);
for (int i = 0; i < K; i++) {
Br[i] = inner_product(r.begin(), r.end(), B[i].begin(), 0);
}
for (int i = 0; i < K; i++) {
int ABr = inner_product(Br.begin(), Br.end(), A[i].begin(), 0);
int Cr = inner_product(r.begin(), r.end(), C[i].begin(), 0);
if (ABr!=Cr)
return false;
}
}
return true;
}
C++

�ݺ�ߣ

[FreivaldsAlgorithm]The Freivalds Algorithm is an algorithm that determines whether AB=C is true/false with a time complexity of O(n2) when there are matrices A, B, and C. This is a slide with an explanation and implementation code.

Recommended

More Related Content

Featured (20)

[FreivaldsAlgorithm]The Freivalds Algorithm is an algorithm that determines whether AB=C is true/false with a time complexity of O(n2) when there are matrices A, B, and C. This is a slide with an explanation and implementation code.