프라이발츠(Freivalds) 알고리즘이란?
프라이발츠 알고리즘은 세 개의 정방행렬에 대해 matrix1 × matrix2 = matrix3라는 등식이 실제로 성립하는지 판별하는 확률적(randomized) 알고리즘입니다. 행렬 곱셈을 직접 수행해 결과를 비교하는 대신, 무작위로 생성한 벡터를 활용해 검증하기 때문에 매우 효율적입니다.
k회 반복했을 때 잘못된 판정을 내릴 확률은 2-k 미만이며, 시간 복잡도는 O(kn²)입니다. 일반적인 행렬 곱셈에는 O(n³)의 시간이 걸린다는 점을 고려하면, 이 알고리즘이 행렬 곱셈 결과 검증에 얼마나 유리한지 쉽게 알 수 있습니다.
알고리즘 동작 순서
시작
matrix1(n×n), matrix2(n×n), matrix3(n×n)을 입력으로 받는다.
// 검증해야 할 등식: matrix1 × matrix2 = matrix3
1) 각 성분이 0 또는 1인 n×1 크기의 벡터 a를 균등 분포로 무작위 선택한다.
2) matrix2 × a와 matrix3 × a를 먼저 계산한 뒤,
matrix1 × (matrix2 × a) − matrix3 × a 값을 구한다.
3) 그 결과가 영벡터(zero vector)인지 확인한다.
4) 영벡터이면 행렬 곱셈이 올바른 것이고, 아니라면 틀린 것이다.
끝.
무작위 벡터 하나로 어떻게 검증이 가능할까?
만약 matrix1 × matrix2 ≠ matrix3라면, 두 곱의 차 D = matrix1 × matrix2 − matrix3는 영행렬이 아닙니다. 영행렬이 아닌 행렬에 0과 1로 이루어진 임의의 벡터 a를 곱했을 때 결과가 우연히 영벡터가 될 확률은 최대 1/2입니다. 따라서 이 검사를 k번 반복하면 오류를 놓칠 확률이 2-k 이하로 급격히 줄어들어, 반복 횟수를 늘릴수록 신뢰도가 높아집니다.
C++ 구현 코드
아래 코드는 사용자로부터 두 개의 n×n 행렬과 결과 행렬을 입력받은 뒤, 프라이발츠 알고리즘을 적용해 곱셈 결과가 맞는지 검증합니다.
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
int main(int argc, char **argv) {
srand(time(NULL)); // 실행마다 다른 난수가 나오도록 시드 설정
cout << "행렬의 차원(n)을 입력하세요: ";
int n;
cin >> n;
cout << "첫 번째 행렬을 입력하세요:\n";
double matrix1[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> matrix1[i][j];
cout << "두 번째 행렬을 입력하세요:\n";
double matrix2[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> matrix2[i][j];
cout << "결과 행렬을 입력하세요:\n";
double matrix3[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> matrix3[i][j];
// 1단계: 0 또는 1로 이루어진 무작위 벡터 a 생성
double a[n][1] = {};
for (int i = 0; i < n; i++)
a[i][0] = rand() % 2;
// 2단계: matrix2 × a 계산
double matrix2a[n][1] = {};
for (int i = 0; i < n; i++)
for (int k = 0; k < n; k++)
matrix2a[i][0] += matrix2[i][k] * a[k][0];
// matrix3 × a 계산
double matrix3a[n][1] = {};
for (int i = 0; i < n; i++)
for (int k = 0; k < n; k++)
matrix3a[i][0] += matrix3[i][k] * a[k][0];
// matrix1 × (matrix2 × a) 계산
double matrix12a[n][1] = {};
for (int i = 0; i < n; i++)
for (int k = 0; k < n; k++)
matrix12a[i][0] += matrix1[i][k] * matrix2a[k][0];
// 3단계: (matrix1 × matrix2 × a) − (matrix3 × a)가 영벡터인지 검사
bool flag = true;
for (int i = 0; i < n; i++) {
if (matrix12a[i][0] - matrix3a[i][0] != 0)
flag = false;
}
// 4단계: 결과 출력
if (flag)
cout << "올바른 결과 행렬입니다.";
else
cout << "올바른 결과 행렬이 아닙니다.";
return 0;
}
참고: 지역 변수로 선언된 배열은 초기화하지 않으면 쓰레기 값(garbage value)을 가질 수 있으므로, 위 코드처럼 = {}로 0으로 초기화하는 것이 안전합니다. 또한 srand(time(NULL))을 추가하면 프로그램을 실행할 때마다 서로 다른 무작위 벡터가 선택됩니다.
실행 예제
예제 1 — 곱셈이 올바른 경우
행렬의 차원(n)을 입력하세요: 2 첫 번째 행렬을 입력하세요: 1 2 3 4 두 번째 행렬을 입력하세요: 2 0 1 2 결과 행렬을 입력하세요: 4 4 10 8 올바른 결과 행렬입니다.
실제로 [1 2; 3 4] × [2 0; 1 2]를 계산하면 [4 4; 10 8]이 되므로, 프로그램이 올바르게 판정한 것을 확인할 수 있습니다.
예제 2 — 곱셈이 틀린 경우
행렬의 차원(n)을 입력하세요: 2 첫 번째 행렬을 입력하세요: 1 2 3 4 두 번째 행렬을 입력하세요: 2 0 1 2 결과 행렬을 입력하세요: 4 5 5 5 올바른 결과 행렬이 아닙니다.
입력된 결과 행렬이 실제 곱셈 결과와 다르므로, 프로그램은 해당 행렬이 올바르지 않다고 판정합니다.
마무리
프라이발츠 알고리즘은 몬테카를로(Monte Carlo) 방식의 대표적인 확률적 검증 기법입니다. 전체 행렬 곱셈(O(n³))을 수행하지 않고도 O(kn²) 시간 안에 높은 신뢰도로 결과를 확인할 수 있어, 대규모 행렬 연산의 무결성 검사나 수치 해석 분야에서 널리 활용됩니다. 필요하다면 반복 횟수 k를 늘려 오류 확률을 지수적으로 줄일 수 있다는 점도 기억해 두세요.