Matrix multiplication algorithm (original) (raw)
Because matrix multiplication is such a central operation in many numerical algorithms, much work has been invested in making matrix multiplication algorithms efficient. Applications of matrix multiplication in computational problems are found in many fields including scientific computing and pattern recognition and in seemingly unrelated problems such as counting the paths through a graph. Many different algorithms have been designed for multiplying matrices on different types of hardware, including parallel and distributed systems, where the computational work is spread over multiple processors (perhaps over a network).
| Property | Value |
|---|---|
| dbo:abstract | Because matrix multiplication is such a central operation in many numerical algorithms, much work has been invested in making matrix multiplication algorithms efficient. Applications of matrix multiplication in computational problems are found in many fields including scientific computing and pattern recognition and in seemingly unrelated problems such as counting the paths through a graph. Many different algorithms have been designed for multiplying matrices on different types of hardware, including parallel and distributed systems, where the computational work is spread over multiple processors (perhaps over a network). Directly applying the mathematical definition of matrix multiplication gives an algorithm that takes time on the order of n3 field operations to multiply two n × n matrices over that field (Θ(n3) in big O notation). Better asymptotic bounds on the time required to multiply matrices have been known since the Strassen's algorithm in the 1960s, but the optimal time (that is, the computational complexity of matrix multiplication) remains unknown. As of October 2022, the best announced bound on the asymptotic complexity of a matrix multiplication algorithm is O(n2.37188) time, given by Duan, Wu and Zhou announced in a preprint. This improves on the bound of O(n2.3728596) time, given by Josh Alman and Virginia Vassilevska Williams. However, this algorithm is a galactic algorithm because of the large constants and cannot be realized practically. (en) Поскольку умножение матриц является центральной операцией во многих численных алгоритмах, много усилий было вложено в повышение эффективности алгоритма умножения матриц. Приложения алгоритма умножения матриц в вычислительных задачах найдены во многих областях, включая и , а также во вроде бы не имеющих отношение к матрицам задачах, таких как подсчёт путей через граф. Было разработано много различных алгоритмов для умножения матриц на оборудовании различного типа, включая параллельные и распределённые системы, где вычисления распределены на несколько процессоров (и, может быть, по сети). Прямое использование математического определения умножения матриц даёт алгоритм, который работает за время порядка операций поля для умножения двух матриц над этим полем, или ( в нотации «O» большое). Улучшенные асимптотические границы по времени были известны с момента появления алгоритма Штрассена в 1960-х годах, но оптимальное время остаётся неизвестным (то есть, неизвестна сложность задачи). К концу 2020 года алгоритм умножения матриц с лучшей асимптотической сложностью, работающий за время , был дан Джозефом Алманом и , однако этот алгоритм галактического масштаба, то есть только для данных галактического размера, поскольку содержит огромные константы и не может быть реализован на практике. (ru) Оскільки множення матриць є настільки центральною операцією в багатьох чисельних алгоритмах, у те, щоби зробити алгори́тми перемно́жування ма́триць ефективними, було вкладено чимало праці. Застосування множення матриць в обчислювальних задачах зустрічаються в багатьох областях, включно з та розпізнаванням образів, і в, здавалося би, не пов'язаних задачах, таких як підрахунок шляхів графом. Було розроблено багато різних алгоритмів для перемножування матриць на різних типах апаратного забезпечення, включно з паралельними та розподіленими системами, де обчислювальну працю розподілювано декількома процесорами (можливо, через мережу). Безпосереднє застосування математичного означення множення матриць дає алгоритм, що для перемножування двох матриць n × n займає часу порядку n3 (в нотації Ландау — Θ(n3)). Кращі асимптотичні межі часу, необхідного для перемножування матриць, були відомі від часів праці Страссена 1960 року, але досі не відомо, яким є оптимальний час (тобто, якою є складність цієї задачі). (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Row_and_column_major_order.svg?width=300 |
| dbo:wikiPageExternalLink | https://github.com/flame/how-to-optimize-gemm |
| dbo:wikiPageID | 21450030 (xsd:integer) |
| dbo:wikiPageLength | 33776 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124066606 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Scalar_multiplication dbr:Monte_Carlo_algorithm dbr:Neural_network dbr:Mesh_networking dbr:Method_of_Four_Russians dbr:Basic_Linear_Algebra_Subprograms dbr:DeepMind dbr:Virginia_Vassilevska_Williams dbr:Volker_Strassen dbr:Computational_complexity_of_matrix_multiplication dbr:Analysis_of_algorithms dbr:Master_theorem_(analysis_of_algorithms) dbr:Matrix_multiplication dbr:Speedup dbr:Freivalds'_algorithm dbr:GF(2) dbr:Cache-oblivious_algorithm dbr:Shmuel_Winograd dbr:Communication-avoiding_algorithm dbr:Computational_complexity_of_mathematical_operations dbr:Parallel_algorithm dbr:Parallel_computing dbr:Pattern_recognition dbr:Numerical_stability dbr:Strassen_algorithm dbr:Theoretical_computer_science dbr:MapReduce dbr:Matrix_chain_multiplication dbc:Articles_with_example_pseudocode dbr:CPU_cache dbc:Matrix_theory dbr:Time_complexity dbr:Distributed_computing dbr:Divide-and-conquer_algorithm dbr:Galactic_algorithm dbr:Locality_of_reference dbr:Field_(mathematics) dbr:Finite_field dbr:Fork–join_model dbr:Recursion dbc:Numerical_linear_algebra dbr:Big_O_notation dbr:Block_matrix dbr:Loop_tiling dbr:Don_Coppersmith dbr:CYK_algorithm dbr:Scientific_computing dbr:Graph_(graph_theory) dbr:Cannon's_algorithm dbc:Matrix_multiplication_algorithms dbr:Loop_unrolling dbr:Row-_and_column-major_order dbr:Multiprogramming dbr:Pseudocode dbr:Sparse_matrix–vector_multiplication dbr:Asymptotic_notation dbr:Critical_path_length dbr:Numerical_algorithm dbr:Shared-memory_multiprocessor dbr:File:Row_and_column_major_order.svg dbr:File:MatrixMultComplexity_svg.svg dbr:File:Block_matrix_multiplication.svg dbr:File:Matrix_multiplication_on_a_cross-wire_two-dimensional_array.png |
| dbp:wikiPageUsesTemplate | dbt:= dbt:As_of dbt:Cite_journal dbt:Further dbt:Math dbt:Mvar dbt:R dbt:Radic dbt:Refbegin dbt:Refend dbt:Reflist dbt:Rp dbt:Sfrac dbt:Short_description dbt:Sqrt dbt:Numerical_linear_algebra dbt:Frame-footer dbt:Framebox |
| dct:subject | dbc:Articles_with_example_pseudocode dbc:Matrix_theory dbc:Numerical_linear_algebra dbc:Matrix_multiplication_algorithms |
| rdf:type | yago:WikicatModelsOfComputation yago:Assistant109815790 yago:CausalAgent100007347 yago:LivingThing100004258 yago:Model110324560 yago:Object100002684 yago:Organism100004475 yago:Person100007846 yago:PhysicalEntity100001930 yago:Worker109632518 yago:YagoLegalActor yago:YagoLegalActorGeo yago:Whole100003553 |
| rdfs:comment | Because matrix multiplication is such a central operation in many numerical algorithms, much work has been invested in making matrix multiplication algorithms efficient. Applications of matrix multiplication in computational problems are found in many fields including scientific computing and pattern recognition and in seemingly unrelated problems such as counting the paths through a graph. Many different algorithms have been designed for multiplying matrices on different types of hardware, including parallel and distributed systems, where the computational work is spread over multiple processors (perhaps over a network). (en) Поскольку умножение матриц является центральной операцией во многих численных алгоритмах, много усилий было вложено в повышение эффективности алгоритма умножения матриц. Приложения алгоритма умножения матриц в вычислительных задачах найдены во многих областях, включая и , а также во вроде бы не имеющих отношение к матрицам задачах, таких как подсчёт путей через граф. Было разработано много различных алгоритмов для умножения матриц на оборудовании различного типа, включая параллельные и распределённые системы, где вычисления распределены на несколько процессоров (и, может быть, по сети). (ru) Оскільки множення матриць є настільки центральною операцією в багатьох чисельних алгоритмах, у те, щоби зробити алгори́тми перемно́жування ма́триць ефективними, було вкладено чимало праці. Застосування множення матриць в обчислювальних задачах зустрічаються в багатьох областях, включно з та розпізнаванням образів, і в, здавалося би, не пов'язаних задачах, таких як підрахунок шляхів графом. Було розроблено багато різних алгоритмів для перемножування матриць на різних типах апаратного забезпечення, включно з паралельними та розподіленими системами, де обчислювальну працю розподілювано декількома процесорами (можливо, через мережу). (uk) |
| rdfs:label | Matrix multiplication algorithm (en) Алгоритм умножения матриц (ru) Алгоритм перемножування матриць (uk) |
| owl:sameAs | freebase:Matrix multiplication algorithm freebase:Matrix multiplication algorithm yago-res:Matrix multiplication algorithm wikidata:Matrix multiplication algorithm dbpedia-fa:Matrix multiplication algorithm dbpedia-ru:Matrix multiplication algorithm dbpedia-sr:Matrix multiplication algorithm dbpedia-uk:Matrix multiplication algorithm https://global.dbpedia.org/id/fs4i |
| prov:wasDerivedFrom | wikipedia-en:Matrix_multiplication_algorithm?oldid=1124066606&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Block_matrix_multiplication.svg wiki-commons:Special:FilePath/Matrix_multiplication_on_a_cross-wire_two-dimensional_array.png wiki-commons:Special:FilePath/Row_and_column_major_order.svg wiki-commons:Special:FilePath/MatrixMultComplexity_svg.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Matrix_multiplication_algorithm |
| is dbo:wikiPageRedirects of | dbr:Coppersmith-Winograd_algorithm dbr:Cache-oblivious_matrix_multiplication dbr:Parallel_algorithms_for_matrix_multiplication dbr:Fast_matrix_multiplication_algorithms dbr:Divide_and_conquer_algorithm_for_matrix_multiplication dbr:Algorithm_for_matrix_multiplication dbr:Algorithms_for_matrix_multiplication |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Basic_Linear_Algebra_Subprograms dbr:Victor_Pan dbr:Virginia_Vassilevska_Williams dbr:Computational_complexity_of_matrix_multiplication dbr:Matrix_(mathematics) dbr:GotoBLAS dbr:Computational_complexity_of_mathematical_operations dbr:Phase-change_memory dbr:Strassen_algorithm dbr:Locality_of_reference dbr:Dynamic_programming dbr:Leibniz_formula_for_determinants dbr:Invertible_matrix dbr:CYK_algorithm dbr:Coppersmith-Winograd_algorithm dbr:Cache-oblivious_matrix_multiplication dbr:Tensor_rank_decomposition dbr:Parallel_algorithms_for_matrix_multiplication dbr:Fast_matrix_multiplication_algorithms dbr:Divide_and_conquer_algorithm_for_matrix_multiplication dbr:Algorithm_for_matrix_multiplication dbr:Algorithms_for_matrix_multiplication |
| is foaf:primaryTopic of | wikipedia-en:Matrix_multiplication_algorithm |
