Algoritmo de Freivalds

El algoritmo de Freivalds (llamado así en honor a Rūsiņš Mārtiņš Freivalds ) es un algoritmo probabilístico aleatorio utilizado para verificar la multiplicación de matrices . Dadas tres matrices n × n $A$ , $B$ , y $C$ , un problema general es verificar si $A\times B=C$ Un algoritmo ingenuo calcularía el producto . $A\times B$ explícitamente y comparar término por término si este producto es igual a $C$ Sin embargo, el algoritmo de multiplicación de matrices más conocido se ejecuta en $O(n^{2.372})$ tiempo. El algoritmo de Freivalds utiliza la aleatorización para reducir este límite de tiempo a $O(n^{2})$ ^{[ 1 ]} con alta probabilidad. En $O(kn^{2})$ tiempo el algoritmo puede verificar un producto matricial con una probabilidad de fallo menor que $2^{-k}$ .

El algoritmo

Aporte

Tres matrices n × n $A$ , $B$ , y $C$ .

Producción

Sí, si $A\times B=C$ ; No, de lo contrario.

Procedimiento

Generar un vector aleatorio 0/1 de n × 1 ${\vec {r}}$ .
Calcular ${\vec {P}}=A\times (B{\vec {r}})-C{\vec {r}}$ .
Mostrar "Sí" si ${\vec {P}}=(0,0,\ldots ,0)^{T}$ ; "No", de lo contrario.

Error

Si $A\times B=C$ , entonces el algoritmo siempre devuelve "Sí". Si $A\times B\neq C$ , entonces la probabilidad de que el algoritmo devuelva "Sí" es menor o igual a la mitad. Esto se denomina error unilateral .

Al iterar el algoritmo k veces y devolver "Sí" solo si todas las iteraciones dan como resultado "Sí", se obtiene un tiempo de ejecución de $O(kn^{2})$ y probabilidad de error de $\leq 1/2^{k}$ se logra.

Ejemplo

Supongamos que uno quisiera determinar si:

AB={\begin{bmatrix}2&3\\3&4\end{bmatrix}}{\begin{bmatrix}1&0\\1&2\end{bmatrix}}{\stackrel {?}{=}}{\begin{bmatrix}6&5\\8&7\end{bmatrix}}=C.

Se selecciona un vector aleatorio de dos elementos con entradas iguales a 0 o 1, por ejemplo : ${\vec {r}}={\begin{bmatrix}1\\1\end{bmatrix}}$ – y se utiliza para calcular:

{\begin{aligned}A\times (B{\vec {r}})-C{\vec {r}}&={\begin{bmatrix}2&3\\3&4\end{bmatrix}}\left({\begin{bmatrix}1&0\\1&2\end{bmatrix}}{\begin{bmatrix}1\\1\end{bmatrix}}\right)-{\begin{bmatrix}6&5\\8&7\end{bmatrix}}{\begin{bmatrix}1\\1\end{bmatrix}}\\&={\begin{bmatrix}2 &3\\3&4\end{bmatrix}}{\begin{bmatrix}1\\3\end{bmatrix}}-{\begin{bmatrix}11\\15\end{bmatrix}}\\&={\begin{bmatrix}11\\15\end{bmatrix}}-{\begin{bmatrix}11\\15\end{bmatrix}}\\&={\begin{bmatrix}0\\0\end{bmatrix}}.\end{aligned}}

Esto produce el vector cero, lo que sugiere la posibilidad de que AB = C. Sin embargo, si en un segundo intento el vector ${\vec {r}}={\begin{bmatrix}1\\0\end{bmatrix}}$ Si se selecciona, el resultado es:

A\times (B{\vec {r}})-C{\vec {r}}={\begin{bmatrix}2&3\\3&4\end{bmatrix}}\left({\begin{bmatrix}1&0\\1&2\end{bmatrix}}{\begin{bmatrix}1\\0\end{bmatrix}}\right)-{\begin{bmatrix}6&5\\8&7\end{bmatrix}}{\begin{bmatrix}1\\0\end{bmatrix}}={\begin{bmatrix}-1\\-1\end{bmatrix}}.

El resultado es distinto de cero, lo que demuestra que, de hecho, AB ≠ C.

Hay cuatro vectores de dos elementos 0/1, y la mitad de ellos dan el vector cero en este caso ( ${\vec {r}}={\begin{bmatrix}0\\0\end{bmatrix}}$ y ${\vec {r}}={\begin{bmatrix}1\\1\end{bmatrix}}$ ), por lo que la probabilidad de seleccionar aleatoriamente estos en dos ensayos (y concluir erróneamente que AB=C) es 1/2 ² o 1/4. En el caso general, la proporción de r que produce el vector cero puede ser menor que 1/2, y se utilizaría un mayor número de ensayos (como 20), lo que hace que la probabilidad de error sea muy pequeña.

