Algoritmo Freivalds
O algoritmo Freivalds (nomeado após Rūsiņš Mārtiņš Freivalds ) é um teste probabilístico para verificar o resultado de um produto de matriz . Dadas três matrizes , e o problema é verificar se . Para resolvê-lo, o algoritmo ingênuo calcula o produto explicitamente e compara o resultado termo a termo com . No entanto, o algoritmo de produto de matriz mais conhecido é executado no tempo . O algoritmo Freivalds usa randomização para reduzir esse limite com uma alta probabilidade. Ele pode verificar um produto de matriz no tempo com uma probabilidade de falha menor que .
NO{\ displaystyle A}
B{\ displaystyle B}
VS{\ displaystyle C}
NO×B=VS{\ displaystyle A \ times B = C}
NO×B{\ displaystyle A \ times B}
VS{\ displaystyle C}
O(não2,3729){\ displaystyle O (n ^ {2,3729})}
O(não2){\ displaystyle O (n ^ {2})}
O(knão2){\ displaystyle O (kn ^ {2})}
2-k{\ displaystyle 2 ^ {- k}}![{\ displaystyle 2 ^ {- k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d5ba5275e798107d7738afeb76e2bdb91cd37e0f)
Algoritmo
Procedimento
O princípio do algoritmo consiste em verificar se, durante três n × n matrizes observou , e se a igualdade se verifica ou não.
NO{\ displaystyle A}
B{\ displaystyle B}
VS{\ displaystyle C}
NO×B=VS{\ displaystyle A \ times B = C}![{\ displaystyle A \ times B = C}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cfec2929c0c42a7dee59545916c8ea52a98a38b)
As três etapas são então realizadas:
- Gere um vetor aleatório de componentes 0 ou 1.r→{\ displaystyle {\ vec {r}}}
![\ vec {r}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6aec3c9ce13b53e9e24c98e7cce4212627884c91)
- Calcule .P→=NO×(Br→)-VSr→{\ displaystyle {\ vec {P}} = A \ vezes (B {\ vec {r}}) - C {\ vec {r}}}
![{\ displaystyle {\ vec {P}} = A \ vezes (B {\ vec {r}}) - C {\ vec {r}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c55ffece78bdeea5626b86ad40052b8894c8fe3b)
- Retorne Sim se ; Não o contrário.P→=(0,0,...,0)T{\ displaystyle {\ vec {P}} = (0,0, \ ldots, 0) ^ {T}}
![{\ displaystyle {\ vec {P}} = (0,0, \ ldots, 0) ^ {T}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/67e31769eff537e409f3c03ed9f0b6631fa6db1e)
Erro
Se , então o algoritmo sempre retorna Sim . Se , então a probabilidade de que o algoritmo retorne Sim é menor ou igual a 1/2.
NO×B=VS{\ displaystyle A \ times B = C}
NO×B≠VS{\ displaystyle A \ times B \ neq C}![{\ displaystyle A \ times B \ neq C}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd43f41eab0fa586931b5dbdb1e467da1460f12a)
Ao repetir o algoritmo k vezes e retornar Sim se e somente se todas as iterações retornarem Sim , a complexidade de tempo do teste é e sua probabilidade de erro é menor ou igual a .
O(knão2){\ displaystyle O (kn ^ {2})}
1/2k{\ displaystyle 1/2 ^ {k}}![{\ displaystyle 1/2 ^ {k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f0534932a3a6b23dd2fc59ffa9a05b5f27181dd3)
Exemplo
Suponha que queremos verificar se:
NOB=[2334][1012]=?[6587]=VS.{\ displaystyle AB = {\ begin {bmatrix} 2 e 3 \\ 3 & 4 \ end {bmatrix}} {\ begin {bmatrix} 1 e 0 \\ 1 & 2 \ end {bmatrix}} {\ stackrel {? } {=}} {\ begin {bmatrix} 6 e 5 \\ 8 e 7 \ end {bmatrix}} = C.}![{\ displaystyle AB = {\ begin {bmatrix} 2 e 3 \\ 3 & 4 \ end {bmatrix}} {\ begin {bmatrix} 1 e 0 \\ 1 & 2 \ end {bmatrix}} {\ stackrel {? } {=}} {\ begin {bmatrix} 6 e 5 \\ 8 e 7 \ end {bmatrix}} = C.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40b8b964afcdf0a656d6335c6eee3d9605409700)
Um vetor aleatório 2 × 1 de componentes iguais a 0 ou 1 é selecionado - por exemplo, - e usado para calcular:
r→=[11]{\ displaystyle {\ vec {r}} = {\ begin {bmatrix} 1 \\ 1 \ end {bmatrix}}}![{\ displaystyle {\ vec {r}} = {\ begin {bmatrix} 1 \\ 1 \ end {bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d55f580ed230f4d546f25e6210e2d7bfbb319b25)
NO×(Br→)-VSr→=[2334]([1012][11])-[6587][11]=[2334][13]-[1115]=[1115]-[1115]=[00].{\ displaystyle {\ begin {alinhados} 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 e 5 \\ 8 e 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 { alinhado}}}![{\ displaystyle {\ begin {alinhados} 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 e 5 \\ 8 e 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 { alinhado}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d3c195761cf6bd80066615a92dc1ce584b12f17)
O resultado é o vetor zero que sugere a possibilidade de AB = C. No entanto, se o vetor for selecionado para uma segunda iteração, o resultado será:
r→=[10]{\ displaystyle {\ vec {r}} = {\ begin {bmatrix} 1 \\ 0 \ end {bmatrix}}}![{\ displaystyle {\ vec {r}} = {\ begin {bmatrix} 1 \\ 0 \ end {bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e4d6b9520ed8d052aa46476b237953ae7db3e1b2)
NO×(Br→)-VSr→=[2334]([1012][10])-[6587][10]=[-1-1].{\ displaystyle A \ times (B {\ vec {r}}) - C {\ vec {r}} = {\ begin {bmatrix} 2 e 3 \\ 3 & 4 \ end {bmatrix}} \ left ({ \ begin {bmatrix} 1 & 0 \\ 1 & 2 \ end {bmatrix}} {\ begin {bmatrix} 1 \\ 0 \ end {bmatrix}} \ right) - {\ begin {bmatrix} 6 e 5 \\ 8 e 7 \ end {bmatriz}} {\ begin {bmatrix} 1 \\ 0 \ end {bmatrix}} = {\ begin {bmatrix} -1 \\ - 1 \ end {bmatrix}}.}![{\ displaystyle A \ times (B {\ vec {r}}) - C {\ vec {r}} = {\ begin {bmatrix} 2 e 3 \\ 3 & 4 \ end {bmatrix}} \ left ({ \ begin {bmatrix} 1 & 0 \\ 1 & 2 \ end {bmatrix}} {\ begin {bmatrix} 1 \\ 0 \ end {bmatrix}} \ right) - {\ begin {bmatrix} 6 e 5 \\ 8 e 7 \ end {bmatriz}} {\ begin {bmatrix} 1 \\ 0 \ end {bmatrix}} = {\ begin {bmatrix} -1 \\ - 1 \ end {bmatrix}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f350143b68beb89ba227ad3c703cb97fac29c3c)
O resultado não é mais zero, o que prova que AB ≠ C.
Existem quatro vetores 0/1 de dois componentes. Metade deles leva ao vetor zero ( e ) de forma que a probabilidade de escolher aleatoriamente esses dois vetores (e, portanto, de concluir erroneamente que AB = C) é 1/2 2 ou 1/4. No caso geral, a proporção de vetores r que conduzem ao vetor zero pode ser menor que 1/2. Um grande número de tentativas são realizadas para tornar a probabilidade de erro muito baixa.
r→=[00]{\ displaystyle {\ vec {r}} = {\ begin {bmatrix} 0 \\ 0 \ end {bmatrix}}}
r→=[11]{\ displaystyle {\ vec {r}} = {\ begin {bmatrix} 1 \\ 1 \ end {bmatrix}}}![{\ displaystyle {\ vec {r}} = {\ begin {bmatrix} 1 \\ 1 \ end {bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d55f580ed230f4d546f25e6210e2d7bfbb319b25)
Probabilidade de erro
Seja p a probabilidade de erro. Se A × B = C então p = 0, e se A × B ≠ C então p ≤ 1/2.
Caso A × B = C
P→=NO×(Br→)-VSr→=(NO×B)r→-VSr→=(NO×B-VS)r→=0→{\ displaystyle {\ begin {align} {\ 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 {alinhado}} }![{\ displaystyle {\ begin {align} {\ 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 {alinhado}} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/5fabd27ff04a5b967fc378a944e3a230a6d6339c)
Esse resultado é independente do valor de porque usa apenas igualdade . Portanto, a probabilidade de erro neste caso é:
r→{\ displaystyle {\ vec {r}}}
NO×B-VS=0{\ displaystyle A \ times BC = 0}![{\ displaystyle A \ times BC = 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e25224bc93c551b9f37f625bafdb78016ed60a34)
Pr[P→≠0]=0{\ displaystyle \ Pr [{\ vec {P}} \ neq 0] = 0}![{\ displaystyle \ Pr [{\ vec {P}} \ neq 0] = 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c73087a7efc162b4e75c6865e98c1d05aec25a0a)
Caso A × B ≠ C
É
P→=D×r→=(p1,p2,...,pnão)T{\ displaystyle {\ vec {P}} = D \ times {\ vec {r}} = (p_ {1}, p_ {2}, \ dots, p_ {n}) ^ {T}}![{\ displaystyle {\ vec {P}} = D \ times {\ vec {r}} = (p_ {1}, p_ {2}, \ dots, p_ {n}) ^ {T}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c7bbb1d0196e78bfa7347345e0b05877f8616198)
ou
D=NO×B-VS=(deuj){\ displaystyle D = A \ times BC = (d_ {ij})}![{\ displaystyle D = A \ times BC = (d_ {ij})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7cea2e204c485325219eb651415d8e5540f16e36)
.
Uma vez que alguns componentes de são necessariamente diferentes de zero. Suponha o elemento . Pela definição do produto de matriz , vem:
NO×B≠VS{\ displaystyle A \ times B \ neq C}
D{\ displaystyle D}
deuj≠0{\ displaystyle d_ {ij} \ neq 0}![{\ displaystyle d_ {ij} \ neq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19a5424b588edf998191cda7aeab206c478ade2a)
peu=∑k=1nãodeukrk=deu1r1+⋯+deujrj+⋯+deunãornão=deujrj+y{\ 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}![{\ 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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/21256efad6a1f0e3164fb5c714e76fd0f30db518)
.
para alguns . Pelo teorema de Bayes , temos:
y{\ displaystyle y}![y](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8a6208ec717213d4317e666f1ae872e00620a0d)
Pr[peu=0]=Pr[peu=0|y=0]⋅Pr[y=0]+Pr[peu=0|y≠0]⋅Pr[y≠0]{\ displaystyle \ Pr [p_ {i} = 0] = \ Pr [p_ {i} = 0 | y = 0] \ cdot \ Pr [y = 0] \, + \, \ Pr [p_ {i} = 0 | y \ neq 0] \ cdot \ Pr [y \ neq 0]}![{\ displaystyle \ Pr [p_ {i} = 0] = \ Pr [p_ {i} = 0 | y = 0] \ cdot \ Pr [y = 0] \, + \, \ Pr [p_ {i} = 0 | y \ neq 0] \ cdot \ Pr [y \ neq 0]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee0c1200643490dc0be3f3c50339db18734b4e7c)
Usando os resultados
Pr[peu=0|y=0]=Pr[rj=0]=12{\ displaystyle \ Pr [p_ {i} = 0 | y = 0] = \ Pr [r_ {j} = 0] = {\ frac {1} {2}}}
Pr[peu=0|y≠0]=Pr[rj=1∧deuj=-y]≤Pr[rj=1]=12{\ displaystyle \ Pr [p_ {i} = 0 | y \ neq 0] = \ Pr [r_ {j} = 1 \ land d_ {ij} = - y] \ leq \ Pr [r_ {j} = 1] = {\ frac {1} {2}}}
na equação anterior, o resultado é:
Pr[peu=0]≤12⋅Pr[y=0]+12⋅Pr[y≠0]=12⋅Pr[y=0]+12⋅(1-Pr[y=0])=12{\ displaystyle {\ begin {alinhados} \ 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 {alinhado}}}![{\ displaystyle {\ begin {alinhados} \ 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 {alinhado}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac04124bbed15468913248264a3f495d919efe2e)
Portanto,
Pr[P→=0]=Pr[p1=0∧⋯∧peu=0∧⋯∧pnão=0]≤Pr[peu=0]≤12.{\ 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}}.}![{\ 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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0e355ff8aa8a654e52019735c8e960fc2555f859)
Isso encerra a prova.
Complexidade
Uma análise simples desse algoritmo mostra uma complexidade de tempo de O ( n 2 ) que bate o algoritmo determinístico clássico em O ( n 3 ). A análise de erro mostra que após k execuções do algoritmo, a probabilidade de erro é menor que . Na prática, o algoritmo é rápido devido às implementações eficientes de cálculo de um produto matriz-vetor. Portanto, o uso de algoritmos aleatórios pode acelerar um algoritmo determinístico lento. O melhor algoritmo determinístico para a verificação do produto da matriz é atualmente uma variante do algoritmo Coppersmith-Winograd com um tempo de execução assintótico em O ( n 2,3729 ).
12k{\ displaystyle {\ frac {1} {2 ^ {k}}}}![{\ displaystyle {\ frac {1} {2 ^ {k}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7247a56934790ab90e0d85e41de5c34f629182da)
O algoritmo Freivalds freqüentemente aparece nas introduções aos algoritmos probabilísticos devido à sua simplicidade. Na prática, também ilustra a superioridade dos algoritmos probabilísticos em certos problemas.
Veja também
Notas
Referências
-
Virginia Vassilevska Williams, " Quebrando a barreira Coppersmith-Winograd "
-
Prabhakar Raghavan , “ Randomized algoritms, ” ACM Computing Surveys , vol. 28,1997( DOI 10.1145 / 234313.234327 , lido online , acessado em 16 de dezembro de 2008 )
- Freivalds, R. (1977), “Probabilistic Machines Can Use Less Running Time”, IFIP Congress 1977, pages 839-842.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">