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 .
Attributes | Values |
---|
rdf:type
| |
rdfs:label
| - Freivalds' algorithm (en)
- Algorithme de Freivalds (fr)
- Алгоритм Фрейвалдса (ru)
|
rdfs:comment
| - 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 . (en)
- L'algorithme de Freivalds (du nom de Rūsiņš Mārtiņš Freivalds) est un test probabiliste pour vérifier le résultat d'un produit matriciel. Étant donné trois matrices , , et , le problème est de vérifier si . Pour le résoudre, l'algorithme naïf calcule le produit explicitement et compare le résultat terme à terme avec . Cependant, le meilleur algorithme connu de produit matriciel s'exécute en temps . L'algorithme de Freivalds utilise la randomisation afin de réduire cette borne à avec une forte probabilité. Il peut vérifier un produit matriciel en temps avec une probabilité d'échec inférieure à . (fr)
- Алгоритм Фрейвалдса (назван по имени Русиньша Мартыньша Фрейвалдса) — это вероятностный рандомизированный алгоритм, используемый для верификации матричного произведения. По трём матрицам , и размера необходимо проверить, что . Наивный алгоритм решения данной задачи заключается в том, чтобы посчитать в явном виде и поэлементно сравнить получившуюся матрицу с . Однако наилучший известный алгоритм умножения матриц работает за время . Алгоритм Фрейвалдса использует чтобы снизить данную оценку до с высокой вероятностью. За время алгоритм может проверить матричное произведение с вероятностью ошибки, не превосходящей . (ru)
|
dcterms:subject
| |
Wikipage page ID
| |
Wikipage revision ID
| |
Link from a Wikipage to another Wikipage
| |
Link from a Wikipage to an external page
| |
sameAs
| |
dbp:wikiPageUsesTemplate
| |
has abstract
| - 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 . (en)
- L'algorithme de Freivalds (du nom de Rūsiņš Mārtiņš Freivalds) est un test probabiliste pour vérifier le résultat d'un produit matriciel. Étant donné trois matrices , , et , le problème est de vérifier si . Pour le résoudre, l'algorithme naïf calcule le produit explicitement et compare le résultat terme à terme avec . Cependant, le meilleur algorithme connu de produit matriciel s'exécute en temps . L'algorithme de Freivalds utilise la randomisation afin de réduire cette borne à avec une forte probabilité. Il peut vérifier un produit matriciel en temps avec une probabilité d'échec inférieure à . (fr)
- Алгоритм Фрейвалдса (назван по имени Русиньша Мартыньша Фрейвалдса) — это вероятностный рандомизированный алгоритм, используемый для верификации матричного произведения. По трём матрицам , и размера необходимо проверить, что . Наивный алгоритм решения данной задачи заключается в том, чтобы посчитать в явном виде и поэлементно сравнить получившуюся матрицу с . Однако наилучший известный алгоритм умножения матриц работает за время . Алгоритм Фрейвалдса использует чтобы снизить данную оценку до с высокой вероятностью. За время алгоритм может проверить матричное произведение с вероятностью ошибки, не превосходящей . (ru)
|
prov:wasDerivedFrom
| |
page length (characters) of wiki page
| |
foaf:isPrimaryTopicOf
| |
is Link from a Wikipage to another Wikipage
of | |
is Wikipage redirect
of | |
is Wikipage disambiguates
of | |
is foaf:primaryTopic
of | |