{"entities":{"Q1111029":{"pageid":1121778,"ns":120,"title":"Item:Q1111029","lastrevid":49219201,"modified":"2026-01-06T19:11:38Z","type":"item","id":"Q1111029","labels":{"en":{"language":"en","value":"A parallel graph partitioning algorithm for a message-passing multiprocessor"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4074511"}},"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":"Q1111029$197E9A03-AAB0-433D-90D7-E50E82B5F0C0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d723bb40400b2f49c648c0afde2fc930c87bc2c4","datavalue":{"value":{"text":"A parallel graph partitioning algorithm for a message-passing multiprocessor","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1111029$CAE105A6-7D31-4F0C-A95D-CCC8D6644970","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"300104865878e76a0abd85ea4c279db4c4b25ccb","datavalue":{"value":"0657.68073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111029$146C60F2-5AA5-46E4-9990-C3AA590DD245","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"87dbaae10a535c446427be665b751caecd906209","datavalue":{"value":"10.1007/BF01388998","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111029$81DD8A71-8224-49D4-9867-E7B56058434B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2828cd1ba69a52725b098d64641101049cd7fafa","datavalue":{"value":{"entity-type":"item","numeric-id":676607,"id":"Q676607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111029$922C3A1F-F8D5-42EE-A60E-40E02BA42092","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c0179b4b46bd26d30a9a1e24d82d2cd7543d86e5","datavalue":{"value":{"entity-type":"item","numeric-id":1108737,"id":"Q1108737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111029$F25BF6A9-58D8-4EB1-B34C-DD5B8614BB1D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a32831c4e3f60d79ea2f79afb884ef69e4c8191c","datavalue":{"value":{"entity-type":"item","numeric-id":199286,"id":"Q199286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111029$877EE37E-9F20-4DDC-BD68-7BF9792A2077","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1111029$795E2E1C-B92B-4B31-AEC4-F7B0055FC673","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b1a9b3b48f0de4b75100e0d200cfb4bfb6494212","datavalue":{"value":"We develop a parallel algorithm for partitioning the vertices of a graph into \\(p\\geq 2\\) sets in such a way that few edges connect vertices in different sets. The algorithm is intended for a message-passing multiprocessor system, such as the hypercube, and is based on the Kernighan-Lin algorithm for finding small edge separators on a single processor [\\textit{B. W. Kerninghan} and \\textit{S. Lin}, Bell Syst. Tech. J. 49, 291-307 (1970; Zbl 0333.05001)]. We use this parallel partitioning algorithm to find orderings for factoring large sparse symmetric positive definite matrices. These orderings not only reduce fill, but also result in good processor utilization and low communication overhead during the factorization. We provide a complexity analysis of the algorithm, as well as some numerical results from an Intel hypercube and a hypercube simulator.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111029$5786FC60-D298-4CD6-A6C4-09E883DC48CE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111029$DEFE35D2-16B5-4887-84F3-4BFDA5579FA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ec3769495799f08479987ac368adf64f125a2b66","datavalue":{"value":"68N25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111029$BFFFA8B4-2B31-4AB9-AC6D-118EB5C450C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bb68a4ead97a966e0738a004317f6777af7ecfa4","datavalue":{"value":"65F50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111029$079FED52-A25F-405F-85DA-5A9733D265BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3a56ed6d195ea3539360546b34a91d2ad94c0346","datavalue":{"value":"15A23","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111029$43FEDBF6-88E6-4EF8-991D-2CB05615FA81","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8a55491e6da39b89eb2ca84313dd5b8e6014e7c1","datavalue":{"value":"4074511","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111029$E79A5F5F-DB31-48D1-9498-7B8691936DBC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e242af08a265f147fecdde71acc893f1df2b816","datavalue":{"value":"graph partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111029$CBD74CA2-F117-4CFF-9B88-E1CEFBD1EE98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"80e83d9f01aafb62e290c3fe4c0afaf75a8f1785","datavalue":{"value":"sparse Cholesky factorization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111029$52A201A9-4F06-4F47-9EF7-11EFE663C8CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6154870566cbdb3fbb3b3a51a8aa3b5ce2ac19c","datavalue":{"value":"reordering sparse matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111029$4321B097-EBD9-4F28-B9BC-AF2E67EC3BC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0967c5f93d36d6aa18ee008d77ee288965d952b9","datavalue":{"value":"parallel algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111029$267D9C6D-DDD5-4B93-9900-26C1CC7EBCC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84b39af02b6294cfc0ac85512f98aea0041760bd","datavalue":{"value":"hypercube","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111029$1BD93DEB-8CD8-480D-AA99-F6CE32DF682E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25bb8cc4410baf8c04d7611fd67c6f3c82f6763b","datavalue":{"value":"Kernighan-Lin algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111029$FB4BB864-BE41-4EE3-93F6-352540043840","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4780b02cfc7bc35a586062e3271a9f52fa94f067","datavalue":{"value":"complexity analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111029$3BEFE868-8352-41CD-AF58-3233BA0161D6","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":"Q1111029$E0874B8E-C8C4-4181-A487-FB4F628D56F1","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":"Q1111029$542797A6-C0C4-4512-99B7-2F13C26BFB29","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a44f31abbdd4dc84e5f661896a7812e44411ddf","datavalue":{"value":{"entity-type":"item","numeric-id":4100093,"id":"Q4100093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111029$88B56992-9847-4511-B385-86D5FAFD9D37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6141476b65d14923fb002fbcd5da8a63dbb0016","datavalue":{"value":{"entity-type":"item","numeric-id":3875202,"id":"Q3875202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111029$61546AA5-189F-4549-AC38-265307DCF1B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a2a57b475ae76d5a53ffe9b99df300f7fdeea33","datavalue":{"value":{"entity-type":"item","numeric-id":3906439,"id":"Q3906439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111029$CF98B231-5FA9-47BA-ADA2-DD986C8CF80F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90f71993a254b670892029bc664b12dfe5eef112","datavalue":{"value":{"entity-type":"item","numeric-id":3783413,"id":"Q3783413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111029$AA2558BB-CC55-4F16-B1B0-1D4C4A6E2016","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1be60cd775b4a8ff89a8f3ced6156dc9c6343f0","datavalue":{"value":{"entity-type":"item","numeric-id":1111029,"id":"Q1111029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111029$1C2B0F31-4CE3-4C66-89D7-CE7A2C99E8EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64f5d3a895cb914cddae8f3e8a14724148d64ac9","datavalue":{"value":{"entity-type":"item","numeric-id":1108738,"id":"Q1108738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111029$74913FF6-3E14-415E-BCA9-01ACAE71F3E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"deb3c6b2f202ff89e0f2c6f2570013cc13bacb8b","datavalue":{"value":{"entity-type":"item","numeric-id":1263230,"id":"Q1263230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111029$84D0521D-E7EA-45A3-8369-F01A2EE68B84","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":"Q1111029$BA283E47-24E1-4E4E-9E9B-B0F43C179F07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111029$B27044B5-A1E8-4648-B5B3-7412871C2D3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f46500d9d46fda8ccacf67c99395b57c2f841ae","datavalue":{"value":{"entity-type":"item","numeric-id":3813197,"id":"Q3813197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111029$5A938F6D-0052-4E17-B4CE-79F128B88A90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8592b19f12bd09556a4de81ad49778d747c4f77b","datavalue":{"value":{"entity-type":"item","numeric-id":4124209,"id":"Q4124209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111029$EF5C4398-2D3B-4E9A-8AD4-6AB31D05E368","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2eada90ebf2f4ebefb88c819aaff0d8304f2d95c","datavalue":{"value":{"entity-type":"item","numeric-id":1086977,"id":"Q1086977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111029$64F31C2B-0B20-4D92-BF5C-DE01A5CAE608","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79fe44d9c4f558bf9934d95ec73ad21b614b29f1","datavalue":{"value":{"entity-type":"item","numeric-id":760156,"id":"Q760156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111029$3259190E-C1AB-408E-8E1C-51B3EBEA469F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e60a13ec6b06492e8b0f1e98c7dcd89dd90a8f04","datavalue":{"value":{"entity-type":"item","numeric-id":1103322,"id":"Q1103322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111029$4B24A84B-6FF6-4E90-AED9-B09070F2599D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d8a6fba063f4f8f42dbd7335ba97bd78fc6f88c","datavalue":{"value":{"entity-type":"item","numeric-id":4185935,"id":"Q4185935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111029$42E49FC0-8F9E-4813-BBC0-EBFBADD5CEF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"352b33bd7bedec9a5caebd970d73a33c036faf67","datavalue":{"value":{"entity-type":"item","numeric-id":4195885,"id":"Q4195885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111029$13DCE017-332A-4028-BCF0-FA1A116458F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"368d4c4b9aa58566b36a6418c6fb41c2eac35229","datavalue":{"value":{"entity-type":"item","numeric-id":3796624,"id":"Q3796624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111029$9B1CFAE6-E793-4C23-8728-6267B03CA56F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00ca2f48a2191c5730d549920215294d2f4aa0ee","datavalue":{"value":{"entity-type":"item","numeric-id":3210039,"id":"Q3210039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111029$F4B594DD-D04A-4C5E-8C16-26159E7A80E6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cf42ea8f85c9fb00f974e7543adaa1607fee97b7","datavalue":{"value":"https://doi.org/10.1007/bf01388998","type":"string"},"datatype":"url"},"type":"statement","id":"Q1111029$307C45AB-DDA9-4E25-9323-F0C9BC729527","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2936bc6c7a003fecfcdafdf41737ad83376b12d1","datavalue":{"value":"W2786884778","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111029$19C96C8C-A18B-447C-A20C-8D722DD5187A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6dda84e816197c65b78d799203284e6cc85db6e7","datavalue":{"value":{"entity-type":"item","numeric-id":3124737,"id":"Q3124737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5239a67f958216733efc52fed6fbcea6fe41f1b3","datavalue":{"value":{"amount":"+0.8777633309364319","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":"Q1111029$1497B9C0-381E-4B8A-946E-88710FD5DADC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58bdb50a521f03daf4aa31bf823160d5cd8c7f70","datavalue":{"value":{"entity-type":"item","numeric-id":4210419,"id":"Q4210419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5239a67f958216733efc52fed6fbcea6fe41f1b3","datavalue":{"value":{"amount":"+0.8777633309364319","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":"Q1111029$37E67FC8-E9E8-46B7-85DA-040BCF31BAAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73193c230af18999490bbecba2c58cfb68cf972a","datavalue":{"value":{"entity-type":"item","numeric-id":1818794,"id":"Q1818794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0882ea3bb6f38a2669b95e067a2f3625dfe9b10","datavalue":{"value":{"amount":"+0.8595733046531677","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":"Q1111029$A78B4D76-8DB5-415C-98F2-683035F3EE17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be55c255812c7f030b47be22134c2116d4e7a7ae","datavalue":{"value":{"entity-type":"item","numeric-id":4038712,"id":"Q4038712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e1c3ecb9afcc6f58796dd4f2f4cbb7147f4661e","datavalue":{"value":{"amount":"+0.8476089835166931","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":"Q1111029$80979AAB-4388-407D-A036-49B05A1F9C12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b235f16bd29fdaa88c3f309392cfb5c7efcc5802","datavalue":{"value":{"entity-type":"item","numeric-id":582120,"id":"Q582120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7a3ced81260acbf2d0d1e0e68aa9c0a659b0102","datavalue":{"value":{"amount":"+0.8437546491622925","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":"Q1111029$914D3146-AAF5-4A89-A0F6-0CF235A9AE86","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1111029","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1111029"}}}}}