{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T18:53:23Z","timestamp":1774637603952,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2025,8,1]]},"abstract":"<jats:p>We introduce Parth, a fill-reducing ordering method for sparse Cholesky solvers with dynamic sparsity patterns (e.g., in physics simulations with contact or geometry processing with local remeshing). Parth facilitates the selective reuse of fill-reducing orderings when sparsity patterns exhibit temporal coherence, avoiding full symbolic analysis by localizing the effect of dynamic sparsity changes on the ordering vector. We evaluated Parth on over 175,000 linear systems collected from both physics simulations and geometry processing applications, and show that for some of the most challenging physics simulations, it achieves up to 14x reordering runtime speedup, resulting in a 2x speedup in Cholesky solve time\u2014even on top of well-optimized solvers such as Apple Accelerate and Intel MKL.<\/jats:p>","DOI":"10.1145\/3731179","type":"journal-article","created":{"date-parts":[[2025,7,27]],"date-time":"2025-07-27T04:02:22Z","timestamp":1753588942000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Adaptive Algebraic Reuse of Reordering in Cholesky Factorizations with Dynamic Sparsity Patterns"],"prefix":"10.1145","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2060-9596","authenticated-orcid":false,"given":"Behrooz","family":"Zarebavani","sequence":"first","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-2864-2089","authenticated-orcid":false,"given":"Danny","family":"M. Kaufman","sequence":"additional","affiliation":[{"name":"Adobe Research, Seattle, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7079-1934","authenticated-orcid":false,"given":"David","family":"I. W. Levin","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2719-8788","authenticated-orcid":false,"given":"Maryam","family":"Mehri Dehnavi","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}]}],"member":"320","published-online":{"date-parts":[[2025,7,27]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"2020. IPC. https:\/\/github.com\/ipc\/ipc-sim GitHub repository."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1465482.1465560"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024081"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1057432.1057457"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391989.1391995"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3126908.3126936"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2018.00065"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2018.00065"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392486"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3581784.3607097"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089547980343641X"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492916000076"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/77626.79170"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3272127.3275107"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417828"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3643028"},{"key":"e_1_2_2_17_1","unstructured":"Apple Inc. 2023. Accelerate Framework. Available at https:\/\/developer.apple.com\/documentation\/accelerate."},{"key":"e_1_2_2_18_1","unstructured":"Alec Jacobson Daniele Panozzo et al. 2024. Libigl Tutorial - Laplace Equation. https:\/\/libigl.github.io\/tutorial\/#laplace-equation. Accessed: 2024-10-18."},{"key":"e_1_2_2_19_1","volume-title":"METIS: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices.","author":"Karypis George","year":"1997","unstructured":"George Karypis and Vipin Kumar. 1997. METIS: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. (1997)."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3478513.3480505"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392425"},{"key":"e_1_2_2_22_1","series-title":"SIAM journal on matrix analysis and applications 11, 1","volume-title":"The role of elimination trees in sparse factorization","author":"Liu Joseph WH","year":"1990","unstructured":"Joseph WH Liu. 1990. The role of elimination trees in sparse factorization. SIAM journal on matrix analysis and applications 11, 1 (1990), 134\u2013172."},{"key":"e_1_2_2_23_1","volume-title":"Dagstuhl Seminar Proceedings. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik.","author":"Pellegrini Fran\u00e7ois","year":"2009","unstructured":"Fran\u00e7ois Pellegrini. 2009. Distillating knowledge about Scotch. In Dagstuhl Seminar Proceedings. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2016.06.004"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/514474.514480"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14747"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417778"},{"key":"e_1_2_2_28_1","unstructured":"Oded Stein. 2024. odedstein-meshes: A Computer Graphics Example Mesh Repository. (2024)."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0602010"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS53621.2022.00121"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3731179","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T17:51:46Z","timestamp":1774633906000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3731179"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,27]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8,1]]}},"alternative-id":["10.1145\/3731179"],"URL":"https:\/\/doi.org\/10.1145\/3731179","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,27]]},"assertion":[{"value":"2025-07-27","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}