Algoritmo de Freivalds

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

El algoritmo

Aporte

Tres matrices n  ×  n , , y . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$

Producción

Sí, si ; No, en caso contrario. ${\displaystyle A\times B=C}$

Procedimiento

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

Error

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

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

Ejemplo

Supongamos que uno quisiera determinar si:

${\displaystyle 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  , y se utiliza para calcular: ${\displaystyle {\vec {r}}={\begin{bmatrix}1\\1\end{bmatrix}}}$

${\displaystyle {\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 ensayo se selecciona el vector, el resultado se convierte en: ${\displaystyle {\vec {r}}={\begin{bmatrix}1\\0\end{bmatrix}}}$

${\displaystyle 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 ( y ), por lo que la probabilidad de seleccionarlos aleatoriamente en dos ensayos (y concluir falsamente que AB=C) es 1/2 ² o 1/4. En el caso general, la proporción de r que da como resultado el vector cero puede ser menor que 1/2, y se utilizaría un número mayor de ensayos (como 20), lo que hace que la probabilidad de error sea muy pequeña. ${\displaystyle {\vec {r}}={\begin{bmatrix}0\\0\end{bmatrix}}}$ ${\displaystyle {\vec {r}}={\begin{bmatrix}1\\1\end{bmatrix}}}$

Análisis de errores

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

CasoA × B=do

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

Esto es independiente del valor de , ya que solo utiliza ese . Por lo tanto, la probabilidad de error en este caso es: ${\displaystyle {\vec {r}}}$ ${\displaystyle A\times B-C=0}$

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

CasoA × B≠do

Sea tal que ${\displaystyle D}$

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

Dónde

${\displaystyle D=A\times B-C=(d_{ij})}$.

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

${\displaystyle 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}$.

Para alguna constante . Utilizando el teorema de Bayes , podemos dividir en : ${\displaystyle y}$ ${\displaystyle y}$

Nosotros lo usamos:

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

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

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

${\displaystyle {\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,

${\displaystyle \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 finaliza la prueba.

Ramificaciones

Un análisis algorítmico simple muestra que el tiempo de ejecución de este algoritmo es (en notación O mayúscula ). Esto supera el tiempo de ejecución del algoritmo determinista clásico de (o si se utiliza una multiplicación rápida de matrices ). El análisis de errores también muestra que si el algoritmo es tiempos de ejecución, se puede lograr un límite de error menor que , 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 . ${\displaystyle O(n^{2})}$ ${\displaystyle O(n^{3})}$ ${\displaystyle O(n^{2.373})}$ ${\displaystyle k}$ ${\displaystyle 1/2^{k}}$

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

Véase también

• Lema de Schwartz-Zippel

Referencias

1. Virginia Vassilevska Williams . "Rompiendo la barrera entre Coppersmith y Winograd". CiteSeerX  10.1.1.228.9947 .
2. Raghavan, Prabhakar (1997). "Algoritmos aleatorios". ACM Computing Surveys . 28 : 33–37. doi : 10.1145/234313.234327 . S2CID  207196543 . Consultado el 16 de diciembre de 2008 .

• Freivalds, R. (1977), “Las máquinas probabilísticas pueden utilizar menos tiempo de ejecución”, Congreso IFIP 1977, págs. 839–842.
• Mitzenmacher, Michael ; Upfal, Eli (2005), Probabilidad y computación: algoritmos aleatorios y análisis probabilístico, Cambridge University Press, págs. 8-12, ISBN 0521835402