Freivald's algorithm

개요

Approximation, 확률론
A×B=C를 O(kN^2)에 해결하기

---

접근

기존의 행렬곱

1. 일반적인 상황은 아니지만, 두 행렬의 곱이 다른 행렬과 같은지 확인해야 하는 상황이 있다. A×B=C를 검증한다고 가정하자. 만약 A,B,C의 크기가 각각 [p,m], [m,q], [p,q] 라면

   1. 곱셈 연산을 하는데 p×m×q번의 연산이 필요하고,
   2. 정수행렬 C를 만들기 위해 p×q×4 만큼의 메모리가 필요하다.

2. 왜냐? 일반적으로 행렬곱 계산은 아래와 같이 해주기 때문이다.

    for (i = 0~p)
        for (j = 0~q)
            for (k = 0~m)
                C[i][j]+=A[i][k]*B[k][j]

3. 크기가 100×100정도라면 큰 문제가 아니다. 하지만 1000이면 1e9번의 연산을 해야하고, 시간을 1분을 주지 않는 이상 무조건 터진다. 크기가 10만 단위로 넘어간다면? 시간은 고사하고 1e10 크기의 배열을 만들 수 없어 메모리 초과가 나버린다.

4. 그래서 골드-플래 하위에서 다루는 행렬 문제들은 대부분 N이 100이하인 것들이다. 그렇다면 이렇게 크기가 큰 행렬의 곱셈 검증을 어떻게 할까?

사고방식

1. 이때 사용하는 것이 Freivald's algorithm이다. 가끔 우리는 완벽한 정답이 아니더라도 아주 근소한 오차를 정답으로 허용하곤 하는데, 이때 사용하는 방법은 휴리스틱, 확률론, 근사 알고리즘이 있다. 여기서 우리는 확률론을 사용할 것이다.
2. 프리발즈 알고리즘의 시작은 이렇다. 꼭 두 행렬이 같은지 보기 위해 N개의 열을 검사해야 할까? 만약 절반만 검사해 모두 같다면 두 행렬은 1/2의 확률로 같은 것 아닐까? 하는 것이다. 대신 절반만큼의 열 중 하나라도 다른 열이 있다면? 두 행렬은 무조건 다르다.
3. 이렇게 k번 검사를 해주면 (1/2)^k만큼의 확률로 같은 것이고, k를 10번만 해줘도 실제로는 다른 두 행렬이 같다고 검증될 확률은 0.09% 가 된다.

구체적 방법론

1. 그래서 랜덤이 어디있냐? 하면 바로 여기있다. 절반의 열을 선택하기 위해 사용하는 것이 열의 개수와 같은 크기의 0,1랜덤벡터이다. 인간이 무작위로 열을 선택해도 되지만 컴퓨터가 골라주는 편이 더 나으니까...

2. 우리가 사용하고자 하는 방법은 다음과 같다.

   ${A\times (B\times r) \neq C\times r => A\times B \neq C}$

   $A=(a_{ij})_{p \times m} \quad B=(b_{ij})_{m \times q} \quad r=(x_i)_{q \times 1}$

   이게 왜 되는지 말하기 이전에 시간복잡도부터 계산하자. 위에서 p×m×q 만큼의 연산이 필요하다고 했는데, 여기서는 B×r에 m×q만큼의 연산이, A×(B×r)에 p×m만큼의 연산이 필요하다.

1. 오른쪽의 C×r에는 p×q만큼의 연산이 필요하므로 총 연산은 p×m+m×q+q×p이고, k번 검증을 한다고 하면 O(N^3)의 시간복잡도를 O(kN^2)으로 줄여줄 수 있다. 그리고 앞서 말한 대로 k는 10-20번이면 충분하므로 시간 차원을 하나 줄여줄 수 있다.

왜 되는가?

1. 먼저 네 가지 상황을 가정하자. A×B=C에 대해 실제 일치 여부와 검증 여부에 따른 확률은 다음과 같다.

   실제\검증	O	X
   O	1	0
   X	p	1-p

   1. 실제로 같을 때는 정확한 검증이 가능하다. 왜냐? 하나라도 다른 열이 있다면 다르다 라는 검증 결과를 내놓는데, 두 행렬이 같다면 이 if문에 걸리는 일이 없기 때문이다.
   2. 실제로 다를 때는 정확한 검증이 불가능하다. 확률적으로 생각해야 하는데, 이 확률을 구해보자.

2. D=A×B-C라고 하자. 확률 p는 실제로 D에 0이 아닌 원소가 포함되었음에도 모두 0이라고 진단할 확률이다. 이 확률의 범위를 구하기 위해 극단적인 상황을 가정하자.

   1. 만약 모든 원소가 nonzero라면? p=0이고 이게 최솟값이 된다. 가장 오진을 할 가능성이 낮은 상황인 셈.
   2. 하나의 원소만 nonzero라면? 가장 오진을 하기 쉽다. 이 하나를 검출하지 못하면 안되기 때문이다. 이 상황을 아래에서 해결해보자.

3. D×r은 행렬곱셈 정의로 아래와 같이 표현 가능한데,

   ${X_i = (D \times r)_i = \sum (D_{ij} \times r_j)}$
   우리는 이런 진단을 내려버린 것이다.
   ${D_{ij}\neq 0\quad X_{i}=0}$
   이를 위해서는 $D_{ij}$를 유일하게 포함한 $X_{i}$를 구할때 $r_{j}$가 nonzero여야 한다. 그럼 이 확률은? r의 원소 하나를 결정할 확률이므로 1/2이 된다.

4. 결국 0<=p<=1/2이므로 실제 다른 상황을 다르게 검증할 확률인 1-p의 범위 또한 1/2<=p<=1이 된다. 즉 한 번 시행에서 최소 1/2확률로 정확한 진단을 내릴 수 있다. 이 시행을 k번 반복하면? 확률은 $\dfrac{1}{2^k}$이 되는 것이다.

내가 이해가 잘 안돼서 좀 거창하고 어렵게 설명한 것 같은데 실상은 단순하다.

---

Source code

bool freivald() {
    int R=25;
    while(R--) {
        for (auto &x:r) x=rand()%2;
        if (A*(B*r)!=C*r)
            return 0;
    }
    return 1;
}

---

관련문제

P2 3847 Comparing answers : 풀이
D5 13165 이것도 해결해 보시지: 풀이
D2 17313 Inner product

---

참조

Wikipedia-freivald's algorithm
네이버블로그-레프네약방