{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:36:35Z","timestamp":1750307795820,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,3,1]],"date-time":"2008-03-01T00:00:00Z","timestamp":1204329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["2002261"],"award-info":[{"award-number":["2002261"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004316","name":"International Business Machines Corporation","doi-asserted-by":"publisher","award":["572\/00848\/04"],"award-info":[{"award-number":["572\/00848\/04"]}],"id":[{"id":"10.13039\/100004316","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2008,3]]},"abstract":"<jats:p>We present a new parallel sparse LU factorization algorithm and code. The algorithm uses a column-preordering partial-pivoting unsymmetric-pattern multifrontal approach. Our baseline sequential algorithm is based on UMFPACK 4, but is somewhat simpler and is often somewhat faster than UMFPACK version 4.0. Our parallel algorithm is designed for shared-memory machines with a small or moderate number of processors (we tested it on up to 32 processors). We experimentally compare our algorithm with SuperLU_MT, an existing shared-memory sparse LU factorization with partial pivoting. SuperLU_MT scales better than our new algorithm, but our algorithm is more reliable and is usually faster. More specifically, on matrices that are costly to factor, our algorithm is usually faster on up to 4 processors, and is usually faster on 8 and 16. We were not able to run SuperLU_MT on 32. The main contribution of this article is showing that the column-preordering partial-pivoting unsymmetric-pattern multifrontal approach, developed as a sequential algorithm by Davis in several recent versions of UMFPACK, can be effectively parallelized.<\/jats:p>","DOI":"10.1145\/1326548.1326550","type":"journal-article","created":{"date-parts":[[2008,3,19]],"date-time":"2008-03-19T12:58:50Z","timestamp":1205931530000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Parallel unsymmetric-pattern multifrontal sparse LU with column preordering"],"prefix":"10.1145","volume":"34","author":[{"given":"Haim","family":"Avron","sequence":"first","affiliation":[{"name":"Tel-Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gil","family":"Shklarski","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sivan","family":"Toledo","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,3,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479800375370"},{"key":"e_1_2_1_2_1","unstructured":"Anderson E. Bai Z. Bischof C. Demmel J. Dongarra J. Croz J. D. Greenbaum A. Hammarling S. McKenney A. Ostrouchov S. and Sorensen D. 1994. LAPACK User's Guide 2nd ed. SIAM Philadelphia PA. Also available online from http:\/\/www.netlib.org.   Anderson E. Bai Z. Bischof C. Demmel J. Dongarra J. Croz J. D. Greenbaum A. Hammarling S. McKenney A. Ostrouchov S. and Sorensen D. 1994. LAPACK User's Guide 2nd ed. SIAM Philadelphia PA. Also available online from http:\/\/www.netlib.org."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/76909.76910"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801385037"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/992200.992205"},{"key":"e_1_2_1_7_1","volume-title":"Tech. Rep. TR-91-023, Department of Computer and Information Science and Engineering","author":"Davis T. A.","year":"1991","unstructured":"Davis , T. A. and Duff , I. S . 1991 . Unsymmetric-pattern multifrontal methods for parallel sparse LU factorization. Tech. Rep. TR-91-023, Department of Computer and Information Science and Engineering , University of Florida . Jan. Davis, T. A. and Duff, I. S. 1991. Unsymmetric-pattern multifrontal methods for parallel sparse LU factorization. Tech. Rep. TR-91-023, Department of Computer and Information Science and Engineering, University of Florida. Jan."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479894246905"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/305658.287640"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024080"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024079"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479895291765"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479897317685"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479897317685"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/77626.79170"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/356044.356047"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0914016"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/277652.277725"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0908072"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021943902025"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0613024"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Gilbert J. R. and Ng E. 1993. Predicting structure in nonsymmetric sparse matrix factorizations. In Graph Theory and Sparse Matrix Computation A. George J. R. Gilbert and J. W. H. Liu Eds. Springer-Verlag.  Gilbert J. R. and Ng E. 1993. Predicting structure in nonsymmetric sparse matrix factorizations. In Graph Theory and Sparse Matrix Computation A. George J. R. Gilbert and J. W. H. Liu Eds. Springer-Verlag.","DOI":"10.2172\/6987948"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0909058"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0909058"},{"volume-title":"Sparse Matrix Symposium 1982: Program and Abstracts","author":"Gilbert J. R.","key":"e_1_2_1_27_1","unstructured":"Gilbert , J. R. and Schreiber , R . 1982. Nested dissection with partial pivoting . In Sparse Matrix Symposium 1982: Program and Abstracts . Fairfield Glade, Tennessee, 61. Gilbert, J. R. and Schreiber, R. 1982. Nested dissection with partial pivoting. In Sparse Matrix Symposium 1982: Program and Abstracts. Fairfield Glade, Tennessee, 61."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024077"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089547980139604X"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/569147.569149"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2003.07.007"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/779359.779361"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0611010"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0614019"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0914063"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/114697.116809"},{"key":"e_1_2_1_37_1","first-page":"81","article-title":"Locality of reference in sparse Cholesky methods","volume":"21","author":"Rozin E.","year":"2005","unstructured":"Rozin , E. and Toledo , S. 2005 . Locality of reference in sparse Cholesky methods . Electr. Trans. Numer. Anal. 21 , 81 -- 106 . Rozin, E. and Toledo, S. 2005. Locality of reference in sparse Cholesky methods. Electr. Trans. Numer. Anal. 21, 81--106.","journal-title":"Electr. Trans. Numer. Anal."},{"key":"e_1_2_1_38_1","volume-title":"MIT Laboratory for Computer Science","author":"Supercomputing Technologies Group","year":"2001","unstructured":"Supercomputing Technologies Group , MIT Laboratory for Computer Science 2001 . Cilk-5.3.2 Reference Manual. Supercomputing Technologies Group , MIT Laboratory for Computer Science, Cambridge, MA. Available online at http:\/\/supertech.lcs.mit.edu\/cilk. Supercomputing Technologies Group, MIT Laboratory for Computer Science 2001. Cilk-5.3.2 Reference Manual. Supercomputing Technologies Group, MIT Laboratory for Computer Science, Cambridge, MA. Available online at http:\/\/supertech.lcs.mit.edu\/cilk."}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1326548.1326550","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1326548.1326550","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:56:25Z","timestamp":1750254985000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1326548.1326550"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,3]]}},"alternative-id":["10.1145\/1326548.1326550"],"URL":"https:\/\/doi.org\/10.1145\/1326548.1326550","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2008,3]]},"assertion":[{"value":"2004-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-03-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}