{"entities":{"Q1192153":{"pageid":1202902,"ns":120,"title":"Item:Q1192153","lastrevid":47079403,"modified":"2025-12-31T14:53:48Z","type":"item","id":"Q1192153","labels":{"en":{"language":"en","value":"The average parallel complexity of Cholesky factorization"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 60606"}},"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":"Q1192153$5E5F1A5B-F92B-48FB-8B82-E27979A39A37","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8f64888d0639e979514bdcb8279e5ba83de8eb65","datavalue":{"value":{"text":"The average parallel complexity of Cholesky factorization","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1192153$2B54219C-9883-43FC-B749-A7A6948B1636","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"02b73f6e80080cf46aff25b1e4077f0ef29ffcbb","datavalue":{"value":"0755.65033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192153$4DA20E17-85BF-49CB-A21A-370FBD7AF921","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b5aa4a8038764311bbc2bbb6135be9fc45d419f5","datavalue":{"value":"10.1016/0898-1221(91)90204-H","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192153$651C8EFC-5E5F-4464-85E7-498DC7C4BF2D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5fd62271fe98c7ff9916cafed51cf35315eeeb31","datavalue":{"value":{"time":"+1992-09-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1192153$3301E12A-2BFB-46E2-884B-E701C305AD75","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"23f12d60c3e67d9256cf9cb8331cd3eac8d38f69","datavalue":{"value":"The author considers average-case performance of Cholesky factorization of sparse symmetric matrices using the minimum degree ordering. In particular, the parallel complexity (which is based on the number of eliminations that can be performed simultaneously at each stage) is examined. Using a combination of simple probabilistic analysis and numerical experiments on random matrices, the author conjectures that the average depth of the elimination tree after the minimum degree ordering has been applied is \\(O(n \\log n)\\) (where \\(n\\) is the order of the matrix). Moreover, after \\(O(\\log n)\\) stages of ``parallel'' elimination, a nearly- dense submatrix of dimension \\(O(n)\\) remains -- an observation that has significant implications for codes that implement direct factorizations of sparse matrices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192153$42CC0511-DC5B-4872-A71B-891C9B63C588","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9885aef811aa349f50c28b046ac04fbe99524c67","datavalue":{"value":"65F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192153$5DCE064C-1F8E-47BB-B9F9-E26C7984660F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192153$9CE722DC-4AC7-41EC-9958-63844B4A6BE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a7edc01538ef78e7e423d9c49f622de0faa5a14","datavalue":{"value":"65Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192153$D371038B-1F55-4105-B8E2-1C9273141A51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bb68a4ead97a966e0738a004317f6777af7ecfa4","datavalue":{"value":"65F50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192153$C9271CBE-214C-4C13-8861-22E443DB5540","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7aa0f442eba86253805e2db2eb964ff69caf6e78","datavalue":{"value":"60606","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192153$31D9890E-92D8-4BD7-96E4-3D43D5C2D5E3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ead8fd8cbb3a1fbf983f00ddaaae0ca51b8df56","datavalue":{"value":"symbolic factorization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192153$F91183AC-1718-4CC1-9A62-13CF0E4662B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78cb1abdfa7c1f4e3294f9cf9e61eb0863adf512","datavalue":{"value":"numerical factorization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192153$04659996-41F9-4B92-A8EA-7F2B87C8AAF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"980cbdd8f840a9f78ce7c51d5c1df7d6bf276782","datavalue":{"value":"solution of triangular systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192153$6F5913A8-7DA5-409B-8442-05CA205A0D6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd68de0363db7d2a3b81de007c2881aea333f6ec","datavalue":{"value":"average-case performance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192153$0D4C800C-FC18-4353-9742-F241608A4F1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4bfe029cf803d365e9f0bdbfa7738c8886f7730d","datavalue":{"value":"Cholesky factorization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192153$46204577-25A4-442F-9BC6-2B9D8D2350FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f657133a9655bdb6e343ee2c4f858a9b8ab95311","datavalue":{"value":"sparse symmetric matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192153$0494A58B-618B-46DF-88D5-562522A49A25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0934d596ead81ed0f19a3da8ea6044f1959b7fd","datavalue":{"value":"minimum degree ordering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192153$4A71A187-4749-4335-90C9-5C90EDFB3F96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a63f5fdf3038af45049408a9914d671beb783a5b","datavalue":{"value":"parallel complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192153$6C28FF2A-A2FD-4517-9401-78FB849F6BC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4a5ad9ff03b17c8457e1ed84ec13768350695ce6","datavalue":{"value":"numerical experiments","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192153$D1C7CEB5-7EEA-4C90-B975-15F4A9FEB3BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"47b64df201e56099c931a4f32180e8696bbbfee1","datavalue":{"value":"random matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192153$12E5FCFA-5915-4819-8241-3E68DFD81FCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e22079f02eadfae4633c9fa98f5b254733d13f3","datavalue":{"value":"average depth of the elimination tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192153$F63134C6-04DE-48EB-8254-6B1F096B1E81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"80793833f41f139406e47c88f9f035f82819bd29","datavalue":{"value":"direct factorizations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192153$5C059FA8-CA58-41DC-A546-2E775838B7BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d470915ad5f8b20e8e1116c88f9a812167267df5","datavalue":{"value":"sparse matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192153$96939E47-3283-4724-950B-7F08C8E50812","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"166288b54eff4f1175b22c60158bd19814132ba5","datavalue":{"value":{"entity-type":"item","numeric-id":852622,"id":"Q852622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192153$2B14720D-576F-4AA3-88A0-18DC01E3DB20","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"6dc6e1cb1460127bfdeb04be0899197c7b7f399a","datavalue":{"value":{"entity-type":"item","numeric-id":20575,"id":"Q20575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192153$B152044D-5738-4EF9-8140-BF26B03EE5D1","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":"Q1192153$21798AC6-97A9-4DC4-8993-F1D5ED70F4A8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"165c9d0cf5f8efdf8dfcedcdae47f99cc2a77457","datavalue":{"value":{"entity-type":"item","numeric-id":3823722,"id":"Q3823722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192153$91AC5E34-ECAB-4D27-BCC7-7697EDCB2F85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c20b9c062c65fa50baeb0cadac82aad397e032bf","datavalue":{"value":{"entity-type":"item","numeric-id":3960122,"id":"Q3960122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192153$1C2B35B5-0A19-4251-A243-6521C0DE7BD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27d7e3ea5e32569f562d397c63044c70766a5448","datavalue":{"value":{"entity-type":"item","numeric-id":5185900,"id":"Q5185900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192153$208A8FEC-F4DB-4CD1-9F79-7673B86B56AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e476db62e610ea29cd858f03ba132df81b28527","datavalue":{"value":{"entity-type":"item","numeric-id":4053004,"id":"Q4053004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192153$E8A71B4A-9904-45F5-B4B2-9A422493E2D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72bdc200c096a90cb093d01083b69c58672a0aa3","datavalue":{"value":{"entity-type":"item","numeric-id":3682518,"id":"Q3682518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192153$6288663D-2326-43FD-8726-818E7B201996","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61528cea5e75d684073907abfff700800ef58ce2","datavalue":{"value":{"entity-type":"item","numeric-id":3664299,"id":"Q3664299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192153$51987CC1-340B-4202-9774-5F2C2D265BA6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"293935db3834ff8b5d542ae1771b7c6cb66baa38","datavalue":{"value":{"entity-type":"item","numeric-id":85551,"id":"Q85551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192153$F587A2E9-7C29-4C2C-B07B-E52D464204D0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc35f71bf043be7aa9eb8c83325724b042636150","datavalue":{"value":{"entity-type":"item","numeric-id":5317648,"id":"Q5317648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f813c32aa3ad3b179fbe44559e192948252b537f","datavalue":{"value":{"amount":"+0.808140754699707","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":"Q1192153$E3C16E56-4FAF-41AE-8034-3EBB2EF63D0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e485a196134819a8e18021dad82837a84eb123c4","datavalue":{"value":{"entity-type":"item","numeric-id":4955154,"id":"Q4955154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14371bbbe691c6f14341c4bf322e01261c7db616","datavalue":{"value":{"amount":"+0.7974364161491394","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":"Q1192153$2396D8E3-2D92-4E6C-AE27-3A0FC92A3B4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de5eec35ef3e0eb8f13e15abb01eacd1d2d5f740","datavalue":{"value":{"entity-type":"item","numeric-id":2877076,"id":"Q2877076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"522cfbdf39d731d887b1db8183f293f56451fab1","datavalue":{"value":{"amount":"+0.7857730388641357","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":"Q1192153$5C22D3C5-0667-4214-9763-AFD97127849B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30483bf2994889340111e38dabfcaabc2814cc5c","datavalue":{"value":{"entity-type":"item","numeric-id":1960600,"id":"Q1960600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ccf84f08f143c55ec9204677a8d154a182192c7","datavalue":{"value":{"amount":"+0.7783308029174805","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":"Q1192153$7CEADD24-6FD0-47BC-8EA5-69216E3E78FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6601c0496c5e7e62d9a5ee1fbc6461ec5b83f84f","datavalue":{"value":{"entity-type":"item","numeric-id":1201013,"id":"Q1201013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"960a165a88206bb91a20c42f30c25d069906a286","datavalue":{"value":{"amount":"+0.7779020071029663","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":"Q1192153$EAD134FA-6408-461C-80B8-26B561505811","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1192153","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1192153"}}}}}