{"entities":{"Q1103322":{"pageid":1114074,"ns":120,"title":"Item:Q1103322","lastrevid":66990558,"modified":"2026-04-12T14:11:24Z","type":"item","id":"Q1103322","labels":{"en":{"language":"en","value":"The analysis of a nested dissection algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4052881"}},"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":"Q1103322$F0BBE1DC-AE84-4655-B1E9-0DBA60C6902B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5f533b6b6f717459b9c5fd4570f926906b0ee1cd","datavalue":{"value":{"text":"The analysis of a nested dissection algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1103322$95F5E8B1-6037-41BA-920A-2C592B0A0197","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3faeee6a680557413cdd8cf2437de1bb65dd0f95","datavalue":{"value":"0645.65012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103322$A5864F3A-8F26-4589-A455-FD9DCBF9B6DE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6bd33638126149e9ec8e37922480ecd2ae35ee28","datavalue":{"value":"10.1007/BF01396660","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103322$EC416F9C-52BA-4352-9F73-C2448F41B7C9","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":"Q1103322$E59014EF-EA85-49B6-9AD2-B73855FC3266","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"065c91f208b67eb2296cd8ea5272c33efd202f25","datavalue":{"value":{"entity-type":"item","numeric-id":598808,"id":"Q598808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103322$ECA0347C-FF57-4BCF-AD1A-B1D4E5F3C6DE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1b3d1ca268e3dbdbae43efb5a69b3a469f08bcb8","datavalue":{"value":{"entity-type":"item","numeric-id":78127,"id":"Q78127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103322$D4166AB2-E35A-4AE7-9172-B5FE429BCCEE","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":"Q1103322$1DFB1666-A5B9-44BF-81C3-5C0E62474ADB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"45e61a9eea7bb593ead3584416e7e141abe450c5","datavalue":{"value":"https://eudml.org/doc/133161","type":"string"},"datatype":"url"},"type":"statement","id":"Q1103322$859FE59C-CA4D-4503-8D07-23CD775F79EF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0cfd0bf8cda2289b3be362d01395974734a24a22","datavalue":{"value":"The nested dissection algorithm invented by \\textit{A. George} [SIAM J. Numer. Anal. 10, 345-363 (1973; Zbl 0259.65087)] is for preserving the sparsity in Gauss elimination on symmetric positive definite matrices. In the original algorithm by \\textit{A. George} and \\textit{J. W.-H. Liu} [ibid. 15, 1053-1070 (1978; Zbl 0408.65064)], a heuristic for finding separators is used. \\textit{R. E. Lipton} and the second author [SIAM J. Appl. Math. 36, 177-189 (1979; Zbl 0432.05022)] gave an algorithm for finding separators in planar graphs and two-dimensional finite element graphs; \\textit{R. J. Lipton}, \\textit{D. J. Rose} and the second author [SIAM J. Numer. Anal. 16, 346-358 (1979; Zbl 0435.65021)] used these separators in a modified version of nested dissection (with bounds O(n log n) of fill and \\(O(n^{3/2})\\) on operation count.)    This paper is analyzing the combination of the original George-Liu algorithm and the Lipton-Tarjan planar separator algorithm. This combination can be implemented in an easier way than the Lipton-Rose- Tarjan version. Based on some topological graph theory, bounds O(n log n) of fill and \\(O(n^{3/2})\\) on operation count are proved for planar graphs, two dimensional finite element graphs, graphs of bounded degree with \\(n^{1/2}\\)-separators.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103322$D83D3A68-ED85-49F1-B943-B0DC0897220F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9885aef811aa349f50c28b046ac04fbe99524c67","datavalue":{"value":"65F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103322$36A6EABA-EF42-44E7-885E-229A9B2C0668","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bb68a4ead97a966e0738a004317f6777af7ecfa4","datavalue":{"value":"65F50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103322$2DD8C61D-6683-459D-AD5E-35E5865D033B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103322$157A1EE0-D830-4E95-8D1E-792B51428966","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"874feb4bbef4040eedbc5ec6153ce9ec2c09279c","datavalue":{"value":"4052881","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103322$F9F3B481-568C-47D2-B8F5-1C2FCB3CFB18","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"41663558957a5273b5923bf82e3e9767a5506758","datavalue":{"value":"sparsity preservation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103322$2892C0A2-AC24-4690-A21B-E16A6CAB55D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f5f7ac618ac9ee4eed3cb552344096cd7970928e","datavalue":{"value":"sparse-contractible graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103322$DB9D9C33-224A-498B-AA0D-DD7CE3B51852","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2cd9fc58909cbea22490caa8c108a778f3dd2b16","datavalue":{"value":"topological graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103322$C3FF9C0A-2714-4AB7-AA9F-9396FE86AA40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0145954a8c6c1d8833cacc24b2536393e3cf21d4","datavalue":{"value":"nested dissection algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103322$8B1B05D8-DD5F-45FD-82DE-0B4A5512C9B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9a07bb06dceb68bf97b5bbf43ad985727fcdf05f","datavalue":{"value":"Gauss elimination","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103322$8A73CCC4-5510-4414-8570-0E510FDECB96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a840e7854f0696d1c1a893853ca81f32d2b4234","datavalue":{"value":"symmetric positive definite matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103322$8971CA28-071D-4718-A94F-D0C73194CEA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa0c719f68573fceba7e940cc3704ede8a44d63f","datavalue":{"value":"separators in planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103322$3E299861-AD96-4BFE-A812-091CE5EFE574","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"855d1388b3d6533d39055290566ad6f97f64d9d2","datavalue":{"value":"George-Liu algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103322$A165B33D-AD88-4D19-9550-288BE15BE8E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f18f1deb34bce2ee9c0739e560b77993e659094","datavalue":{"value":"finite element graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103322$5C2811EA-9475-4C80-A8F9-7545DEAD470E","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":"Q1103322$116C65F0-E4FB-409A-AD41-3960C62DF17F","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":"Q1103322$3E8A33E2-884A-4C32-9F8A-A3A68084E1E6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fd3a0b1f135c6dac172b52625070bb225752915","datavalue":{"value":{"entity-type":"item","numeric-id":3968972,"id":"Q3968972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103322$8D621A82-3DCA-4618-815F-89767D8E8BB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad132ed76d2c50bb9892411c1e7587f7b08828e1","datavalue":{"value":{"entity-type":"item","numeric-id":5674920,"id":"Q5674920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103322$9869FEF9-EA92-4906-A799-AAF87586895A","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":"Q1103322$77958C8F-E03C-4F9D-ADCB-F51E984C7F11","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":"Q1103322$549C549D-473B-4F23-A2C0-5891035CFE18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbbb32b7075575c1cb0708f2127f8e393f0d8c07","datavalue":{"value":{"entity-type":"item","numeric-id":3220606,"id":"Q3220606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103322$26065AFE-2087-4C86-9D6A-4179A29DC2A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"208d8b2742968ad5d6cb79b1d05ef3d75144d863","datavalue":{"value":{"entity-type":"item","numeric-id":3344230,"id":"Q3344230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103322$C62A7791-D4D3-4551-A741-BA42A6FBB97C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2c594e9705e780a6a4b2b01479e5d5553e79570","datavalue":{"value":{"entity-type":"item","numeric-id":5572939,"id":"Q5572939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103322$C4EF5F09-35A3-47C3-8661-1FEF0231A7B5","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":"Q1103322$E29161C9-E65C-4E5D-9022-82E8DA8F8D31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ff8a807471958a38eef5720fd27b64677c1d24","datavalue":{"value":{"entity-type":"item","numeric-id":3869371,"id":"Q3869371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103322$3F9994DF-2505-4801-B4B0-1D186C7D5BE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79f40f6cac0c780a9b93fef04ad01fbee5da55dc","datavalue":{"value":{"entity-type":"item","numeric-id":5731396,"id":"Q5731396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103322$F74EC822-4C8F-4BDA-BF63-8B85109E50C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b9c3d3ddd813706b0b4fb590181a03e51f774ad","datavalue":{"value":{"entity-type":"item","numeric-id":3284907,"id":"Q3284907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103322$6B5E5120-1F43-4823-BF8E-904DE676B65B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b546b29506726197d486ce9c402fd37a52289738","datavalue":{"value":{"entity-type":"item","numeric-id":5683627,"id":"Q5683627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103322$E7645340-0E2D-4818-8D79-871758B2DCC6","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":"Q1103322$A5AE4F9D-2984-4FC2-B72A-0C45CD567D66","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":"Q1103322$4DBE40BA-BF6A-4CC2-B483-8B778EBF00F5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ba87b3943b5104f39ceaecdba7fcd1b2aef5d08d","datavalue":{"value":"W2090129250","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103322$D4084373-813E-452F-8069-7149B3137A08","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f22721b9d3455daa508af6b95e6511a243d6649","datavalue":{"value":{"entity-type":"item","numeric-id":1114300,"id":"Q1114300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4416e94e11e6ba870486e0e151a04147d7d6363","datavalue":{"value":{"amount":"+0.8532108664512634","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":"Q1103322$0268B133-C056-430F-9BA8-D769AF889934","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa7c9f771924751ae299b14d9110562a859e64bd","datavalue":{"value":{"entity-type":"item","numeric-id":792734,"id":"Q792734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"713c2751b4d086acc445d00faeaa130fad1e8e50","datavalue":{"value":{"amount":"+0.8414421677589417","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":"Q1103322$1EAC1924-F277-46FE-B922-24B2984A586C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"249c70c79fcd6c735369f62017d353b1477ecea4","datavalue":{"value":{"entity-type":"item","numeric-id":4339133,"id":"Q4339133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39c41b2fde7995d28842406ab9970a24ae3184d5","datavalue":{"value":{"amount":"+0.8251587748527527","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":"Q1103322$1CD8EE2D-17E8-43DE-9D30-604B32045A9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"266653d242dff5ce043cc919090d01e218498f2e","datavalue":{"value":{"entity-type":"item","numeric-id":3805749,"id":"Q3805749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17d98f1f6f9666f7f9676e6171946de086cd6b55","datavalue":{"value":{"amount":"+0.8137017488479614","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":"Q1103322$0F4A044A-039B-44AD-BA27-648F2B97E4D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3700c348a7d39f2da2daa60c7ca249670407b345","datavalue":{"value":{"entity-type":"item","numeric-id":4288579,"id":"Q4288579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02c638d332c1980abd3b033e8449d6fdbdb6cb1c","datavalue":{"value":{"amount":"+0.7989054322242737","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":"Q1103322$68DB8EDF-E83D-4E13-B038-AF4F7BB45750","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The analysis of a nested dissection algorithm","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_analysis_of_a_nested_dissection_algorithm"}}}}}