Freivalds' algorithm

Freivalds' algorithm (named after <a href="/facts/R%C5%ABsi%C5%86%C5%A1_M%C4%81rti%C5%86%C5%A1_Freivalds/MzH4x5JP">Rūsiņš Mārtiņš Freivalds</a>) is a probabilistic <a href="/facts/Randomized_algorithm/Fngl1zgk">randomized algorithm</a> used to verify <a href="/facts/Matrix_multiplication/lYDB6Ro2">matrix multiplication</a>. Given three n × n <a href="/facts/Matrix_(mathematics)/qa8FI4ko">matrices</a> 
 
 
 
 A
 
 
 {\displaystyle A}
 
, 
 
 
 
 B
 
 
 {\displaystyle B}
 
, and 
 
 
 
 C
 
 
 {\displaystyle C}
 
, a general problem is to verify whether 
 
 
 
 A
 ×
 B
 =
 C
 
 
 {\displaystyle A\times B=C}
 
. A naïve <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> would compute the product 
 
 
 
 A
 ×
 B
 
 
 {\displaystyle A\times B}
 
 explicitly and compare term by term whether this product equals 
 
 
 
 C
 
 
 {\displaystyle C}
 
. However, the <a href="/facts/Computational_complexity_of_matrix_multiplication/KCn5KUzd">best known matrix multiplication algorithm</a> runs in 
 
 
 
 O
 (
 
 n
 
 2.3729
 
 
 )
 
 
 {\displaystyle O(n^{2.3729})}
 
 time. Freivalds' algorithm utilizes <a href="/facts/Randomization/m5ctJfbM">randomization</a> in order to reduce this time bound to 
 
 
 
 O
 (
 
 n
 
 2
 
 
 )
 
 
 {\displaystyle O(n^{2})}

<a href="/facts/With_high_probability/eBttFkd4">with high probability</a>. In 
 
 
 
 O
 (
 k
 
 n
 
 2
 
 
 )
 
 
 {\displaystyle O(kn^{2})}
 
 time the algorithm can verify a matrix product with probability of failure less than 
 
 
 
 
 2
 
 −
 k
 
 
 
 
 {\displaystyle 2^{-k}}
 
.

Freivalds' algorithm open-in-new

Freivalds' algorithm