{"entities":{"Q1114300":{"pageid":1125049,"ns":120,"title":"Item:Q1114300","lastrevid":66456873,"modified":"2026-04-12T10:11:43Z","type":"item","id":"Q1114300","labels":{"en":{"language":"en","value":"Algorithmique et calculs de complexit\u00e9 pour un solveur de type dissections embo\u00eet\u00e9es. (Algorithmic study and complexity bounds for a nested dissection solver)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4084840"}},"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":"Q1114300$80FAF2A2-C797-4455-9D5B-3D1AC73EE500","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4921ea3efa8ade5d486218d7f11b1b7c5567ae51","datavalue":{"value":{"text":"Algorithmique et calculs de complexit\u00e9 pour un solveur de type dissections embo\u00eet\u00e9es. (Algorithmic study and complexity bounds for a nested dissection solver)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1114300$60981CC1-5311-4AE2-B9DB-CE7AC8145C0B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f48b690b228e584d5c3bfd8558cc7e007100e9dc","datavalue":{"value":"0663.65020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114300$CDA3568C-C1C9-4BED-B969-39E6703E2F63","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"916f8f27fb5c5623d3cff71137bc9b8ef7b50745","datavalue":{"value":"10.1007/BF01396049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114300$923F3310-624C-4326-B663-F45EB36C6726","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aedf720352fcca932fab3523c4bbcafd7c4c7cdb","datavalue":{"value":{"entity-type":"item","numeric-id":1104176,"id":"Q1104176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114300$2B5595B5-957F-4081-BF77-0F1C31343820","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":"Q1114300$CEB46303-A6A8-4FF5-9697-2044224A9822","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":"Q1114300$4355AB65-B915-4EA2-9B00-15E0BB0D81C4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"00d3f1b3426a1b12e965cf5dbbd977c1436468ee","datavalue":{"value":"https://eudml.org/doc/133364","type":"string"},"datatype":"url"},"type":"statement","id":"Q1114300$4AA160C3-01C6-4D9D-A9DC-5EDB5538244B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d7b622f27ebd89b783d3df458b89ba33df2793b2","datavalue":{"value":"We consider the nested dissection method based on separator theorems introduced by \\textit{R. E. Tarjan} [ibid. 50, 377-404 (1987; Zbl 0645.65012)] and the second author [ibid. 47, 175-190 (1985; Zbl 0537.65025)] used for solving large sparse systems of linear equations. More precisely, we study a block storage scheme such as proposed by \\textit{A. George} [SIAM J. Numer. Anal. 14, 161-179 (1977; Zbl 0356.65023)] for regular square grids and we prove the following results: first, for families of graphs of bounded degree with \\(n^{\\sigma}\\)-separator theorem, \\(1/2\\leq \\sigma <1\\), the overhead storage of the block data structure for the factored matrix is linear in system dimension; on the other hand, by adding a non restrictive assumption on the separation, this structure can be constructed by a block symbolic factorization which runs in time linear in matrix dimension. Numerical experiments illustrating these theoretical results are provided.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114300$F278D20E-30C0-4C5E-B2B8-B1C1EEBE273C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9885aef811aa349f50c28b046ac04fbe99524c67","datavalue":{"value":"65F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114300$75710CBF-D391-4FF4-A5BD-C6A2CDEDA2B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bb68a4ead97a966e0738a004317f6777af7ecfa4","datavalue":{"value":"65F50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114300$51611AFD-FE1A-41E1-B515-B13B3E6CDAD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0493e66c36e2772f355d1d5e05f0013b3d870be0","datavalue":{"value":"65N30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114300$0E60EA3C-4477-40BB-AB87-C3D0E2D2A83A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"10f72afa0a0056347b2124314497ff11fe53c94b","datavalue":{"value":"4084840","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114300$F196ED33-4716-464E-AEF9-496B61600F7E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9a07bb06dceb68bf97b5bbf43ad985727fcdf05f","datavalue":{"value":"Gauss elimination","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114300$916A6910-45F5-454C-94AC-32FA1FB92A4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3522f369b37f0a765caf643c9c11f9ce492080f3","datavalue":{"value":"separator theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114300$688345FE-03FB-4AEC-A534-4D4C825DA325","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114300$1939F797-9099-4077-A3C7-5F3677FE5737","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b449a91ffcbbf24ef2877ab80b29a8916043c1a","datavalue":{"value":"nested dissection method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114300$C36A58DE-28A1-45A6-952E-C8125D06CB5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a020163db5ae7e325f6f02c2c1b9de1876ea3a9","datavalue":{"value":"large sparse systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114300$6356A759-A624-4FC7-86B0-719F08465F04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b06b8aea71ed4fd2a074994002341a95a084367b","datavalue":{"value":"block storage scheme","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114300$2D12211E-1FCA-4E35-BE3E-3CB7C35D540E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"719ed930d7b23331709e18495f2302eeea09df85","datavalue":{"value":"Numerical experiments","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114300$D60A161C-F06B-4996-BA10-C9838B27A4C8","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":"Q1114300$71A5D632-173D-4EB2-994C-4B375CBCF831","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":"Q1114300$5918DAB4-F645-44FC-97A1-626F75D5EFF9","rank":"normal"}],"P223":[{"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":"Q1114300$1FC7C611-E2A3-49C9-9155-BCCAC4E8F174","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"003b78277e98c7adf3ae2918ce4a7fe34af0637b","datavalue":{"value":{"entity-type":"item","numeric-id":4127870,"id":"Q4127870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114300$CF7F1B79-3A98-44F9-97E2-BD3F1DE8231C","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":"Q1114300$6D274BF3-A6DF-465D-A72E-3D07AD495DC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44915680340ead0067ae993b0a669aeaff36bb8c","datavalue":{"value":{"entity-type":"item","numeric-id":4171505,"id":"Q4171505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114300$BC96FFFA-613A-427D-ABF8-55CF324767FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f86f3039f299ca0352226ce2ec797139305e8a92","datavalue":{"value":{"entity-type":"item","numeric-id":3899516,"id":"Q3899516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114300$9C9D0433-B4E9-4674-892F-129C7D93989C","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":"Q1114300$B3C31E9E-93C2-408E-ADB6-BFC12ABB7CD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4161c7864db9559c1f43e0126c670eeb9076c86a","datavalue":{"value":{"entity-type":"item","numeric-id":4176338,"id":"Q4176338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114300$522007F4-EA03-419A-A9E7-7981DE1A1BDA","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":"Q1114300$334AC5A7-9108-4A5B-A542-23C8E27CF4AB","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":"Q1114300$A8F39C95-0DA2-4C41-A6B6-1BD717C5129B","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":"Q1114300$0944107D-B7D9-433F-9789-99B0F9C9F980","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e83e4eb2959b9925e3ff367dabc202da2b57d82c","datavalue":{"value":{"entity-type":"item","numeric-id":3321331,"id":"Q3321331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114300$C6EDC2E4-B99C-457C-91AA-80C09EB5870A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0980fc4823dcb1079335bed9c58f81aca181bae6","datavalue":{"value":{"entity-type":"item","numeric-id":792734,"id":"Q792734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114300$1616597A-7F03-4120-81CF-E65A80C2F205","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":"Q1114300$567D951E-5F44-4BC0-B41B-7ED016F2F8A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"844f7a57fc6723bb022d75f7ba096fa7ed7c7a00","datavalue":{"value":{"entity-type":"item","numeric-id":3953077,"id":"Q3953077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114300$F3E7DA8A-8D79-4C18-9249-16F7A9C221F2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"51ab5eb26601a2d5fdda61e10496a573c012149c","datavalue":{"value":"W379665175","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114300$97192154-BC95-467C-AEE0-11DA7CADD755","rank":"normal"}],"P1643":[{"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":"b5324c4f7d961f5469f76e06ab57dec25ebeea1c","datavalue":{"value":{"amount":"+0.8909736275672913","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":"Q1114300$05604A84-516C-4FE9-9E4B-D7AD65C8D7EB","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":"baa28e6475b7b2bfc6918945cfaf80ebd346eb15","datavalue":{"value":{"amount":"+0.880870521068573","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":"Q1114300$126C0563-710B-48CE-9666-306270752711","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e45bfffb3a33e2069bf4ea65718b3b903e504ea8","datavalue":{"value":{"entity-type":"item","numeric-id":1103322,"id":"Q1103322"},"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":"Q1114300$E778177D-CA8A-4CA3-9275-584624BE26EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2265cb560119de369188c833d575f16db4ebfff","datavalue":{"value":{"entity-type":"item","numeric-id":3789083,"id":"Q3789083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95aab46ddbebf466b6899cce3694bfcb5691ce08","datavalue":{"value":{"amount":"+0.802398145198822","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":"Q1114300$C98F735E-8C7D-4FAB-8846-08CAE5F3999B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3bb175095c9da50620d53386ecf86302c905dc37","datavalue":{"value":{"entity-type":"item","numeric-id":751757,"id":"Q751757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87c6563b33cfae9a2fdf480221048f053cb67f59","datavalue":{"value":{"amount":"+0.7978327870368958","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":"Q1114300$D6E29FEA-8430-440B-AF37-51EFF1F94708","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Algorithmique et calculs de complexit\u00e9 pour un solveur de type dissections embo\u00eet\u00e9es. (Algorithmic study and complexity bounds for a nested dissection solver)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Algorithmique_et_calculs_de_complexit%C3%A9_pour_un_solveur_de_type_dissections_embo%C3%AEt%C3%A9es._(Algorithmic_study_and_complexity_bounds_for_a_nested_dissection_solver)"}}}}}