{"entities":{"Q799337":{"pageid":801185,"ns":120,"title":"Item:Q799337","lastrevid":64501218,"modified":"2026-04-11T20:18:17Z","type":"item","id":"Q799337","labels":{"en":{"language":"en","value":"How to multiply matrices faster"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3874491"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799337$E4FE7948-5019-46EB-A136-2364C056B96E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eefdef0191e041ab8743bbcffc983abf32e8f221","datavalue":{"value":{"text":"How to multiply matrices faster","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q799337$6A09F235-CF0C-4A6B-B233-2573A477E754","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ea3827cc96aa6d9c4a161fef5e95df0496e2e2b8","datavalue":{"value":"0548.65022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799337$A89CAC5C-A89A-4DC4-A168-56183A78E660","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"85c07c7737819bff773f78e2590a3bb761fe677b","datavalue":{"value":{"entity-type":"item","numeric-id":162374,"id":"Q162374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799337$CB5409C6-4DAC-425F-9167-844A225245EC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q799337$0CF3E0BE-DC3F-4081-8A19-5C793A2F3D95","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"615170a5baa9b0cfab282d8c53c76844fcdc2cd0","datavalue":{"value":"The monograph, consisting of fourty minimally interconnected sections, is divided into three main parts. Part 1 describes historically all major asymptotically fast algorithms used for \\(n\\times n\\) matrix multiplication (MM): Strassen's algorithm, bilinear algorithms, trilinear aggregating, APA-algorithms (any precision approximation algorithms denoted as \\(\\lambda\\) -algorithms), disjoint MM. Asymptotically fast algorithms for MM with exponent 2.496 are derived. Part 2 presents the reduction of the solution of some combinatorial and algebraic problems to MM and their consequent acceleration employing bit-time and bit-space concepts. The Boolean MM, the all pair shortest distance problem on a digraph, the solution of a system of linear equations, matrix inversion, the evaluation of the determinant of a matrix are considered. Bit-time and bit-space estimates, a close relation of bit-time and bit-space to the values of condition numbers together with their estimates are derived. A bit-complexity classification is given. Part 3 deals with bilinear algorithms and \\(\\lambda\\) -algorithms of the currently least ranks and \\(\\lambda\\) -ranks, commutative quadratic algorithms, general arithmetical algorithms and \\(\\lambda\\) -algorithms for \\(n\\times n\\) MM for small and moderate n. Some well-known linear lower bounds on the complexity of algorithms of different classes are derived. New extension of the class of arithmetical \\(\\lambda\\) -algorithms for the evaluation of a set of rational expressions is considered. The book is an essentially self- contained and clearly written high level research exposition covering mostly the progress in MM since 1978 which has not been covered in such extent in other books up-to-date.","type":"string"},"datatype":"string"},"type":"statement","id":"Q799337$006CB916-BAAA-484A-B812-BC570DCC6B9F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"72309745094959b676ca20810c7af21a33fe24b5","datavalue":{"value":"65F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799337$80E94662-47DB-4BC8-8CA1-977C826F21D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"da9089632ac15e697a99fcfd70cf6851ce0f2f20","datavalue":{"value":"65-02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799337$7B25F509-5EDF-40B0-94B2-A25B06CE754C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9885aef811aa349f50c28b046ac04fbe99524c67","datavalue":{"value":"65F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799337$CB94FFA0-18AF-47F8-A6B0-6B0020601983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83fd851d78dc4c8819268c60531c7e9e72c3d7f6","datavalue":{"value":"65F40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799337$083ACBE3-CA83-41E5-8615-ADCBA97EBC89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"01c01fe808ed718e2875de738d94f61942d3944d","datavalue":{"value":"65F35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799337$63857C3B-4D68-4A67-8EFA-BE7F06189B99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"de7887ac8896f76fb0219bbdc2f1520f3f1a5b3b","datavalue":{"value":"15A09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799337$185EFFA2-4A7A-479E-A512-33193F5E622C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799337$5D4985E7-1CED-45D4-AD02-F9D26613F5C6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"673f1a6a933a29d64336ac24f2d46cb70b88e46a","datavalue":{"value":"3874491","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799337$B0F2E53A-B553-4D1F-8846-88342B63DC52","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ded00ff24911bfc89d689a407cbdf3066d9cce96","datavalue":{"value":"monograph","type":"string"},"datatype":"string"},"type":"statement","id":"Q799337$231E873D-3913-41E1-BCD7-1382797E62EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"61045fcfd3307e7cbf9eed0f768bf9c62c382635","datavalue":{"value":"asymptotically fast algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q799337$720F75F3-A9DD-4A70-8518-C93A3C8B5015","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de71a87004b2cb6be9dfb83edd24b279968af4f7","datavalue":{"value":"matrix multiplication","type":"string"},"datatype":"string"},"type":"statement","id":"Q799337$F2CA2FDF-C9C7-48FC-B18B-4B1B7C69CE6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c1a2eba9bac9971207298009871199e651ca130","datavalue":{"value":"Strassen's algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q799337$D83BB7D5-B982-4444-9CAB-BC93C3502805","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab23cbc048867be6dc43805d4a45580afd8a0340","datavalue":{"value":"bilinear algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q799337$A98EC572-46CA-4E57-8289-BC6DEFF34767","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"03460f3ba97226d4a13118ef9d97e3e5c0679850","datavalue":{"value":"trilinear aggregating","type":"string"},"datatype":"string"},"type":"statement","id":"Q799337$A59E6B48-8323-4C35-AAF2-9AAD671BB81B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8565eaba2f4d82e4bd82f0423dc7513c3ad2e6df","datavalue":{"value":"APA- algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q799337$EAFD25A4-A259-4D52-81B4-40EDB9D339C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"105c10d34b449ad5907a0e5d51e90739317538be","datavalue":{"value":"precision approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q799337$528D03BA-CA2F-49DA-9B7D-783EBDB0F68F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e2815ed8f2d32ec3db37321937af4c840532d82","datavalue":{"value":"bit-time and bit-space concepts","type":"string"},"datatype":"string"},"type":"statement","id":"Q799337$B8A9CEA2-EEEF-4611-AF39-8D3ED0F7C163","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"576896884c8c6a9fff89bf1c31c20f7aca9212aa","datavalue":{"value":"all pair shortest distance problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q799337$E6590D19-1E78-4EBB-AFA1-F39676268587","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59b0c1a02a224b9fb659082e53fed4a02f3d9545","datavalue":{"value":"matrix inversion","type":"string"},"datatype":"string"},"type":"statement","id":"Q799337$0E23E60E-4503-429D-AA23-3DCCE2A0BB01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ceb8df8375343895659f15a6a079d7a03cf4566e","datavalue":{"value":"condition numbers","type":"string"},"datatype":"string"},"type":"statement","id":"Q799337$152E8368-107B-4D08-880F-88B7C5404956","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2278f035590e400c7ab8ae4076c4d373dd8d0ebe","datavalue":{"value":"complexity of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q799337$7259DD86-907A-49DD-ACDA-7B570502DE1E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"748dce42a571924bd5dc5be9f8a70b8adc09d292","datavalue":{"value":{"entity-type":"item","numeric-id":163211,"id":"Q163211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799337$9288E869-67FD-4931-A8CE-BBF10EE09656","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f62228a5ef103a56a3b2ab18d746e6cdc0920111","datavalue":{"value":{"entity-type":"item","numeric-id":209077,"id":"Q209077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799337$BD38B0CC-F47C-4E77-9435-70B65EBB4709","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799337$A4C3EC00-5D29-48FF-9FCA-59DC4E95F563","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e52014ed294307bf5de8a13ae588a74b94626665","datavalue":{"value":{"entity-type":"item","numeric-id":1183208,"id":"Q1183208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82f8c484a60c59247b2801143b66a474027f910f","datavalue":{"value":{"amount":"+0.8277037739753723","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q799337$7E3039C3-3BA3-4B93-BB28-80EF8E7C96BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc96c5038bee308e2d032e197479fc90cc186573","datavalue":{"value":{"entity-type":"item","numeric-id":4610195,"id":"Q4610195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82f8c484a60c59247b2801143b66a474027f910f","datavalue":{"value":{"amount":"+0.8277037739753723","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q799337$DEA7C9A4-0E32-4917-9F7A-9A455D6F217A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9333348fe711ec2bac47bb78e1458a71907cb886","datavalue":{"value":{"entity-type":"item","numeric-id":3816908,"id":"Q3816908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c10482cbae76e58693ab25c8ac55aa61748d1b3","datavalue":{"value":{"amount":"+0.8233078718185425","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q799337$66F5C50E-B53A-4AC4-9D96-E7FF552426B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1020dcbadd974a7c32952400e36fc2ab37885152","datavalue":{"value":{"entity-type":"item","numeric-id":1271174,"id":"Q1271174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07a3ea4d4a05fe785ef591b9cb8e818e6c47b20f","datavalue":{"value":{"amount":"+0.8212834596633911","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q799337$820D4918-2778-4AE8-9312-C3DD2CDB72C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a1eee0da531d675e09c32e048114e2786471e9e","datavalue":{"value":{"entity-type":"item","numeric-id":2940335,"id":"Q2940335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07a3ea4d4a05fe785ef591b9cb8e818e6c47b20f","datavalue":{"value":{"amount":"+0.8212834596633911","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q799337$817521B2-D375-44DF-950F-883C061BC0E3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"How to multiply matrices faster","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/How_to_multiply_matrices_faster"}}}}}