An Entity of Type: Rule105846932, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

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 .

Property Value
dbo: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)
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 4767368 (xsd:integer)
dbo:wikiPageLength
  • 8183 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1121114896 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
rdf:type
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)
rdfs:label
  • Freivalds' algorithm (en)
  • Algorithme de Freivalds (fr)
  • Алгоритм Фрейвалдса (ru)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License