Freivalds' algorithm
Freivalds' algorithm (named after Rūsiņš Mārtiņš Freivalds) is a probabilistic randomized algorithm used to verify matrix multiplication. Given three n × n matrices , , and , a general problem is to verify whether . A naïve algorithm would compute the product explicitly and compare term by term whether this product equals . However, the best known matrix multiplication algorithm runs in time. Freivalds' algorithm utilizes randomization in order to reduce this time bound to with high probability. In time the algorithm can verify a matrix product with probability of failure less than .
- Comment
- enFreivalds' algorithm (named after Rūsiņš Mārtiņš Freivalds) is a probabilistic randomized algorithm used to verify matrix multiplication. Given three n × n matrices , , and , a general problem is to verify whether . A naïve algorithm would compute the product explicitly and compare term by term whether this product equals . However, the best known matrix multiplication algorithm runs in time. Freivalds' algorithm utilizes randomization in order to reduce this time bound to with high probability. In time the algorithm can verify a matrix product with probability of failure less than .
- Has abstract
- enFreivalds' algorithm (named after Rūsiņš Mārtiņš Freivalds) is a probabilistic randomized algorithm used to verify matrix multiplication. Given three n × n matrices , , and , a general problem is to verify whether . A naïve algorithm would compute the product explicitly and compare term by term whether this product equals . However, the best known matrix multiplication algorithm runs in time. Freivalds' algorithm utilizes randomization in order to reduce this time bound to with high probability. In time the algorithm can verify a matrix product with probability of failure less than .
- Is primary topic of
- Freivalds' algorithm
- Label
- enFreivalds' algorithm
- Link from a Wikipage to an external page
- books.google.com/books%3Fid=0bAYl6d7hvkC&pg=PA8
- Link from a Wikipage to another Wikipage
- Algorithm
- Bayes' theorem
- Big O notation
- Category:Articles containing proofs
- Category:Matrix multiplication algorithms
- Category:Matrix theory
- Category:Randomized algorithms
- Computational complexity of matrix multiplication
- Deterministic algorithm
- Error bound
- Matrix (mathematics)
- Matrix multiplication
- One-sided error
- Probabilistic algorithm
- Probability
- Random
- Randomization
- Randomized algorithm
- Randomized algorithms
- Rūsiņš Mārtiņš Freivalds
- Schwartz–Zippel lemma
- Vector (geometric)
- With high probability
- SameAs
- 4qBW1
- Algorithme de Freivalds
- Freivalds' algorithm
- m.0cm7cp
- Q6522941
- Алгоритм Фрейвалдса
- الگوریتم فریوالد
- ขั้นตอนวิธีของเฟรย์วัลส์
- Subject
- Category:Articles containing proofs
- Category:Matrix multiplication algorithms
- Category:Matrix theory
- Category:Randomized algorithms
- WasDerivedFrom
- Freivalds' algorithm?oldid=1121114896&ns=0
- WikiPageLength
- 8183
- Wikipage page ID
- 4767368
- Wikipage revision ID
- 1121114896
- WikiPageUsesTemplate
- Template:Citation
- Template:EquationNote
- Template:EquationRef
- Template:NumBlk
- Template:Numerical linear algebra
- Template:Reflist
- Template:Snd