Freivalds Algorithm: 행렬 곱 결과 검증
Freivalds 알고리즘은 행렬 곱 자체를 O(N²)에 계산하는 방법이 아닙니다. 이미 주어진 N×N 정수 행렬 A, B, C에 대해 AB=C인지 확률적으로 검증합니다. 한 번의 검증에는 행렬-벡터 곱 세 번이 필요해 O(N²)입니다.
0 또는 1을 독립적으로 고른 벡터 r을 만들고 A(Br)와 Cr을 비교합니다. AB=C라면 정확한 정수 연산에서 항상 일치합니다. AB≠C인데 우연히 일치할 확률은 한 번에 최대 1/2입니다. 독립적으로 k회 반복하면 잘못된 곱을 통과시키는 확률은 최대 2⁻ᵏ입니다. 통과는 정확하다는 증명이 아니라 오류를 발견하지 못했다는 뜻입니다.
import java.util.Random;
public class Freivalds {
static long[] multiply(long[][] matrix, long[] vector) {
int n = vector.length;
if (matrix.length != n) throw new IllegalArgumentException("크기 불일치");
long[] result = new long[n];
for (int i = 0; i < n; i++) {
if (matrix[i].length != n) throw new IllegalArgumentException("정방행렬 필요");
for (int k = 0; k < n; k++) {
result[i] = Math.addExact(result[i],
Math.multiplyExact(matrix[i][k], vector[k]));
}
}
return result;
}
static boolean verify(long[][] a, long[][] b, long[][] c,
int repetitions, Random random) {
if (repetitions <= 0) throw new IllegalArgumentException("반복 횟수는 양수");
int n = a.length;
for (int trial = 0; trial < repetitions; trial++) {
long[] r = new long[n];
for (int i = 0; i < n; i++) r[i] = random.nextBoolean() ? 1 : 0;
long[] abr = multiply(a, multiply(b, r));
long[] cr = multiply(c, r);
for (int i = 0; i < n; i++) {
if (abr[i] != cr[i]) return false;
}
}
return true;
}
}기존 구현은 a[i][k] * b[i][j]로 벡터의 잘못된 행을 사용하고 보조 클래스의 메서드를 잘못 호출했습니다. 위 구현은 matrix[i][k] * vector[k]를 사용합니다. Math.multiplyExact와 addExact는 long 범위를 넘으면 예외를 던집니다. 큰 정수 입력에는 BigInteger 또는 오류 확률 분석을 포함한 적절한 유한체 연산을 사용해야 합니다. double을 쓴다면 반올림 오차 때문에 정확한 0 비교가 안전하지 않으며 이 정수 증명을 그대로 적용할 수 없습니다.
예를 들어 A가 단위행렬이고 B가 [[1,2],[3,4]]라면 올바른 C는 B입니다. C의 오른쪽 아래 값을 5로 바꾸고 반복 시험하면 오류를 검출해야 합니다. 잘못된 C라도 무작위 벡터가 우연히 차이를 가리지 못할 수 있으므로 단일 시행만으로 오류 검출을 보장하지 않습니다.
이 글은 과거 학습 기록으로 검색에서 제외한 상태를 유지합니다.
