{"entities":{"Q799369":{"pageid":801217,"ns":120,"title":"Item:Q799369","lastrevid":64501479,"modified":"2026-04-11T20:18:22Z","type":"item","id":"Q799369","labels":{"en":{"language":"en","value":"On commutativity and approximation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3874605"}},"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":"Q799369$9CF6E473-920C-4AE7-A798-726FE3A55013","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"affe9f0f947653ee392b90c849066dc67d9ae26b","datavalue":{"value":{"text":"On commutativity and approximation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q799369$5027B5D1-2FD3-465D-95E9-35B21302C049","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"62ff68f99f7cba6d13e696737dc9ca96da3323be","datavalue":{"value":"0548.68036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799369$F6CAB6E0-4D4E-4B18-95A4-EC84911FF161","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"83784cb1cc780607296631685bceb226f8b017db","datavalue":{"value":"10.1016/0304-3975(83)90068-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799369$5073D23F-1C5D-4677-8D9D-1DB789D92871","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799369$4A2CD6F9-4C9C-47C9-8DB6-4364BEBFBFB4","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":"Q799369$6626ED37-F820-46FD-9520-02AFA84B0902","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c3cad004572825177622b0e158628719c8487dfe","datavalue":{"value":"The paper deals with lower and upper bounds on the algebraic complexity of bilinear forms based on the rank of the corresponding tensors. It defines the ''commutative border rank'' (cbrk) of a tensor, which is a modification of the definition of ''rank'' so that it can be applied to algorithms that a) only need to approximate the solution and b) make use of commutativity.    The following upper and lower bounds on algebraic complexity are derived, using corresponding bounds on cbrk: (i) \\(m(n+1)/2\\) multiplications are necessary and sufficient for n,m-matrix-vector product. (ii) 6 multiplications are sufficient and 5 are necessary for 2,2-matrix multiplication. (iii) \\((n/2)+2\\) multiplications are sufficient for approximating the value of a polynomial of degree n at a given point. The last section of the paper gives possible bounds on the exponent of matrix multiplication complexity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q799369$EA3E03E8-D496-41E9-B812-3EF27AD293BE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799369$69D7E17C-97DD-4440-8398-BBB0215DB682","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799369$2E27DA77-8866-4D3B-9799-87B30A3519EF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c954a243963fbfdf653d18a27dbe41c300497e13","datavalue":{"value":"3874605","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799369$660D8622-FE99-4CEE-B10A-7AB4D4F908B1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d2f2469c4e4a8bb9da83b7ea337e8a2758a2b663","datavalue":{"value":"tensor rank","type":"string"},"datatype":"string"},"type":"statement","id":"Q799369$8694EC6D-1F05-4034-8C39-75501E6CB368","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ad42331fe1306ade354b6f85458e0b64cdeac0a","datavalue":{"value":"polynomial evaluation","type":"string"},"datatype":"string"},"type":"statement","id":"Q799369$5E23EE31-2766-494F-8193-9EA556E2DCAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"405a4c12b3e0f2cec69c0a7e250d1805253fefb6","datavalue":{"value":"approximate algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q799369$1F1BA00B-E69A-4094-85D5-1C6B1981A8D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"86eef3b82e298f35b5ce8c635a7d57dc9a9869ed","datavalue":{"value":"approximate complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q799369$0C196426-ABEE-45FD-858A-99853C393FF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93ec0f49c4410c32c7ee6490c85a39fd93ede4ec","datavalue":{"value":"commutative border rank","type":"string"},"datatype":"string"},"type":"statement","id":"Q799369$5B5074C0-91CF-4669-B6A4-1E63A15D6404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"010c7d2ed2de24e1d8a535188cc19c40627ba1be","datavalue":{"value":"algebraic complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q799369$E0FB4D37-73E0-4232-B2F5-D14D223AED9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"21aa5c62b1913d51b98ea925b740f02db41c18ee","datavalue":{"value":"matrix-vector product","type":"string"},"datatype":"string"},"type":"statement","id":"Q799369$8011F717-DBB5-4C30-9B21-7F5A07F98DB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de71a87004b2cb6be9dfb83edd24b279968af4f7","datavalue":{"value":"matrix multiplication","type":"string"},"datatype":"string"},"type":"statement","id":"Q799369$30CEBF8D-7A33-43A2-BED8-2FAB2417A85B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"037a7271a05dd03a2192bbe167aeb5faf07fd93b","datavalue":{"value":{"entity-type":"item","numeric-id":205944,"id":"Q205944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799369$DDBCB282-3B12-4448-B3DE-326026C53808","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0aa8d3ac5bbff6b41e0a3e53ebafb780beece760","datavalue":{"value":{"entity-type":"item","numeric-id":441885,"id":"Q441885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799369$12468FD3-65C3-4A43-9951-731C3E1E6751","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":"Q799369$BEA37EE6-1157-48F1-A199-43C3CFB8F999","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9cadb42991033d149c25b7a1de9c850f5256c6da","datavalue":{"value":"https://doi.org/10.1016/0304-3975(83)90068-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q799369$CC0B257D-0B66-4F5E-B7EB-B1F40ADD3B2E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"89f3d6a3c33e9fdecdaf7e896bb545da0ce045aa","datavalue":{"value":"W2021882883","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799369$0B5C72DA-ACFE-46A7-8246-9A1AAE075AFD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb903d13ff3f41378ab4bd3ab769de49d91bbf13","datavalue":{"value":{"entity-type":"item","numeric-id":3890107,"id":"Q3890107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799369$847A2551-A27F-429F-BC5E-EF1D59B781AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3bfd11a4c1ce94b86c6942c6ee034fea4de139a","datavalue":{"value":{"entity-type":"item","numeric-id":1253097,"id":"Q1253097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799369$86D9C4E4-BBD9-473E-A92C-A43918C7F34D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"191386e5f1bcd09526502f33c3e1223d96d3500e","datavalue":{"value":{"entity-type":"item","numeric-id":3891766,"id":"Q3891766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799369$0BE6E536-27CA-43A8-A364-A88FBAEE8A73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"185812f4a394f61052aeca3705caa191a7cb923b","datavalue":{"value":{"entity-type":"item","numeric-id":3947117,"id":"Q3947117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799369$99AFF818-BE2D-48E3-ACB7-D7CC9F75D646","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d3119cb2162d160798b0e9adc09b82c53d47445","datavalue":{"value":{"entity-type":"item","numeric-id":3898027,"id":"Q3898027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799369$E974E8EB-C004-41A3-BC7D-A486E9273DFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6816c612d4fd1b15e4cc158394a9ebcee5e4ae91","datavalue":{"value":{"entity-type":"item","numeric-id":1240771,"id":"Q1240771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799369$FA0810A0-EA6E-4FE0-B245-16812EE83B7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90ad613ffef66147095e361398e11b36b06253ed","datavalue":{"value":{"entity-type":"item","numeric-id":3912015,"id":"Q3912015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799369$9CF7DBBC-8606-40D3-8804-EA035D13F786","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39ec0db8b8f0d2a52ec3b3caa281bd109ca87ce0","datavalue":{"value":{"entity-type":"item","numeric-id":4778270,"id":"Q4778270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799369$5393C69F-1C24-43B4-97B7-C7AACDDB3217","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"522e89673cb3122fd0bec879f19808cb3513e83f","datavalue":{"value":{"entity-type":"item","numeric-id":4047029,"id":"Q4047029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799369$E46F5343-C5E8-42D0-8E20-C57D897A39D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"808f6c2b11b575cdfd8a4301f9810ae8c8133229","datavalue":{"value":{"entity-type":"item","numeric-id":1245277,"id":"Q1245277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799369$E655EF88-2E14-4BD9-9D12-5E6C080C25C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a148e12ed1f41044f529beae0e83ef7878225c9f","datavalue":{"value":{"entity-type":"item","numeric-id":5584925,"id":"Q5584925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799369$69AD897C-F9BB-44A3-81EA-53AC4F5E9761","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e60f9f3b9b866a357e400d37167acbcb6e6a2a2","datavalue":{"value":{"entity-type":"item","numeric-id":794161,"id":"Q794161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17405e653205fc764b879849413dd993b72ede1d","datavalue":{"value":{"amount":"+0.8247334361076355","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":"Q799369$675D4EAB-69D6-4CB6-9892-919035DFCEDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa03fa047003eb1e017f4539481f87b81316e5c9","datavalue":{"value":{"entity-type":"item","numeric-id":891131,"id":"Q891131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb37d2d13fccc6a659b9d96f58c35d58e25f1a09","datavalue":{"value":{"amount":"+0.8157628774642944","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":"Q799369$BC4DA46C-14A4-4D08-AB19-4FBC9FC593BC","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":"ab70dd8906ef6a00ea9c858d23fc22ee260ee499","datavalue":{"value":{"amount":"+0.7935483455657959","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":"Q799369$60FDCA2F-1F6C-45CB-BF73-61CE68C1D595","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5eec027c34a71eb5547ca96b129964220d9eb0cd","datavalue":{"value":{"entity-type":"item","numeric-id":483185,"id":"Q483185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b1c3324c0d921f6b2c0d3df000012a286c5413d","datavalue":{"value":{"amount":"+0.7849534749984741","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":"Q799369$66BC36DA-F830-4E51-BD3F-5B78148B309D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"018d9c68550ffb3b7fe80afdc887d4231d19ed81","datavalue":{"value":{"entity-type":"item","numeric-id":5402555,"id":"Q5402555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdd609cf45682cbf1ff3817f18567998b5f78788","datavalue":{"value":{"amount":"+0.7842538356781006","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":"Q799369$6A5E9240-84B3-42C7-8F74-F6F9CC3AD79E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On commutativity and approximation","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_commutativity_and_approximation"}}}}}