[Algorithm] Freivalds Algorithm

Freivalds Algorithm은 행렬 A,B 그리고 C가 있을 때 $AB=C$가 True/False인지 $O({n}^{2})$의 시간복잡도로 판별하는 알고리즘이다.

일반적인 행렬 곱셈을 이용하면 $O({n}^{3})$의 시간이 걸리고

Strassen(슈트라센) 행렬곱을 이용하면 $O({n}^{2.807})$의 시간이,

Coppersmith–Winograd(코퍼스미스-위노그라드) 행렬곱을 이용해도 $O({n}^{2.3727})$의 시간이 걸린다.

알고리즘

설명에 앞서 행렬곱은 아래와 같이 정의된다.

비결정론적 알고리즘인 프리발즈 알고리즘은 아래와 같은 절차를 거친다.
0과 1로 랜덤하게 채워진 열벡터 $r$을 생성하고
$A(Br)=Cr$ 인지 아닌지 확인한다.

위 수식이 한 번이라도 False가 나오면 $AB=C$는 False가 되고,

위 방법을 k번 반복하여 모두 일치했다면 $AB=C$는 True라고 가정한다.
($\frac{1}{{2}^{k}}$의 오답률을 가진다.)

증명

먼저, 만약 $A(Br)\neq Cr$ 라면 당연히 $AB \neq C$이다.

이제 $A(Br) = Cr$이 True여도 실제 $AB=C$는 False일 수 있다. 그럴 확률이 어떻게 나오는지 계산해보자.

$D=AB-C$ 라고 정의하자, 이제 $D \neq 0$ (D는 영행렬이 아니면서)
이면서 $Dr=0$($Dr$은 열벡터)인 상황인 경우의 확률을 찾아야 한다.

여기서 $D \neq 0$이기 때문에 행렬 D의 원소 ${d}_{ij}$ 중 하나 이상은 반드시 0이 아니게 된다.

하지만 $Dr=0$ 이기 때문에, $\sum_{j=0}^{N} d_{ij} \cdot r_{j} = 0$ 이 되어야 한다.

(Dr의 모든 원소가 0이 되어야 하기 때문)

• $P(Dr=0)$ 은 열벡터 모두가 0이 될 확률이고,

• $P(\sum_{j=0}^{N} d_{ij} \cdot r_{j} = 0)$은 열벡터의 원소 1개가 0일 확률이다.

따라서, $P(Dr=0)$ < $P(\sum_{j=0}^{N} d_{ij} \cdot r_{j} = 0)$ 가 된다.

여기서 우항을 ${r}_{j}$에 대한 식으로 바꾸어 보면 아래와 같다.

$P(r_{j} = \frac{(\sum_{j=0}^{N} d_{ij} \cdot r_{j}) - d_{ij} \cdot r_{j}}{d_{ij}})$

위 식은 $r_{j}$가 어떠한 값을 가질 확률인데 $r_{j}$는 0또는 1의 값만 가질 수 있다. 따라서 $P(r_{j}=0)$ 과 $P(r_{j}=1)$ 은 각각 $\frac{1}{2}$이다.

결론적으로, $P(Dr=0)$ < $\frac{1}{2}$ 이므로 이를 k번 반복하게 되면 오답률은 $\frac{1}{{2}^{k}}$로 줄어든다.

코드

using Mat = vector<vector<int>>;
bool Freivalds(Mat& A, Mat& B, Mat& C, int K, int x, int y) {
	int  t = 20;
	while (t--) {
		vector<int> r(K);
		generate(r.begin(),r.end(), []()->int {return rand() % 2; });
		vector<int> Br(K);
		for (int i = 0; i < K; i++) {	
			Br[i]=inner_product(r.begin(), r.end(), B[y+i].begin()+x, 0);
		}
		for (int i = 0; i < K; i++) {
			if (inner_product(Br.begin(), Br.end(), A[i].begin(), 0) - inner_product(r.begin(), r.end(), C[i].begin(), 0) != 0)
				return false;
		}
	}
	return true;
}

References

• https://en.wikipedia.org/wiki/Freivalds%27_algorithm