Freivalds algoritme
Den Freivalds algoritmen (oppkalt etter Rūsiņš Mārtiņš Freivalds ) er en sannsynlighetstest for å kontrollere resultatet av et matriseprodukt . Gitt tre matriser , og problemet er å sjekke om . For å løse det, beregner den naive algoritmen produktet eksplisitt og sammenligner resultatuttrykket til begrepet med . Imidlertid kjører den mest kjente matriksproduktalgoritmen i tide . Freivalds-algoritmen bruker randomisering for å redusere denne bundet til med stor sannsynlighet. Det kan verifisere et matriksprodukt i tide med en feilsannsynlighet på mindre enn .
PÅ{\ displaystyle A}B{\ displaystyle B}VS{\ displaystyle C}PÅ×B=VS{\ displaystyle A \ times B = C}PÅ×B{\ displaystyle A \ times B}VS{\ displaystyle C}O(ikke2.3729){\ displaystyle O (n ^ {2.3729})}O(ikke2){\ displaystyle O (n ^ {2})}O(kikke2){\ displaystyle O (kn ^ {2})}2-k{\ displaystyle 2 ^ {- k}}
Algoritme
Fremgangsmåte
Prinsippet for algoritmen består i å kontrollere om det for tre n × n- matriser er notert , og om likheten er verifisert eller ikke.
PÅ{\ displaystyle A}B{\ displaystyle B}VS{\ displaystyle C}PÅ×B=VS{\ displaystyle A \ times B = C}
De tre trinnene blir deretter utført:
- Generer en tilfeldig vektor av komponentene 0 eller 1.r→{\ displaystyle {\ vec {r}}}
- Beregn .P→=PÅ×(Br→)-VSr→{\ displaystyle {\ vec {P}} = A \ ganger (B {\ vec {r}}) - C {\ vec {r}}}
- Returner Ja hvis ; Nei ellers.P→=(0,0,...,0)T{\ displaystyle {\ vec {P}} = (0,0, \ ldots, 0) ^ {T}}
Feil
Hvis , så returnerer algoritmen alltid Ja . Hvis , er sannsynligheten for at algoritmen returnerer Ja mindre enn eller lik 1/2.
PÅ×B=VS{\ displaystyle A \ times B = C}PÅ×B≠VS{\ displaystyle A \ times B \ neq C}
Ved å gjenta algoritmen k ganger og returnere Ja hvis og bare hvis alle iterasjonene returnerer Ja , er tidskompleksiteten til testen og feilsannsynligheten er mindre enn eller lik .
O(kikke2){\ displaystyle O (kn ^ {2})}1/2k{\ displaystyle 1/2 ^ {k}}
Eksempel
Anta at vi vil sjekke om:
PÅB=[2334][1012]=?[6587]=VS.{\ 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.}En 2 × 1 tilfeldig vektor av komponenter lik 0 eller 1 er valgt - for eksempel - og brukes til å beregne:
r→=[11]{\ displaystyle {\ vec {r}} = {\ begynn {bmatrix} 1 \\ 1 \ end {bmatrix}}}
PÅ×(Br→)-VSr→=[2334]([1012][11])-[6587][11]=[2334][13]-[1115]=[1115]-[1115]=[00].{\ displaystyle {\ begin {align} 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}} \ høyre) - {\ 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 { justert}}}Resultatet er nullvektoren som antyder muligheten for at AB = C. Hvis vektoren velges for en ny iterasjon, blir resultatet:
r→=[10]{\ displaystyle {\ vec {r}} = {\ begynn {bmatrix} 1 \\ 0 \ end {bmatrix}}}
PÅ×(Br→)-VSr→=[2334]([1012][10])-[6587][10]=[-1-1].{\ displaystyle A \ times (B {\ vec {r}}) - C {\ vec {r}} = {\ begin {bmatrix} 2 & 3 \\ 3 & 4 \ end {bmatrix}} \ left ({ \ begin {bmatrix} 1 og 0 \\ 1 og 2 \ slutt {bmatrix}} {\ begynn {bmatrix} 1 \\ 0 \ slutt {bmatrix}} \ høyre) - {\ begynn {bmatrix} 6 og 5 \\ 8 og 7 \ end {bmatrix}} {\ begin {bmatrix} 1 \\ 0 \ end {bmatrix}} = {\ begin {bmatrix} -1 \\ - 1 \ end {bmatrix}}.}Resultatet er ikke lenger null som beviser at AB ≠ C.
Det er fire to-komponent 0/1 vektorer. Halvparten av dem fører til nullvektoren ( og ) slik at sannsynligheten for å tilfeldig velge disse to vektorene (og derfor feilaktig konkludere med at AB = C) er 1/2 2 eller 1/4. Generelt sett kan andelen vektorer r som fører til nullvektoren være mindre enn 1/2. Et stort antall forsøk utføres for å gjøre sannsynligheten for feil svært lav.
r→=[00]{\ displaystyle {\ vec {r}} = {\ begin {bmatrix} 0 \\ 0 \ end {bmatrix}}}r→=[11]{\ displaystyle {\ vec {r}} = {\ begynn {bmatrix} 1 \\ 1 \ end {bmatrix}}}
Sannsynlighet for feil
La p være den sannsynligheten for feil. Hvis A × B = C så er p = 0, og hvis A × B ≠ C så p ≤ 1/2.
Sak A × B = C
P→=PÅ×(Br→)-VSr→=(PÅ×B)r→-VSr→=(PÅ×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 \ ganger f.Kr.) {\ vec {r}} \\ & = {\ vec {0}} \ end {align}} }Dette resultatet er uavhengig av verdien av fordi det bare bruker likhet . Derfor er sannsynligheten for feil i dette tilfellet:
r→{\ displaystyle {\ vec {r}}}PÅ×B-VS=0{\ displaystyle A \ times BC = 0}
Pr[P→≠0]=0{\ displaystyle \ Pr [{\ vec {P}} \ neq 0] = 0}
Sak A × B ≠ C
Er
P→=D×r→=(s1,s2,...,sikke)T{\ displaystyle {\ vec {P}} = D \ ganger {\ vec {r}} = (p_ {1}, p_ {2}, \ prikker, p_ {n}) ^ {T}}eller
D=PÅ×B-VS=(dJegj){\ displaystyle D = A \ ganger BC = (d_ {ij})}.
Siden noen komponenter av nødvendigvis ikke er null. Anta elementet . Ved definisjonen av matriksproduktet kommer det:
PÅ×B≠VS{\ displaystyle A \ times B \ neq C}D{\ displaystyle D}dJegj≠0{\ displaystyle d_ {ij} \ neq 0}
sJeg=∑k=1ikkedJegkrk=dJeg1r1+⋯+dJegjrj+⋯+dJegikkerikke=dJegjrj+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}.
for noen . Etter Bayes 'teorem har vi:
y{\ displaystyle y}
Pr[sJeg=0]=Pr[sJeg=0|y=0]⋅Pr[y=0]+Pr[sJeg=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]}Bruke resultatene
Pr[sJeg=0|y=0]=Pr[rj=0]=12{\ displaystyle \ Pr [p_ {i} = 0 | y = 0] = \ Pr [r_ {j} = 0] = {\ frac {1} {2}}}
Pr[sJeg=0|y≠0]=Pr[rj=1∧dJegj=-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}}}
i forrige ligning er resultatet:
Pr[sJeg=0]≤12⋅Pr[y=0]+12⋅Pr[y≠0]=12⋅Pr[y=0]+12⋅(1-Pr[y=0])=12{\ displaystyle {\ begin {align} \ 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 {align}}}Derfor,
Pr[P→=0]=Pr[s1=0∧⋯∧sJeg=0∧⋯∧sikke=0]≤Pr[sJeg=0]≤12.{\ displaystyle \ Pr [{\ vec {P}} = 0] = \ Pr [p_ {1} = 0 \ land \ prikker \ land p_ {i} = 0 \ land \ prikker \ land p_ {n} = 0 ] \ leq \ Pr [p_ {i} = 0] \ leq {\ frac {1} {2}}.}Dette avslutter beviset.
Kompleksitet
En enkel analyse av denne algoritmen viser en tidskompleksitet på O ( n 2 ) som slår den klassiske deterministiske algoritmen ved O ( n 3 ). Feilanalysen viser at etter k kjøringer av algoritmen er feil sannsynligheten mindre enn . I praksis er algoritmen rask på grunn av effektive implementeringer av beregning av et matrise-vektorprodukt. Derfor kan bruken av randomiserte algoritmer øke hastigheten på en sakte deterministisk algoritme . Den beste deterministiske algoritmen for verifisering av matriksproduktet er for tiden en variant av Coppersmith-Winograd-algoritmen med en asymptotisk utførelsestid i O ( n 2.3729 ).
12k{\ displaystyle {\ frac {1} {2 ^ {k}}}}
Freivalds algoritme vises ofte i introduksjoner til sannsynlighetsalgoritmer på grunn av sin enkelhet. I praksis illustrerer det også overlegenheten til sannsynlighetsalgoritmer i visse problemer.
Se også
Merknader
Referanser
-
Virginia Vassilevska Williams, " Breaking the Coppersmith-Winograd barrier "
-
Prabhakar Raghavan , “ Randomized algorithms, ” ACM Computing Surveys , vol. 28,1997( DOI 10.1145 / 234313.234327 , lest online , åpnet 16. desember 2008 )
- Freivalds, R. (1977), “Probabilistic Machines Can Use Less Running Time”, IFIP Congress 1977, side 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;">