{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T07:05:19Z","timestamp":1761807919612,"version":"3.37.3"},"reference-count":30,"publisher":"Wiley","license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"funder":[{"name":"Polish National Science Center","award":["DEC-2012\/07\/B\/ST6\/01229","DEC-2011\/03\/B\/ST6\/01393","DEC-2012\/06\/M\/ST1\/00363","CCF 1337281","CCF 1218568","ACI 1216701","CNS 1064956"],"award-info":[{"award-number":["DEC-2012\/07\/B\/ST6\/01229","DEC-2011\/03\/B\/ST6\/01393","DEC-2012\/06\/M\/ST1\/00363","CCF 1337281","CCF 1218568","ACI 1216701","CNS 1064956"]}]},{"name":"Polish National Science Center","award":["DEC-2012\/07\/B\/ST6\/01229","DEC-2011\/03\/B\/ST6\/01393","DEC-2012\/06\/M\/ST1\/00363","CCF 1337281","CCF 1218568","ACI 1216701","CNS 1064956"],"award-info":[{"award-number":["DEC-2012\/07\/B\/ST6\/01229","DEC-2011\/03\/B\/ST6\/01393","DEC-2012\/06\/M\/ST1\/00363","CCF 1337281","CCF 1218568","ACI 1216701","CNS 1064956"]}]},{"name":"Polish National Science Center","award":["DEC-2012\/07\/B\/ST6\/01229","DEC-2011\/03\/B\/ST6\/01393","DEC-2012\/06\/M\/ST1\/00363","CCF 1337281","CCF 1218568","ACI 1216701","CNS 1064956"],"award-info":[{"award-number":["DEC-2012\/07\/B\/ST6\/01229","DEC-2011\/03\/B\/ST6\/01393","DEC-2012\/06\/M\/ST1\/00363","CCF 1337281","CCF 1218568","ACI 1216701","CNS 1064956"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DEC-2012\/07\/B\/ST6\/01229","DEC-2011\/03\/B\/ST6\/01393","DEC-2012\/06\/M\/ST1\/00363","CCF 1337281","CCF 1218568","ACI 1216701","CNS 1064956"],"award-info":[{"award-number":["DEC-2012\/07\/B\/ST6\/01229","DEC-2011\/03\/B\/ST6\/01393","DEC-2012\/06\/M\/ST1\/00363","CCF 1337281","CCF 1218568","ACI 1216701","CNS 1064956"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DEC-2012\/07\/B\/ST6\/01229","DEC-2011\/03\/B\/ST6\/01393","DEC-2012\/06\/M\/ST1\/00363","CCF 1337281","CCF 1218568","ACI 1216701","CNS 1064956"],"award-info":[{"award-number":["DEC-2012\/07\/B\/ST6\/01229","DEC-2011\/03\/B\/ST6\/01393","DEC-2012\/06\/M\/ST1\/00363","CCF 1337281","CCF 1218568","ACI 1216701","CNS 1064956"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DEC-2012\/07\/B\/ST6\/01229","DEC-2011\/03\/B\/ST6\/01393","DEC-2012\/06\/M\/ST1\/00363","CCF 1337281","CCF 1218568","ACI 1216701","CNS 1064956"],"award-info":[{"award-number":["DEC-2012\/07\/B\/ST6\/01229","DEC-2011\/03\/B\/ST6\/01393","DEC-2012\/06\/M\/ST1\/00363","CCF 1337281","CCF 1218568","ACI 1216701","CNS 1064956"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DEC-2012\/07\/B\/ST6\/01229","DEC-2011\/03\/B\/ST6\/01393","DEC-2012\/06\/M\/ST1\/00363","CCF 1337281","CCF 1218568","ACI 1216701","CNS 1064956"],"award-info":[{"award-number":["DEC-2012\/07\/B\/ST6\/01229","DEC-2011\/03\/B\/ST6\/01393","DEC-2012\/06\/M\/ST1\/00363","CCF 1337281","CCF 1218568","ACI 1216701","CNS 1064956"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DEC-2012\/07\/B\/ST6\/01229","DEC-2011\/03\/B\/ST6\/01393","DEC-2012\/06\/M\/ST1\/00363","CCF 1337281","CCF 1218568","ACI 1216701","CNS 1064956"],"award-info":[{"award-number":["DEC-2012\/07\/B\/ST6\/01229","DEC-2011\/03\/B\/ST6\/01393","DEC-2012\/06\/M\/ST1\/00363","CCF 1337281","CCF 1218568","ACI 1216701","CNS 1064956"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004052","name":"King Abdullah University of Science and Technology","doi-asserted-by":"publisher","award":["DEC-2012\/07\/B\/ST6\/01229","DEC-2011\/03\/B\/ST6\/01393","DEC-2012\/06\/M\/ST1\/00363","CCF 1337281","CCF 1218568","ACI 1216701","CNS 1064956"],"award-info":[{"award-number":["DEC-2012\/07\/B\/ST6\/01229","DEC-2011\/03\/B\/ST6\/01393","DEC-2012\/06\/M\/ST1\/00363","CCF 1337281","CCF 1218568","ACI 1216701","CNS 1064956"]}],"id":[{"id":"10.13039\/501100004052","id-type":"DOI","asserted-by":"publisher"}]},{"name":"J. T. Oden Research Faculty Fellowship","award":["DEC-2012\/07\/B\/ST6\/01229","DEC-2011\/03\/B\/ST6\/01393","DEC-2012\/06\/M\/ST1\/00363","CCF 1337281","CCF 1218568","ACI 1216701","CNS 1064956"],"award-info":[{"award-number":["DEC-2012\/07\/B\/ST6\/01229","DEC-2011\/03\/B\/ST6\/01393","DEC-2012\/06\/M\/ST1\/00363","CCF 1337281","CCF 1218568","ACI 1216701","CNS 1064956"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Scientific Programming"],"published-print":{"date-parts":[[2015]]},"abstract":"<jats:p>We construct quasi-optimal elimination trees for 2D finite element meshes with singularities. These trees minimize the complexity of the solution of the discrete system. The computational cost estimates of the elimination process model the execution of the multifrontal algorithms in serial and in parallel shared-memory executions. Since the meshes considered are a subspace of all possible mesh partitions, we call these minimizers quasi-optimal. We minimize the cost functionals using dynamic programming. Finding these minimizers is more computationally expensive than solving the original algebraic system. Nevertheless, from the insights provided by the analysis of the dynamic programming minima, we propose a heuristic construction of the elimination trees that has cost<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M1\"><mml:mi mathvariant=\"script\">O<\/mml:mi><mml:mfenced separators=\"|\"><mml:mrow><mml:msub><mml:mrow><mml:mi>N<\/mml:mi><\/mml:mrow><mml:mrow><mml:mi>e<\/mml:mi><\/mml:mrow><\/mml:msub><mml:mrow><mml:mrow><mml:mi mathvariant=\"normal\">log<\/mml:mi><\/mml:mrow><mml:mo>\u2061<\/mml:mo><mml:mrow><mml:mfenced separators=\"|\"><mml:mrow><mml:msub><mml:mrow><mml:mi>N<\/mml:mi><\/mml:mrow><mml:mrow><mml:mi>e<\/mml:mi><\/mml:mrow><\/mml:msub><\/mml:mrow><\/mml:mfenced><\/mml:mrow><\/mml:mrow><\/mml:mrow><\/mml:mfenced><\/mml:math>, where<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M2\"><mml:mrow><mml:msub><mml:mrow><mml:mi>N<\/mml:mi><\/mml:mrow><mml:mrow><mml:mi>e<\/mml:mi><\/mml:mrow><\/mml:msub><\/mml:mrow><\/mml:math>is the number of elements in the mesh. We show that this heuristic ordering has similar computational cost to the quasi-optimal elimination trees found with dynamic programming and outperforms state-of-the-art alternatives in our numerical experiments.<\/jats:p>","DOI":"10.1155\/2015\/303024","type":"journal-article","created":{"date-parts":[[2015,3,10]],"date-time":"2015-03-10T21:33:34Z","timestamp":1426023214000},"page":"1-18","source":"Crossref","is-referenced-by-count":12,"title":["Quasi-Optimal Elimination Trees for 2D Grids with Singularities"],"prefix":"10.1155","volume":"2015","author":[{"given":"A.","family":"Paszy\u0144ska","sequence":"first","affiliation":[{"name":"Jagiellonian University, 31007 Krakow, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Paszy\u0144ski","sequence":"additional","affiliation":[{"name":"AGH University of Science and Technology, 30059 Krakow, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K.","family":"Jopek","sequence":"additional","affiliation":[{"name":"AGH University of Science and Technology, 30059 Krakow, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Wo\u017aniak","sequence":"additional","affiliation":[{"name":"AGH University of Science and Technology, 30059 Krakow, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Goik","sequence":"additional","affiliation":[{"name":"AGH University of Science and Technology, 30059 Krakow, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Gurgul","sequence":"additional","affiliation":[{"name":"AGH University of Science and Technology, 30059 Krakow, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H.","family":"AbouEisha","sequence":"additional","affiliation":[{"name":"Applied Mathematics & Computational Science, King Abdullah University of Science and Technology (KAUST), Thuwal 23955-6900, Saudi Arabia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Moshkov","sequence":"additional","affiliation":[{"name":"Applied Mathematics & Computational Science, King Abdullah University of Science and Technology (KAUST), Thuwal 23955-6900, Saudi Arabia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V. M.","family":"Calo","sequence":"additional","affiliation":[{"name":"Applied Mathematics & Computational Science, King Abdullah University of Science and Technology (KAUST), Thuwal 23955-6900, Saudi Arabia"},{"name":"Earth Science & Engineering and Center for Numerical Porous Media, King Abdullah University of Science and Technology (KAUST), Thuwal 23955-6900, Saudi Arabia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Lenharth","sequence":"additional","affiliation":[{"name":"Institute for Computational Engineering and Science, University of Texas, Austin, TX 78712-1229, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Nguyen","sequence":"additional","affiliation":[{"name":"Institute for Computational Engineering and Science, University of Texas, Austin, TX 78712-1229, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K.","family":"Pingali","sequence":"additional","affiliation":[{"name":"Institute for Computational Engineering and Science, University of Texas, Austin, TX 78712-1229, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","reference":[{"key":"33","doi-asserted-by":"publisher","DOI":"10.1137\/0602010"},{"year":"2006","series-title":"Applied Mathematics and Nonlinear Science","key":"7"},{"key":"10","doi-asserted-by":"publisher","DOI":"10.1145\/356044.356047"},{"key":"11","doi-asserted-by":"publisher","DOI":"10.1137\/0905045"},{"key":"18","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1620020104"},{"key":"19","doi-asserted-by":"publisher","DOI":"10.1137\/s1064827595287997"},{"key":"2","doi-asserted-by":"publisher","DOI":"10.1137\/s0895479894278952"},{"key":"3","doi-asserted-by":"publisher","DOI":"10.1016\/s0045-7825(99)00242-x"},{"key":"4","doi-asserted-by":"publisher","DOI":"10.1137\/s0895479899358194"},{"issue":"32","key":"5","first-page":"136","volume":"2","year":"2001","journal-title":"Computer Methods in Applied Mechanics and Engineering"},{"key":"26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01973-9_97"},{"key":"27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69389-5_68"},{"key":"28","doi-asserted-by":"publisher","DOI":"10.3233\/fi-2009-111"},{"issue":"4","key":"29","doi-asserted-by":"crossref","first-page":"435","DOI":"10.3233\/FI-2009-112","volume":"93","year":"2009","journal-title":"Fundamenta Informaticae"},{"issue":"1","key":"23","doi-asserted-by":"crossref","first-page":"1993","DOI":"10.1016\/j.procs.2010.04.223","volume":"1","year":"2010","journal-title":"Procedia Computer Science"},{"key":"30","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.1533"},{"issue":"2","key":"15","first-page":"149","volume":"2","year":"1993","journal-title":"Machine Graphics and Vision"},{"key":"16","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-18771-5_41"},{"key":"17","doi-asserted-by":"publisher","DOI":"10.1007\/bfb0039608"},{"key":"32","first-page":"1545","volume":"18","year":"2012","journal-title":"Procedia Computer Science"},{"key":"9","doi-asserted-by":"publisher","DOI":"10.1142\/9789814261456"},{"key":"14","doi-asserted-by":"crossref","first-page":"1090","DOI":"10.1016\/j.procs.2014.05.098","volume":"29","year":"2014","journal-title":"Procedia Computer Science"},{"key":"25","doi-asserted-by":"publisher","DOI":"10.1016\/j.jocs.2010.03.002"},{"key":"6","doi-asserted-by":"publisher","DOI":"10.2478\/amcs-2014-0064"},{"key":"12","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-014-9440-y"},{"key":"24","doi-asserted-by":"publisher","DOI":"10.1137\/050631732"},{"key":"8","doi-asserted-by":"publisher","DOI":"10.1016\/j.cma.2011.02.001"},{"key":"22","doi-asserted-by":"publisher","DOI":"10.1016\/j.cma.2008.05.027"},{"key":"1","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2014.05.085"},{"key":"13","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2014.05.086"}],"container-title":["Scientific Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/sp\/2015\/303024.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/sp\/2015\/303024.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/sp\/2015\/303024.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,30]],"date-time":"2020-08-30T17:44:16Z","timestamp":1598809456000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.hindawi.com\/journals\/sp\/2015\/303024\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"references-count":30,"alternative-id":["303024","303024"],"URL":"https:\/\/doi.org\/10.1155\/2015\/303024","relation":{},"ISSN":["1058-9244","1875-919X"],"issn-type":[{"type":"print","value":"1058-9244"},{"type":"electronic","value":"1875-919X"}],"subject":[],"published":{"date-parts":[[2015]]}}}