{"entities":{"Q1123535":{"pageid":1134284,"ns":120,"title":"Item:Q1123535","lastrevid":66803364,"modified":"2026-04-12T12:58:38Z","type":"item","id":"Q1123535","labels":{"en":{"language":"en","value":"Reordering sparse matrices for parallel elimination"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4109939"}},"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":"Q1123535$830EEF30-E0D1-45A9-BD43-3DCCA7BC3333","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c5af506ec7dde6a8e1e56b619997d8654ff34e8e","datavalue":{"value":{"text":"Reordering sparse matrices for parallel elimination","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1123535$E65DDCCE-0C54-4002-91ED-A70624C5251F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f227d44406b80ee48bf6ece5c0cecabace0df76a","datavalue":{"value":"0677.65023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123535$78F54B06-253F-4F2B-B7D4-687FDF59C90F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f21e4bfbc939b7aefbbc3eaade27119e14899889","datavalue":{"value":"10.1016/0167-8191(89)90064-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123535$F713ED40-1FBF-4055-B4AF-05C52A34888E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1f153417668b9a5c5d367a1f1668e47f50cfb609","datavalue":{"value":{"entity-type":"item","numeric-id":871146,"id":"Q871146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123535$FDD9EE23-4FB1-477A-B563-3E33CD76025F","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":"Q1123535$FC64A547-21E1-499B-AD7C-C8389178BFDA","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":"Q1123535$7ABE2C06-8D0D-442F-AA3E-2899D332BC1F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1ded1b92eb604401208872d117b35fc202e90c64","datavalue":{"value":"This paper describes a new reordering algorithm for a sparse symmetric positive-definite matrix A which produces a matrix suitable for parallel Gaussian elimination. It is assumed that a good fill-reducing ordering P of A has already been obtained. The reordering scheme proposed by \\textit{J. A. G. Jess} and \\textit{H. G. M. Kees} [IEEE Trans. Comput. C-31, 231-239 (1982; Zbl 0479.68034)] finds a final reordering \\(\\tilde P\\) which has the same fill reduction as P.    Firstly, the current author shows that the process generates an elimination tree with minimum height amongst all such trees from the class of equivalent orderings. In the second part of the paper the author considers a new reordering strategy which forms the elimination tree of the matrix \\(PAP^ T\\) and reduces its height without the introduction of additional fill.    Numerical examples with standard sparse systems of order between 1000 and 6400 demonstrate that ordering times may be reduced by a factor of two or better over a basic minimum degree ordering previously described by the author [ACM Trans. Math. Software 11, 141-153 (1985; Zbl 0568.65015)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123535$863F3B52-79C9-4961-AEEB-50AAB25F7B3D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9885aef811aa349f50c28b046ac04fbe99524c67","datavalue":{"value":"65F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123535$09E7E7FC-FDE0-4B41-BDCE-CDA6E0EF1EA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a7edc01538ef78e7e423d9c49f622de0faa5a14","datavalue":{"value":"65Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123535$DA2B997F-7D2C-428A-AC7B-199CCE27AB55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bb68a4ead97a966e0738a004317f6777af7ecfa4","datavalue":{"value":"65F50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123535$D0404FE2-2ECF-44B4-8560-323F66F80F6E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"61f4ee28ead7ba63015dfb353cb2bd88f748d765","datavalue":{"value":"4109939","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123535$1C9FAADC-386E-459D-BF73-9AFBA9EFD8FB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d135b4b2c79038e67cad967abf250f4ead091ae4","datavalue":{"value":"reordering algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123535$3133AF3A-A7D8-46B3-A3B1-80C6D62BEF0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a4807fa8cbe1b62c244c41101efd6558f5068b9","datavalue":{"value":"sparse symmetric positive-definite matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123535$59D2C426-B3E8-4034-9577-11DCD791CADE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"31746d742ce79a61b7a3efee7d0fc79a50b40ae9","datavalue":{"value":"parallel Gaussian elimination","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123535$B6D1A9CC-BCCA-47EC-826D-33C6DAB801A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3df6bd86331c4f112a52d4d647b9c484dff9a0b9","datavalue":{"value":"fill-reducing ordering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123535$18BF2FC7-DA1E-4E96-A398-548964E216C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"26d3e33e327c7c20e4a80fc767125a4f24ef4dde","datavalue":{"value":"elimination tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123535$B5B071B2-9EE5-47FF-803E-C355D9EB30E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"255badb5de8e54836b0083190a8a25bf7781372a","datavalue":{"value":"Numerical examples","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123535$8BD66689-4D54-4BE6-9FA8-D2E75C15F2AC","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":"Q1123535$47F79EDF-4D70-4511-8601-5D0B4DB182B3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"26f4b548699001bc82bdf5f9b874e8057535d11f","datavalue":{"value":"https://doi.org/10.1016/0167-8191(89)90064-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1123535$BEA3915F-911A-4602-94A1-D572D2C5ED67","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7d57d00f113bf824cb2b14ff033efbd454ec807f","datavalue":{"value":"W2059098138","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123535$B553E054-AE70-4FA2-80D8-6040AF3EFE1B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19b6f511b870ec1ba7f3cfad12cccc7925e47300","datavalue":{"value":{"entity-type":"item","numeric-id":3468542,"id":"Q3468542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dbee2fad4ef5c1bef38125e7d50438a51a6d9903","datavalue":{"value":{"amount":"+0.9314065","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1123535$5E25A43A-E207-418A-AB25-8F59177ECBFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e2975388bd26ff07363482a0e8b70e5f704422d","datavalue":{"value":{"entity-type":"item","numeric-id":3802488,"id":"Q3802488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81924072434d1c1e677663d96bd1035cdd3cdd65","datavalue":{"value":{"amount":"+0.9190923","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1123535$7FC1B694-DA0C-4862-8D05-E9A99BC8964A","rank":"normal"},{"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":"ab9ad7be84d4befd36ff7cad941e30a83a84cdca","datavalue":{"value":{"amount":"+0.9181663","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1123535$58A05705-071D-41CF-BE0A-965631C1123F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5ec5e3b19a8629583d8ade4e18f1109ee163630","datavalue":{"value":{"entity-type":"item","numeric-id":1119337,"id":"Q1119337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d09007a43c5e61faa97ea26d67ca6e19b8fecb3","datavalue":{"value":{"amount":"+0.90761596","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1123535$0E5EF0C2-6DB7-4682-877F-C7BC36133CFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e6a1d41dc7452ab3aaec750a80007c27d4e6cab","datavalue":{"value":{"entity-type":"item","numeric-id":3799564,"id":"Q3799564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d09007a43c5e61faa97ea26d67ca6e19b8fecb3","datavalue":{"value":{"amount":"+0.90761596","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1123535$A75261EF-DDF9-4875-9473-C71033EA285B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73cf0740d9007669850fbfedaa4931ad70d919e0","datavalue":{"value":{"entity-type":"item","numeric-id":5898183,"id":"Q5898183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2db5fee06bdcb7b09bb6a9090c8b073e6712981","datavalue":{"value":{"amount":"+0.90518284","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1123535$A3E38739-A200-439C-8B1F-D3F68EB50E1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5893013c9b27cf1314927dfdae240249dc9c31ae","datavalue":{"value":{"entity-type":"item","numeric-id":672596,"id":"Q672596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38d224f36448635fa15f06937d29fbdec5c9e59f","datavalue":{"value":{"amount":"+0.90313137","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1123535$361F035C-FEC0-4D11-BD6B-EA9722C522E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c4112fb2bcc456b925189afd5357b8037557dd3","datavalue":{"value":{"entity-type":"item","numeric-id":3796624,"id":"Q3796624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9360e206173351470dfc29dd45e1749bdec9428f","datavalue":{"value":{"amount":"+0.89901316","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1123535$348E2560-789E-48CC-9D7D-B28B9A60D79E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"989a622a2d9f319541d6417f7832b5b80816795b","datavalue":{"value":{"entity-type":"item","numeric-id":1402303,"id":"Q1402303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d931404d1fd253c1753073c5a415f2d8bac18a80","datavalue":{"value":{"amount":"+0.8971138","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1123535$1B686594-AC5F-4833-B31A-56CF689556B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d35549c1e205b64c4b7229dee6f1e4e0920b61ab","datavalue":{"value":{"entity-type":"item","numeric-id":4693189,"id":"Q4693189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7fd68ddc1bd6688692e8c47e541c601eb35bb434","datavalue":{"value":{"amount":"+0.89658344","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1123535$980C4F0D-85AC-42DB-8C72-9645DBAC0DBF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Reordering sparse matrices for parallel elimination","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Reordering_sparse_matrices_for_parallel_elimination"}}}}}