{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:27:57Z","timestamp":1760239677023,"version":"build-2065373602"},"reference-count":37,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2020,12,13]],"date-time":"2020-12-13T00:00:00Z","timestamp":1607817600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004442","name":"National Science Centre, Poland","doi-asserted-by":"publisher","award":["2017\/26\/M\/ ST1\/ 00281"],"award-info":[{"award-number":["2017\/26\/M\/ ST1\/ 00281"]}],"id":[{"id":"10.13039\/501100004442","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>In this paper, we consider the computational cost of a multi-frontal direct solver used for the factorization of matrices resulting from a discretization of isogeometric analysis with T-splines, and analysis-suitable T-splines. We start from model projection or model heat transfer problems discretized over two-dimensional meshes, either uniformly refined or refined towards a point or an edge. These grids preserve several symmetries and they are the building blocks of more complicated grids constructed during adaptive isotropic refinement procedures. A large class of computational problems construct meshes refined towards point or edge singularities. We propose an ordering that permutes the matrix in a way that the computational cost of a multi-frontal solver executed on adaptive grids is linear. We show that analysis-suitable T-splines with our ordering, besides having other well-known advantages, also significantly reduce the computational cost of factorization with the multi-frontal direct solver. Namely, the factorization with N T-splines of order p over meshes refined to a point has a linear O(Np4) cost, and the factorization with T-splines on meshes refined to an edge has O(N2pp2) cost. We compare the execution time of the multi-frontal solver with our ordering to the Approximate Minimum Degree (AMD) and Cuthill\u2013McKee orderings available in Octave.<\/jats:p>","DOI":"10.3390\/sym12122070","type":"journal-article","created":{"date-parts":[[2020,12,14]],"date-time":"2020-12-14T00:45:36Z","timestamp":1607906736000},"page":"2070","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Computational Costs of Multi-Frontal Direct Solvers with Analysis-Suitable T-Splines"],"prefix":"10.3390","volume":"12","author":[{"given":"Anna","family":"Paszy\u0144ska","sequence":"first","affiliation":[{"name":"Faculty of Physics, Astronomy and Applied Computer Science, Jagiellonian University, Ul. Prof. Stanis\u0142awa \u0141ojasiewicza 11, 30-348 Krak\u00f3w, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maciej","family":"Paszy\u0144ski","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Faculty of Computer Science, Electronics and Telecommunication, AGH University of Science and Technology, Al. Mickiewicza 30, 30-059 Krak\u00f3w, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,12,13]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Cottrell, A., Hughes, T.J.R., and Bazilevs, Y. (2009). Isogeometric Analysis: Toward Unification of CAD and FEA, John Wiley and Sons.","DOI":"10.1002\/9780470749081"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/j.cma.2009.02.036","article-title":"Isogeometric analysis using T-splines","volume":"199","author":"Bazilevs","year":"2010","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"584","DOI":"10.1016\/j.cma.2012.06.023","article-title":"A subdivision-based implementation of the hierarchical B-spline finite element method","volume":"253","author":"Bornemann","year":"2013","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1016\/j.cagd.2012.03.025","article-title":"THB-splines: The truncated basis for hierarchical splines","volume":"29","author":"Giannelli","year":"2012","journal-title":"Comput. Aided Geom. Des."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/j.cagd.2012.12.005","article-title":"Polynomial splines over locally refined box-partitions","volume":"30","author":"Dokken","year":"2013","journal-title":"Comput. Aided Geom. Des."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1016\/j.cma.2013.09.014","article-title":"Isogeometric analysis using LR B-splines","volume":"269","author":"Johannessen","year":"2014","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1575","DOI":"10.1111\/j.1467-8659.2010.01766.x","article-title":"Iso-geometric Finite Element Analysis Based on Catmull-Clark: Subdivision Solids","volume":"29","author":"Burkhart","year":"2010","journal-title":"Comput. Graph. Forum"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.cma.2015.03.019","article-title":"Truncated hierarchical Catmull-Clark subdivision with local refinement","volume":"291","author":"Wei","year":"2015","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1016\/j.cma.2015.10.024","article-title":"Extended Truncated hierarchical Catmull-Clark subdivision with local refinement","volume":"299","author":"Wei","year":"2016","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1016\/j.cma.2019.04.036","article-title":"Hybrid non-uniform recursive subdivision with improved convergence rates","volume":"352","author":"Li","year":"2019","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1016\/S0045-7825(99)00242-X","article-title":"Multifrontal parallel distributed symmetric and unsymmetric solvers","volume":"184","author":"Amestoy","year":"2000","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1137\/S0895479899358194","article-title":"A fully asynchronous multifrontal solver using distributed dynamic scheduling","volume":"1","author":"Amestoy","year":"2001","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_13","first-page":"136","article-title":"Hybrid scheduling for the parallel solution of linear systems","volume":"2","author":"Amestoy","year":"2001","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1016\/j.cma.2011.11.002","article-title":"The cost of continuity: A study on performance of isogeometric finite elements using direct solvers","volume":"213\u2013216","author":"Collier","year":"2012","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1016\/j.camwa.2015.05.007","article-title":"Direct solvers performance on h-adapted grids","volume":"70","author":"Pardo","year":"2015","journal-title":"Comput. Math. Appl."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1016\/j.cma.2016.08.017","article-title":"The value of continuity: Refined isogeometric analysis and fast direct solvers","volume":"316","author":"Garcia","year":"2017","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Heggernes, P., Eisenstat, S.C., Kumfert, G., and Pothen, A. (2001). The Computational Complexity of the Minimum Degree Algorithm, Institute for Computer Applications in Science and Engineering. ICASE Report No. 2001\u201342.","DOI":"10.2172\/15002765"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"800","DOI":"10.1023\/A:1021908421589","article-title":"Toward a tighter coupling of bottom-up and top-down sparse matrix ordering methods","volume":"41","author":"Schulze","year":"2001","journal-title":"BIT"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S1064827595287997","article-title":"A fast and high quality multilevel scheme for partitioning irregular graphs","volume":"20","author":"Karypis","year":"1998","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1137\/1034004","article-title":"The multifrontal method for sparse matrix solution: Theory and practice","volume":"34","author":"Liu","year":"1992","journal-title":"SIAM Rev."},{"key":"ref_21","first-page":"303024","article-title":"Quasi-optimal elimination trees for 2D grids with singularities","volume":"2015","author":"Jopek","year":"2015","journal-title":"Sci. Program."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1467","DOI":"10.1016\/j.camwa.2014.09.012","article-title":"Volume and neighbors algorithm for finding elimination trees for three dimensional h-adaptive grds","volume":"68","year":"2014","journal-title":"Comput. Math. Appl."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1016\/j.procs.2014.05.085","article-title":"Dynamic programming algorithm for generation of optimal elimination trees for multi-frontal direct solver over h-refined grids","volume":"29","author":"AbouEisha","year":"2014","journal-title":"Procedia Comput. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1515\/amcs-2017-0025","article-title":"Element partition trees for h-refined meshes to optimize direct solver performance. Part 1, Dynamic programming","volume":"27","author":"AbouEisha","year":"2017","journal-title":"Int. J. Appl. Math. Comput. Sci."},{"key":"ref_25","unstructured":"Balay, S., Abhyankar, S., Adams, M.F., Brown, J., Brune, P., Buschelman, K., Eijkhout, V., Gropp, W.D., Kaushik, D., and Knepley, M.G. (2020, October 12). PETSc Web Page, Available online: http:\/\/www.mcs.anl.gov\/petsc."},{"key":"ref_26","unstructured":"Blackford, L.S., Choi, J., Cleary, A., D\u2019Azevedo, E., Demmel, J., Dhillon, I., Dongarra, J., Hammarling, S., Henry, S., and Petitet, A. (1999). ScaLAPACK Users\u2019 Guide, Society for Industrial and Applied Mathematics."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/S0167-8191(01)00141-7","article-title":"PaStiX: A High-Performance Parallel Direct Solver for Sparse Symmetric Definite Systems","volume":"28","author":"Hnon","year":"2002","journal-title":"Parallel Comput."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1145\/1089014.1089017","article-title":"An Overview of SuperLU: Algorithms, Implementation, and User Interface","volume":"31","year":"2005","journal-title":"Trans. Math. Softw."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1090","DOI":"10.1016\/j.procs.2014.05.098","article-title":"A Linear Complexity Direct Solver for H-adaptive Grids with Point Singularities","volume":"29","author":"Gurgul","year":"2014","journal-title":"Procedia Comput. Sci."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1979","DOI":"10.1142\/S0218202513500231","article-title":"Analysis-suitable T-splines of arbitrary degree: Definition and properties","volume":"23","author":"Buffa","year":"2013","journal-title":"Math. Models Methods Appl. Sci."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1854","DOI":"10.1016\/j.procs.2011.04.201","article-title":"Computational complexity and memory usage for multi-frontal direct solvers used in p finite element analysis","volume":"4","author":"Calo","year":"2011","journal-title":"Procedia Comput. Sci."},{"key":"ref_32","first-page":"226","article-title":"Computational Complexity of Hierarchically Adapted Meshes","volume":"Volume 12139","author":"Skotniczny","year":"2020","journal-title":"Computational Science\u2014ICCS 2020, Proceedings of the 20th International Conference, Amsterdam, The Netherlands, 3\u20135 June 2020"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"4333","DOI":"10.1016\/j.cma.2008.05.003","article-title":"Isogeometric analysis of the Cahn-Hilliard phase-field model","volume":"197","author":"Gomez","year":"2008","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1828","DOI":"10.1016\/j.cma.2010.02.010","article-title":"Isogeometric analysis of the isothermal Navier-Stokes-Korteweg equations","volume":"199","author":"Gomez","year":"2010","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.compfluid.2011.05.002","article-title":"High-performance computing of wind turbine aerodynamics using isogeometric analysis","volume":"49","author":"Hsu","year":"2011","journal-title":"Comput. Fluids"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1002\/nme.3262","article-title":"A finite strain Eulerian formulation for compressible and nearly incompressible hyper-elasticity using high-order NURBS elements","volume":"89","author":"Duddu","year":"2012","journal-title":"Int. J. Numer. Methods Eng."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/s00466-008-0321-z","article-title":"Multiphysics Model for Blood Flow and Drug Transport with Application to Patient-Specific Coronary Artery Flow","volume":"43","author":"Calo","year":"2008","journal-title":"Comput. Mech."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/12\/12\/2070\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:44:35Z","timestamp":1760179475000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/12\/12\/2070"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,13]]},"references-count":37,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2020,12]]}},"alternative-id":["sym12122070"],"URL":"https:\/\/doi.org\/10.3390\/sym12122070","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2020,12,13]]}}}