| http://dbpedia.org/ontology/abstract
|
Поскольку умножение матриц является центра … Поскольку умножение матриц является центральной операцией во многих численных алгоритмах, много усилий было вложено в повышение эффективности алгоритма умножения матриц. Приложения алгоритма умножения матриц в вычислительных задачах найдены во многих областях, включая и , а также во вроде бы не имеющих отношение к матрицам задачах, таких как подсчёт путей через граф. Было разработано много различных алгоритмов для умножения матриц на оборудовании различного типа, включая параллельные и распределённые системы, где вычисления распределены на несколько процессоров (и, может быть, по сети). Прямое использование математического определения умножения матриц даёт алгоритм, который работает за время порядка операций поля для умножения двух матриц над этим полем, или ( в нотации «O» большое). Улучшенные асимптотические границы по времени были известны с момента появления алгоритма Штрассена в 1960-х годах, но оптимальное время остаётся неизвестным (то есть, неизвестна сложность задачи). К концу 2020 года алгоритм умножения матриц с лучшей асимптотической сложностью, работающий за время , был дан Джозефом Алманом и , однако этот алгоритм галактического масштаба, то есть только для данных галактического размера, поскольку содержит огромные константы и не может быть реализован на практике.ты и не может быть реализован на практике.
, Оскільки множення матриць є настільки цент … Оскільки множення матриць є настільки центральною операцією в багатьох чисельних алгоритмах, у те, щоби зробити алгори́тми перемно́жування ма́триць ефективними, було вкладено чимало праці. Застосування множення матриць в обчислювальних задачах зустрічаються в багатьох областях, включно з та розпізнаванням образів, і в, здавалося би, не пов'язаних задачах, таких як підрахунок шляхів графом. Було розроблено багато різних алгоритмів для перемножування матриць на різних типах апаратного забезпечення, включно з паралельними та розподіленими системами, де обчислювальну працю розподілювано декількома процесорами (можливо, через мережу). Безпосереднє застосування математичного означення множення матриць дає алгоритм, що для перемножування двох матриць n × n займає часу порядку n3 (в нотації Ландау — Θ(n3)). Кращі асимптотичні межі часу, необхідного для перемножування матриць, були відомі від часів праці Страссена 1960 року, але досі не відомо, яким є оптимальний час (тобто, якою є складність цієї задачі).ас (тобто, якою є складність цієї задачі).
, Because matrix multiplication is such a ce … 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.stants and cannot be realized practically.
|
| http://dbpedia.org/ontology/thumbnail
|
http://commons.wikimedia.org/wiki/Special:FilePath/Row_and_column_major_order.svg?width=300 +
|
| http://dbpedia.org/ontology/wikiPageExternalLink
|
https://github.com/flame/how-to-optimize-gemm +
|
| http://dbpedia.org/ontology/wikiPageID
|
21450030
|
| http://dbpedia.org/ontology/wikiPageLength
|
33776
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1124066606
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Locality_of_reference +
, http://dbpedia.org/resource/Scalar_multiplication +
, http://dbpedia.org/resource/Virginia_Vassilevska_Williams +
, http://dbpedia.org/resource/Category:Matrix_theory +
, http://dbpedia.org/resource/File:Block_matrix_multiplication.svg +
, http://dbpedia.org/resource/File:MatrixMultComplexity_svg.svg +
, http://dbpedia.org/resource/Category:Numerical_linear_algebra +
, http://dbpedia.org/resource/File:Matrix_multiplication_on_a_cross-wire_two-dimensional_array.png +
, http://dbpedia.org/resource/DeepMind +
, http://dbpedia.org/resource/Category:Matrix_multiplication_algorithms +
, http://dbpedia.org/resource/Recursion +
, http://dbpedia.org/resource/Critical_path_length +
, http://dbpedia.org/resource/GF%282%29 +
, http://dbpedia.org/resource/Computational_complexity_of_mathematical_operations +
, http://dbpedia.org/resource/Block_matrix +
, http://dbpedia.org/resource/Neural_network +
, http://dbpedia.org/resource/Shmuel_Winograd +
, http://dbpedia.org/resource/CPU_cache +
, http://dbpedia.org/resource/Numerical_algorithm +
, http://dbpedia.org/resource/Cache-oblivious_algorithm +
, http://dbpedia.org/resource/Don_Coppersmith +
, http://dbpedia.org/resource/Big_O_notation +
, http://dbpedia.org/resource/Computational_complexity_of_matrix_multiplication +
, http://dbpedia.org/resource/CYK_algorithm +
, http://dbpedia.org/resource/File:Row_and_column_major_order.svg +
, http://dbpedia.org/resource/Row-_and_column-major_order +
, http://dbpedia.org/resource/Galactic_algorithm +
, http://dbpedia.org/resource/Shared-memory_multiprocessor +
, http://dbpedia.org/resource/Sparse_matrix%E2%80%93vector_multiplication +
, http://dbpedia.org/resource/Matrix_multiplication +
, http://dbpedia.org/resource/Distributed_computing +
, http://dbpedia.org/resource/Basic_Linear_Algebra_Subprograms +
, http://dbpedia.org/resource/Cannon%27s_algorithm +
, http://dbpedia.org/resource/Freivalds%27_algorithm +
, http://dbpedia.org/resource/Theoretical_computer_science +
, http://dbpedia.org/resource/Field_%28mathematics%29 +
, http://dbpedia.org/resource/Pseudocode +
, http://dbpedia.org/resource/Time_complexity +
, http://dbpedia.org/resource/Monte_Carlo_algorithm +
, http://dbpedia.org/resource/Master_theorem_%28analysis_of_algorithms%29 +
, http://dbpedia.org/resource/Fork%E2%80%93join_model +
, http://dbpedia.org/resource/Divide-and-conquer_algorithm +
, http://dbpedia.org/resource/Loop_tiling +
, http://dbpedia.org/resource/Pattern_recognition +
, http://dbpedia.org/resource/Mesh_networking +
, http://dbpedia.org/resource/Scientific_computing +
, http://dbpedia.org/resource/Parallel_computing +
, http://dbpedia.org/resource/Matrix_chain_multiplication +
, http://dbpedia.org/resource/Strassen_algorithm +
, http://dbpedia.org/resource/Asymptotic_notation +
, http://dbpedia.org/resource/Speedup +
, http://dbpedia.org/resource/Method_of_Four_Russians +
, http://dbpedia.org/resource/Loop_unrolling +
, http://dbpedia.org/resource/Parallel_algorithm +
, http://dbpedia.org/resource/Multiprogramming +
, http://dbpedia.org/resource/Graph_%28graph_theory%29 +
, http://dbpedia.org/resource/Analysis_of_algorithms +
, http://dbpedia.org/resource/Volker_Strassen +
, http://dbpedia.org/resource/Communication-avoiding_algorithm +
, http://dbpedia.org/resource/Category:Articles_with_example_pseudocode +
, http://dbpedia.org/resource/Finite_field +
, http://dbpedia.org/resource/Numerical_stability +
, http://dbpedia.org/resource/MapReduce +
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Math +
, http://dbpedia.org/resource/Template:Radic +
, http://dbpedia.org/resource/Template:As_of +
, http://dbpedia.org/resource/Template:Reflist +
, http://dbpedia.org/resource/Template:Numerical_linear_algebra +
, http://dbpedia.org/resource/Template:Frame-footer +
, http://dbpedia.org/resource/Template:Cite_journal +
, http://dbpedia.org/resource/Template:Sqrt +
, http://dbpedia.org/resource/Template:Framebox +
, http://dbpedia.org/resource/Template:R +
, http://dbpedia.org/resource/Template:Rp +
, http://dbpedia.org/resource/Template:Further +
, http://dbpedia.org/resource/Template:Mvar +
, http://dbpedia.org/resource/Template:Sfrac +
, http://dbpedia.org/resource/Template:= +
, http://dbpedia.org/resource/Template:Short_description +
, http://dbpedia.org/resource/Template:Refend +
, http://dbpedia.org/resource/Template:Refbegin +
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Articles_with_example_pseudocode +
, http://dbpedia.org/resource/Category:Numerical_linear_algebra +
, http://dbpedia.org/resource/Category:Matrix_multiplication_algorithms +
, http://dbpedia.org/resource/Category:Matrix_theory +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Matrix_multiplication_algorithm?oldid=1124066606&ns=0 +
|
| http://xmlns.com/foaf/0.1/depiction
|
http://commons.wikimedia.org/wiki/Special:FilePath/Block_matrix_multiplication.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Matrix_multiplication_on_a_cross-wire_two-dimensional_array.png +
, http://commons.wikimedia.org/wiki/Special:FilePath/Row_and_column_major_order.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/MatrixMultComplexity_svg.svg +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Matrix_multiplication_algorithm +
|
| owl:sameAs |
https://global.dbpedia.org/id/fs4i +
, http://sr.dbpedia.org/resource/Algoritam_mno%C5%BEenja_matrica +
, http://rdf.freebase.com/ns/m.010prbtk +
, http://uk.dbpedia.org/resource/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%BF%D0%B5%D1%80%D0%B5%D0%BC%D0%BD%D0%BE%D0%B6%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86%D1%8C +
, http://fa.dbpedia.org/resource/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85%E2%80%8C%D9%87%D8%A7%DB%8C_%D8%B6%D8%B1%D8%A8_%D9%85%D8%A7%D8%AA%D8%B1%DB%8C%D8%B3 +
, http://ru.dbpedia.org/resource/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%83%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86 +
, http://yago-knowledge.org/resource/Matrix_multiplication_algorithm +
, http://rdf.freebase.com/ns/m.012ngj92 +
, http://www.wikidata.org/entity/Q17082383 +
, http://dbpedia.org/resource/Matrix_multiplication_algorithm +
|
| rdf:type |
http://dbpedia.org/class/yago/Whole100003553 +
, http://dbpedia.org/class/yago/Object100002684 +
, http://dbpedia.org/class/yago/YagoLegalActorGeo +
, http://dbpedia.org/class/yago/YagoLegalActor +
, http://dbpedia.org/class/yago/Person100007846 +
, http://dbpedia.org/class/yago/Model110324560 +
, http://dbpedia.org/class/yago/WikicatModelsOfComputation +
, http://dbpedia.org/class/yago/CausalAgent100007347 +
, http://dbpedia.org/class/yago/Organism100004475 +
, http://dbpedia.org/class/yago/Assistant109815790 +
, http://dbpedia.org/class/yago/PhysicalEntity100001930 +
, http://dbpedia.org/class/yago/LivingThing100004258 +
, http://dbpedia.org/class/yago/Worker109632518 +
|
| rdfs:comment |
Because matrix multiplication is such a ce … 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).tiple processors (perhaps over a network).
, Оскільки множення матриць є настільки цент … Оскільки множення матриць є настільки центральною операцією в багатьох чисельних алгоритмах, у те, щоби зробити алгори́тми перемно́жування ма́триць ефективними, було вкладено чимало праці. Застосування множення матриць в обчислювальних задачах зустрічаються в багатьох областях, включно з та розпізнаванням образів, і в, здавалося би, не пов'язаних задачах, таких як підрахунок шляхів графом. Було розроблено багато різних алгоритмів для перемножування матриць на різних типах апаратного забезпечення, включно з паралельними та розподіленими системами, де обчислювальну працю розподілювано декількома процесорами (можливо, через мережу).ькома процесорами (можливо, через мережу).
, Поскольку умножение матриц является центра … Поскольку умножение матриц является центральной операцией во многих численных алгоритмах, много усилий было вложено в повышение эффективности алгоритма умножения матриц. Приложения алгоритма умножения матриц в вычислительных задачах найдены во многих областях, включая и , а также во вроде бы не имеющих отношение к матрицам задачах, таких как подсчёт путей через граф. Было разработано много различных алгоритмов для умножения матриц на оборудовании различного типа, включая параллельные и распределённые системы, где вычисления распределены на несколько процессоров (и, может быть, по сети).лько процессоров (и, может быть, по сети).
|
| rdfs:label |
Алгоритм перемножування матриць
, Matrix multiplication algorithm
, Алгоритм умножения матриц
|
