This HTML5 document contains 106 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n7http://dbpedia.org/resource/File:
n14https://global.dbpedia.org/id/
dbthttp://dbpedia.org/resource/Template:
n17https://fmm.univ-lille.fr/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n13http://commons.wikimedia.org/wiki/Special:FilePath/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Quantum_logic_gate
dbo:wikiPageWikiLink
dbr:Computational_complexity_of_matrix_multiplication
Subject Item
dbr:Virginia_Vassilevska_Williams
dbo:wikiPageWikiLink
dbr:Computational_complexity_of_matrix_multiplication
dbo:knownFor
dbr:Computational_complexity_of_matrix_multiplication
Subject Item
dbr:Computational_complexity_of_matrix_multiplication
rdfs:label
Computational complexity of matrix multiplication
rdfs:comment
In theoretical computer science, the computational complexity of matrix multiplication dictates how quickly the operation of matrix multiplication can be performed. Matrix multiplication algorithms are a central subroutine in theoretical and numerical algorithms for numerical linear algebra and optimization, so finding the right amount of time it should take is of major practical relevance.
foaf:depiction
n13:MatrixMultComplexity_svg.svg
dcterms:subject
dbc:Unsolved_problems_in_computer_science dbc:Computer_arithmetic_algorithms dbc:Computational_complexity_theory dbc:Matrix_theory
dbo:wikiPageID
24107400
dbo:wikiPageRevisionID
1121125201
dbo:wikiPageWikiLink
dbr:Group_theory dbr:LU_decomposition dbr:Shmuel_Winograd dbr:Basic_Linear_Algebra_Subprograms dbc:Unsolved_problems_in_computer_science dbr:Determinant dbc:Matrix_theory n7:MatrixMultComplexity_svg.svg dbr:Matrix_chain_multiplication dbr:Block_matrix dbc:Computer_arithmetic_algorithms dbr:Chris_Umans dbr:Duality_(optimization) dbr:Matrix_multiplication dbr:Matrix_multiplication_algorithm dbr:Robert_Kleinberg dbr:Divide-and-conquer_algorithm dbr:Matrix_inversion dbr:Monte_Carlo_algorithm dbr:Sparse_matrix–vector_multiplication dbr:Numerical_linear_algebra dbr:Freivalds'_algorithm dbr:Algorithm dbr:Strassen_algorithm dbr:Volker_Strassen dbr:Virginia_Vassilevska_Williams dbr:Smith_normal_form dbr:Numerical_stability dbr:Galactic_algorithm dbr:Numerical_algorithm dbr:Model_of_computation dbc:Computational_complexity_theory dbr:Floating_point dbr:Triple_product_property dbr:Worst-case_complexity dbr:Big_O_notation dbr:Time_complexity dbr:Field_(mathematics) dbr:Sunflower_conjecture dbr:Analysis_of_algorithms dbr:Abelian_group dbr:Don_Coppersmith dbr:Ran_Raz dbr:Hermite_normal_form dbr:Finite_field dbr:Balázs_Szegedy dbr:Arithmetic_circuit_complexity dbr:Wreath_product dbr:Gaussian_elimination dbr:Computational_complexity dbr:Computational_complexity_of_mathematical_operations dbr:CYK_algorithm dbr:Henry_Cohn dbr:Optimization dbr:Theoretical_computer_science
dbo:wikiPageExternalLink
n17:
owl:sameAs
wikidata:Q106996431 n14:FuZW8
dbp:wikiPageUsesTemplate
dbt:Mvar dbt:Math dbt:As_of dbt:Citation_needed dbt:Short_description dbt:For dbt:Cite_journal dbt:Unsolved dbt:Reflist dbt:Tmath dbt:Main dbt:= dbt:Further
dbo:thumbnail
n13:MatrixMultComplexity_svg.svg?width=300
dbo:abstract
In theoretical computer science, the computational complexity of matrix multiplication dictates how quickly the operation of matrix multiplication can be performed. Matrix multiplication algorithms are a central subroutine in theoretical and numerical algorithms for numerical linear algebra and optimization, so finding the right amount of time it should take is of major practical relevance. Directly applying the mathematical definition of matrix multiplication gives an algorithm that requires n3 field operations to multiply two n × n matrices over that field (Θ(n3) in big O notation). Surprisingly, algorithms exist that provide better running times than this straightforward "schoolbook algorithm". The first to be discovered was Strassen's algorithm, devised by Volker Strassen in 1969 and often referred to as "fast matrix multiplication". The optimal number of field operations needed to multiply two square n × n matrices up to constant factors is still unknown. This is a major open question in theoretical computer science. 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 and similar improvements to Strassen are not used in practice, because they are galactic algorithms: the constant coefficient hidden by the Big O notation is so large that they are only worthwhile for matrices that are too large to handle on present-day computers.
prov:wasDerivedFrom
wikipedia-en:Computational_complexity_of_matrix_multiplication?oldid=1121125201&ns=0
dbo:wikiPageLength
33132
foaf:isPrimaryTopicOf
wikipedia-en:Computational_complexity_of_matrix_multiplication
Subject Item
dbr:Matrix_multiplication_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_of_matrix_multiplication
Subject Item
dbr:Clique_problem
dbo:wikiPageWikiLink
dbr:Computational_complexity_of_matrix_multiplication
Subject Item
dbr:Freivalds'_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_of_matrix_multiplication
Subject Item
dbr:Arithmetic_circuit_complexity
dbo:wikiPageWikiLink
dbr:Computational_complexity_of_matrix_multiplication
Subject Item
dbr:Computational_complexity_of_mathematical_operations
dbo:wikiPageWikiLink
dbr:Computational_complexity_of_matrix_multiplication
Subject Item
dbr:Strassen_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_of_matrix_multiplication
Subject Item
dbr:Transitive_reduction
dbo:wikiPageWikiLink
dbr:Computational_complexity_of_matrix_multiplication
Subject Item
dbr:Invertible_matrix
dbo:wikiPageWikiLink
dbr:Computational_complexity_of_matrix_multiplication
Subject Item
dbr:Directed_acyclic_graph
dbo:wikiPageWikiLink
dbr:Computational_complexity_of_matrix_multiplication
Subject Item
dbr:Coppersmith–Winograd_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_of_matrix_multiplication
dbo:wikiPageRedirects
dbr:Computational_complexity_of_matrix_multiplication
Subject Item
dbr:List_of_unsolved_problems_in_computer_science
dbo:wikiPageWikiLink
dbr:Computational_complexity_of_matrix_multiplication
Subject Item
dbr:Seidel's_algorithm
dbo:wikiPageWikiLink
dbr:Computational_complexity_of_matrix_multiplication
Subject Item
dbr:Fast_matrix_multiplication
dbo:wikiPageWikiLink
dbr:Computational_complexity_of_matrix_multiplication
dbo:wikiPageRedirects
dbr:Computational_complexity_of_matrix_multiplication
Subject Item
dbr:Complexity_of_matrix_multiplication
dbo:wikiPageWikiLink
dbr:Computational_complexity_of_matrix_multiplication
dbo:wikiPageRedirects
dbr:Computational_complexity_of_matrix_multiplication
Subject Item
wikipedia-en:Computational_complexity_of_matrix_multiplication
foaf:primaryTopic
dbr:Computational_complexity_of_matrix_multiplication