{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T21:44:40Z","timestamp":1791150280146,"version":"4.1.0"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2007,1]]},"abstract":"<jats:p>This paper presents the design and implementation of a memory scalable parallel symbolic factorization algorithm for general sparse unsymmetric matrices. Our parallel algorithm uses a graph partitioning approach, applied to the graph of $|A|+|A|^T$, to partition the matrix in such a way that is good for sparsity preservation as well as for parallel factorization. The partitioning yields a so-called separator tree which represents the dependencies among the computations. We use the separator tree to distribute the input matrix over the processors using a block cyclic approach and a subtree to subprocessor mapping. The parallel algorithm performs a bottom-up traversal of the separator tree. With a combination of right-looking and left-looking partial factorizations, the algorithm obtains one column structure of L and one row structure of U at each step. The algorithm is implemented in C and MPI. From a performance study on large matrices, we show that the parallel algorithm significantly reduces the memory requirement of the symbolic factorization step, as well as the overall memory requirement of the parallel solver. It also often reduces the runtime of the sequential algorithm, which is already relatively small. In general, the parallel algorithm prevents the symbolic factorization step from being a time or memory bottleneck of the parallel solver.<\/jats:p>","DOI":"10.1137\/050638102","type":"journal-article","created":{"date-parts":[[2007,6,4]],"date-time":"2007-06-04T10:06:37Z","timestamp":1180951597000},"page":"1289-1314","source":"Crossref","is-referenced-by-count":42,"title":["Parallel Symbolic Factorization for Sparse LU with Static Pivoting"],"prefix":"10.1137","volume":"29","author":[{"given":"Laura","family":"Grigori","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James W.","family":"Demmel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaoye S.","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2007,6,1]]},"reference":[{"key":"R1","unstructured":"T.Y. Chen, J. R. Gilbert, and S. Toledo,\n                      Toward an efficient column minimum degree code for symmetric multiprocessors\n                      , in Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing, SIAM, Philadelphia, 1999."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"M. Cosnard and L. Grigori,\n                      A parallel algorithm for sparse symbolic LU factorization without pivoting on out-of-core matrices\n                      , in Proceedings of the 15th International Conference on Supercomputing, ACM Press, New York, 2001, pp. 146\u2013153.","DOI":"10.1145\/377792.377823"},{"key":"R3","unstructured":"T. Davis,\n                      University of Florida Sparse Matrix Collection\n                      , NA Digest, vol. 92, no. 42, October 16, 1994, NA Digest, vol. 96, no. 28, July 23, 1996, and NA Digest, vol. 97, no. 23, June 7, 1997; http:\/\/www.cise.ufl.edu\/research\/sparse\/matrices."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479895291765"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479899358443"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/0613017"},{"key":"R7","unstructured":"A. George and J. W. H. Liu,\n                      Computer Solution of Large Sparse Positive Definite Systems\n                      , Prentice\u2013Hall, Englewood Cliffs, NJ, 1981."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(89)90101-4"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/0614024"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/S089547980139604X"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1109\/71.598277"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/0916028"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"B. Hendrickson and R. Leland,\n                      A multilevel algorithm for partitioning graphs\n                      , in Proceedings of SuperComputing '95, ACM Press, New York, 1995.","DOI":"10.1145\/224170.224228"},{"key":"R14","unstructured":"HSL,\n                      A Collection of Fortran Codes for Large-Scale Scientific Computation\n                      , http:\/\/www.cse. clrc.ac.uk\/nag\/hsl\/ (2004)."},{"key":"R15","unstructured":"M. Joshi, G. Karypis, V. Kumar, A. Gupta, and F. Gustavson,\n                      PSPASES: An efficient and scalable parallel sparse direct solver\n                      , in Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing, SIAM, Philadelphia, 1999."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1997.1403"},{"key":"R17","unstructured":"G. Karypis, K. Schloegel, and V. Kumar\n                      ,\n                      \n                        ParMe$\\!\n                        T\n                        \\!$iS\n                      \n                      : Parallel Graph Partitioning and Fill-Reducing Matrix Ordering, Version\n                      3.1, University of Minnesota, http:\/\/www-users. cs.umn.edu\/~karypis\/metis\/parmetis\/ (August 2003)."},{"key":"R18","unstructured":"K. Ko, N. Folwell, L. Ge, A. Guetz, V. Ivanov, L. Lee, Z. Li, I. Malik, W. Mi, C. Ng, and M. Wolf,\n                      Electromagnetic Systems Simulation\u2014From Simulation to Fabrication\n                      , sciDAC report, Stanford Linear Accelerator Center, Menlo Park, CA, 2003."},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/779359.779361"},{"key":"R20","unstructured":"J. Riedy and J. W. Demmel,\n                      Parallel Bipartite Matching for Sparse Matrix Computation\n                      , manuscript, University of California at Berkeley, Berkeley, CA."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/0134014"},{"key":"R22","unstructured":"A. van Heukelum,\n                      Symbolic Sparse Cholesky Factorization Using Elimination Trees\n                      , Master's thesis, Department of Mathematics, Utrecht University, Utrecht, The Netherlands, 1999."},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(88)90039-7"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/050638102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:57:38Z","timestamp":1787335058000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/050638102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["10.1137\/050638102"],"URL":"https:\/\/doi.org\/10.1137\/050638102","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1]]}}}