Análisis de errores

Sea p la probabilidad de error. Afirmamos que si A × B = C , entonces p = 0, y si A × B ≠ C , entonces p ≤ 1/2.

Caso A × B = C

{\begin{aligned}{\vec {P}}&=A\times (B{\vec {r}})-C{\vec {r}}\\&=(A\times B){\vec {r}}-C{\vec {r}}\\&=(A\times BC){\vec {r}}\\&={\vec {0}}\end{aligned}}

Esto es independientemente del valor de ${\vec {r}}$ , ya que solo utiliza eso $A\times BC=0$ Por lo tanto, la probabilidad de error en este caso es:

\Pr[{\vec {P}}\neq 0]=0

Caso A × B ≠ C

Dejar $D$ de tal manera que

{\vec {P}}=D\times {\vec {r}}=(p_{1},p_{2},\dots ,p_{n})^{T}

Dónde

D=A\times BC=(d_{ij})

.

Desde $A\times B\neq C$ , tenemos que algún elemento de $D$ es distinto de cero. Supongamos que el elemento $d_{ij}\neq 0$ Por definición de multiplicación de matrices , tenemos:

p_{i}=\sum _{k=1}^{n}d_{ik}r_{k}=d_{i1}r_{1}+\cdots +d_{ij}r_{j}+\cdots +d_{in}r_{n}=d_{ij}r_{j}+y

.

Por alguna constante $y$ . Usando el teorema de Bayes , podemos particionar sobre $y$ :

Utilizamos eso:

\Pr[p_{i}=0|y=0]=\Pr[r_{j}=0]={\frac {1}{2}}

\Pr[p_{i}=0|y\neq 0]=\Pr[r_{j}=1\land d_{ij}=-y]\leq \Pr[r_{j}=1]={\frac {1}{2}}

Sustituyendo estos valores en la ecuación ( 1 ), obtenemos:

{\begin{aligned}\Pr[p_{i}=0]&\leq {\frac {1}{2}}\cdot \Pr[y=0]+{\frac {1}{2}}\cdot \Pr[y\neq 0]\\&={\frac {1}{2}}\cdot \Pr[y=0]+{\frac {1}{2}}\cdot (1-\Pr[y=0])\\&={\frac {1}{2}}\end{aligned}}

Por lo tanto,

\Pr[{\vec {P}}=0]=\Pr[p_{1}=0\land \dots \land p_{i}=0\land \dots \land p_{n}=0]\leq \Pr[p_{i}=0]\leq {\frac {1}{2}}.

Con esto concluye la demostración.

Ramificaciones

Un análisis algorítmico simple muestra que el tiempo de ejecución de este algoritmo es $O(n^{2})$ (en notación Big O ). Esto supera el tiempo de ejecución del algoritmo determinista clásico de $O(n^{3})$ (o $O(n^{2.372})$ si se utiliza la multiplicación rápida de matrices ). El análisis de errores también muestra que si se ejecuta el algoritmo $k$ veces, un margen de error de menos de $1/2^{k}$ Se puede lograr una cantidad exponencialmente pequeña. El algoritmo también es rápido en la práctica debido a la amplia disponibilidad de implementaciones rápidas para productos matriz-vector. Por lo tanto, la utilización de algoritmos aleatorios puede acelerar un algoritmo determinista muy lento .

El algoritmo de Freivalds aparece con frecuencia en las introducciones a los algoritmos probabilísticos debido a su simplicidad y a cómo ilustra la superioridad de los algoritmos probabilísticos en la práctica para algunos problemas.

Véase también

Lema de Schwartz-Zippel

Referencias

↑ Raghavan, Prabhakar (1997). "Algoritmos aleatorios" . ACM Computing Surveys . 28 : 33–37 . doi : 10.1145/234313.234327 . S2CID 207196543 .

Freivalds, R. (1977). «Las máquinas probabilísticas pueden usar menos tiempo de ejecución». Procesamiento de la información 77 : actas del Congreso IFIP 77, Toronto, 8-12 de agosto de 1977. North-Holland. págs. 839-842 . ISBN 0-7204-0755-9OCLC 878720415
Mitzenmacher, Michael ; Upfal, Eli (2005). "1.3 Aplicación: Verificación de la multiplicación de matrices" . Probabilidad y computación: Algoritmos aleatorios y análisis probabilístico . Cambridge University Press. pp. 8–12 . ISBN 0-521-83540-2.

[1] Raghavan, Prabhakar (1997). "Algoritmos aleatorios" . ACM Computing Surveys . 28 : 33–37 . doi : 10.1145/234313.234327 . S2CID 207196543 .

[ 1 ]