Freivalds' algorithm (original) (raw)
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 | https://books.google.com/books%3Fid=0bAYl6d7hvkC&pg=PA8 |
| dbo:wikiPageID | 4767368 (xsd:integer) |
| dbo:wikiPageLength | 8183 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1121114896 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Bayes'_theorem dbr:Algorithm dbc:Randomized_algorithms dbr:Vector_(geometric) dbr:Deterministic_algorithm dbc:Articles_containing_proofs dbr:Computational_complexity_of_matrix_multiplication dbr:Matrix_(mathematics) dbr:Matrix_multiplication dbc:Matrix_theory dbr:Rūsiņš_Mārtiņš_Freivalds dbr:Probability dbr:Random dbr:Big_O_notation dbr:Schwartz–Zippel_lemma dbr:One-sided_error dbc:Matrix_multiplication_algorithms dbr:Randomized_algorithm dbr:Randomized_algorithms dbr:With_high_probability dbr:Randomization dbr:Probabilistic_algorithm dbr:Error_bound |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:NumBlk dbt:Reflist dbt:Snd dbt:EquationRef dbt:EquationNote dbt:Numerical_linear_algebra |
| dct:subject | dbc:Randomized_algorithms dbc:Articles_containing_proofs dbc:Matrix_theory dbc:Matrix_multiplication_algorithms |
| rdf:type | yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatRandomizedAlgorithms |
| 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 | freebase:Freivalds' algorithm yago-res:Freivalds' algorithm wikidata:Freivalds' algorithm dbpedia-fa:Freivalds' algorithm dbpedia-fr:Freivalds' algorithm dbpedia-ru:Freivalds' algorithm dbpedia-th:Freivalds' algorithm https://global.dbpedia.org/id/4qBW1 |
| prov:wasDerivedFrom | wikipedia-en:Freivalds'_algorithm?oldid=1121114896&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Freivalds'_algorithm |
| is dbo:wikiPageDisambiguates of | dbr:Freivalds |
| is dbo:wikiPageRedirects of | dbr:Freivald's_algorithm dbr:Freivald_algorithm |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:List_of_numerical_analysis_topics dbr:Computational_complexity_of_matrix_multiplication dbr:Matrix_multiplication_algorithm dbr:Freivald's_algorithm dbr:Freivalds dbr:Rūsiņš_Mārtiņš_Freivalds dbr:Intransitive_dice dbr:With_high_probability dbr:Freivald_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Freivalds'_algorithm |