{"entities":{"Q912562":{"pageid":914410,"ns":120,"title":"Item:Q912562","lastrevid":65324817,"modified":"2026-04-12T01:48:10Z","type":"item","id":"Q912562","labels":{"en":{"language":"en","value":"Optimal algorithms for Gaussian elimination on an MIMD computer"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4145222"}},"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":"Q912562$E5DFB48A-689F-48F2-9195-034CF51AA464","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"429743f6e945023ebd8cd2a4badbd9a924de0d5e","datavalue":{"value":{"text":"Optimal algorithms for Gaussian elimination on an MIMD computer","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q912562$1203FC8C-68F0-45A0-A528-DFDD299498B4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5670639e4e64dc30d2ac672626cda92bd7e68cbc","datavalue":{"value":"0698.65018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q912562$AD0FAF89-1A12-47CE-9760-FD6D5C31D320","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"48305e08c683c1efa55a2c23fb26f42d689b4c59","datavalue":{"value":"10.1016/0167-8191(89)90052-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q912562$7B6F9823-B874-429E-B92D-FD3C4A79C298","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9972538e77526934730e312c051e21ac0c02b883","datavalue":{"value":{"entity-type":"item","numeric-id":912561,"id":"Q912561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q912562$78DC672C-77AE-4D1A-A972-6BBE622200A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"94730d4f319bff810ecb15719995f961a7d0892b","datavalue":{"value":{"entity-type":"item","numeric-id":235410,"id":"Q235410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q912562$BD60C6F5-A219-404E-AC4F-D4EEC97CA179","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"eeac13f60c55bdb04ecb49274cc7b24a1688345d","datavalue":{"value":{"entity-type":"item","numeric-id":71527,"id":"Q71527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q912562$EDCCA856-6ECF-45A3-910E-646890888104","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q912562$0EE4B568-7B86-4B3E-BDB5-B77640ED4438","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b59dcdc06d2030e2cc1a1726e41d9821f10f27fc","datavalue":{"value":"A graph theoretic approach is used to derive asymptotically optimal algorithms for parallel LU decomposition with partial pivoting on an MIMD computer for a dense \\(n\\times n\\) nonsingular matrix using \\(p=\\alpha n\\) processors, \\(\\alpha\\leq 1\\). An algorithm is asymptotically optimal if its efficiency is maximum for \\(n\\to \\infty\\). The asymptotic efficiency \\(e_{\\alpha}=1/(1+\\alpha^ 3)=0.959\\) for \\(\\alpha \\leq \\alpha_ 0\\simeq 0.347\\) and \\(e_{\\alpha}=1/(3\\alpha)\\) for \\(\\alpha \\geq \\alpha_ 0\\) is proved, where \\(\\alpha_ 0\\) is the solution of the equation \\(3\\alpha - \\alpha^ 3=1\\). A high degree of parallelism can be achieved for \\(\\alpha \\leq \\alpha_ 0\\). The derived lower bound improves the results by \\textit{R. E. Lord}, \\textit{J. S. Kowalik} and \\textit{S. P. Kumar} [J. Assoc. Comput. Mach. 30, 103-117 (1983; Zbl 0502.65017)] for the minimum of processors (the smallest \\(\\alpha\\)) required to achieve the parallel execution in time \\(T_{opt}=n^ 2+0(n)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q912562$FF038EA9-B4E8-499B-95B8-B60D78B44FAF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9885aef811aa349f50c28b046ac04fbe99524c67","datavalue":{"value":"65F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q912562$67EBB116-A6A1-43B5-BCFF-137461E20036","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a7edc01538ef78e7e423d9c49f622de0faa5a14","datavalue":{"value":"65Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q912562$835F3B79-907B-47D5-B415-78F9DB84952B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q912562$DF228876-9CE8-4523-98B7-ADD16BB108F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ec3769495799f08479987ac368adf64f125a2b66","datavalue":{"value":"68N25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q912562$C55EB2EE-0187-4AE5-9D34-34DF99D6F6B7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c2f8bac4206df03a42edefc5f20e057e12d427a5","datavalue":{"value":"4145222","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q912562$203F0FB4-04B2-4C03-801B-4FF7CBF1CD14","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a39582725d773f66ea7b763bc55e831ca75ab427","datavalue":{"value":"Gaussian elimination","type":"string"},"datatype":"string"},"type":"statement","id":"Q912562$D79AF3F4-A102-4BFC-B254-2960B4C09A80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"492524d5c0785e07294780a480c26b249ab1f4c6","datavalue":{"value":"task graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q912562$5E0BED0B-08DB-4135-94D2-F942C620BCE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4780b02cfc7bc35a586062e3271a9f52fa94f067","datavalue":{"value":"complexity analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q912562$E7E890C7-75E4-48FF-BC0E-C93AA2DF77B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10755dbe5bded185142807963e71c09e160f1f86","datavalue":{"value":"asymptotically optimal algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q912562$F3653D86-6566-4832-818A-FF78D4059FC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"abad26d69cf074877d3563a7c4a8b0d645d14698","datavalue":{"value":"parallel LU decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q912562$DDCF0EB9-3E65-40A1-95BC-EABCCC727DAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc51caa0c50e2582ddd1570ab3d82d8caf958848","datavalue":{"value":"partial pivoting","type":"string"},"datatype":"string"},"type":"statement","id":"Q912562$9551DB97-DC81-447B-AE00-FB8EE7E796EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"135b29ce08dc059e2ef7acdfa2b40ae291019433","datavalue":{"value":"MIMD computer","type":"string"},"datatype":"string"},"type":"statement","id":"Q912562$485EB30B-4294-4CA5-82AE-974A23DB4764","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":"Q912562$9D28AC12-21D3-407D-AAAE-783D4E97BFD0","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":"Q912562$0FBA39D2-CE77-4F13-AECE-BA2F36B3CE24","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"091b7b6197d2dcdea3efdbf58d2797b35da52e1b","datavalue":{"value":"https://doi.org/10.1016/0167-8191(89)90052-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q912562$508C203E-016A-4360-9F30-E45845173F7D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a2a6b432bd8ed3e45a5707c001eaa1a9362dda2d","datavalue":{"value":"W2064687427","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q912562$91FCC347-DAF7-4502-9289-69922B31BA7E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a05e434e567ee8167f11e196ab3ae0367ce66de0","datavalue":{"value":{"entity-type":"item","numeric-id":1096997,"id":"Q1096997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13a084261570781543e85fe2c706088354086a17","datavalue":{"value":{"amount":"+0.8675233721733093","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":"Q912562$C9D2133C-A998-4A58-84A5-B022675161DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5077c6b1af008acd2a70e6fbf2fd0b5300b2a32","datavalue":{"value":{"entity-type":"item","numeric-id":3747616,"id":"Q3747616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e0fc29100ea68e766b030cf926fadb831e3c071","datavalue":{"value":{"amount":"+0.8650622367858887","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":"Q912562$8A298828-2CE1-4947-9D2B-265522A3E384","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec934d91b22c272522990f8b4547a2eea5908970","datavalue":{"value":{"entity-type":"item","numeric-id":918627,"id":"Q918627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d730f02406fef34ac5aa4120503276815a452c7","datavalue":{"value":{"amount":"+0.8608806133270264","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":"Q912562$A5501D08-8F6F-42FB-90BD-F2485736D7D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef3dd94ea23c128723131186921b5e1bbdb1ef53","datavalue":{"value":{"entity-type":"item","numeric-id":3809117,"id":"Q3809117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5400572989190b5728143dac1a75c37a752f7f7d","datavalue":{"value":{"amount":"+0.8481062650680542","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":"Q912562$699B9D2F-EA18-42C4-96AA-C8E69C775EE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b455375b7cfe86a0cd500fc1f42bd800c3f5fc38","datavalue":{"value":{"entity-type":"item","numeric-id":3813133,"id":"Q3813133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02ce6be736f9155141926d5210809ce032727177","datavalue":{"value":{"amount":"+0.8377100825309753","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":"Q912562$F1264AE5-9A4A-4F89-AFE3-9693E607DE95","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Optimal algorithms for Gaussian elimination on an MIMD computer","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Optimal_algorithms_for_Gaussian_elimination_on_an_MIMD_computer"}}}}}