{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:32:48Z","timestamp":1787319168583,"version":"3.56.0"},"reference-count":35,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[1993,7]]},"abstract":"<jats:p>A parallel algorithm is presented for the LU decomposition of a general sparse matrix on a distributed-memory MIMD multiprocessor with a square mesh communication network. In the algorithm, matrix elements are assigned to processors according to the grid distribution. Each processor represents the nonzero elements of its part of the matrix by a local, ordered, two-dimensional linked-list data structure. The complexity of important operations on this data structure and on several others is analysed. At each step of the algorithm, a parallel search for a set of m compatible pivot elements is performed. The Markowitz counts of the pivot elements are close to minimum, to preserve the sparsity of the matrix. The pivot elements also satisfy a threshold criterion, to ensure numerical stability. The compatibility of the m pivots enables the simultaneous elimination of m pivot rows and m pivot columns in a rank-m update of the reduced matrix. Experimental results on a network of 400 transputers are presented for a set of test matrices from the Harwell\u2013Boeing sparse matrix collection.<\/jats:p>","DOI":"10.1137\/0614059","type":"journal-article","created":{"date-parts":[[2005,2,27]],"date-time":"2005-02-27T07:14:21Z","timestamp":1109488461000},"page":"853-879","source":"Crossref","is-referenced-by-count":23,"title":["Parallel Sparse LU Decomposition on a Mesh Network of Transputers"],"prefix":"10.1137","volume":"14","author":[{"given":"A. Frank","family":"van der Stappen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rob H.","family":"Bisseling","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Johannes G.G.","family":"van de Vorst","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,17]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(89)90029-X"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/0912041"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"R. H. Bisseling, J. G. G. van de Vorst,  Parallel  LU decomposition on a transputer network,  Lecture Notes in Computer Science 384, Vol. 384, Springer-Verlag, New York,  1989,  61\u201377","DOI":"10.1007\/3-540-51604-2_5"},{"key":"R4","volume-title":"Programming in occam 2","author":"Burns A.","year":"1988"},{"key":"R5","unstructured":"D. A. Calahan,  Parallel solution of sparse simultaneous linear equations,  Proc. 11th Annual Allerton Conf. on Circuits and System Theory,  1973,  729\u2013735"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(87)90007-X"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1093\/imamat\/8.3.344"},{"key":"R8","unstructured":"T. A. Davis,  A parallel algorithm for sparse unsymmetric  LU factorization, Ph. D. thesis, Tech. Rep., 907, Center for Supercomputing Research and Development, Univ, of Illinois, Urbana, IL,  1989, Sept."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/0611028"},{"key":"R10","volume-title":"A discipline of programming","author":"Dijkstra Edsger W.","year":"1976"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1145\/355815.355817"},{"key":"R12","volume-title":"Direct methods for sparse matrices","author":"Duff I. S.","year":"1986"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/62038.62043"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/0908054"},{"key":"R15","volume-title":"Solving Problems on Concurrent Processors","author":"Fox G. C.","year":"1988"},{"key":"R16","unstructured":"K. A. Gallivan, B. A. Marsolf, H. A. G. Wijshoff,  MCSPARSE: A parallel sparse unsymmetric linear system solver, Tech. Rep., 1142, Center for Supercomputing Research and Development Univ. of Illinois, Urbana, IL,  1991, Aug."},{"key":"R17","unstructured":"K. Gallivan, A. Sameh, Z. Zlatev,  Parallel direct method codes for general sparse matrices, Tech. Rep., 1143, Center for Supercomputing Research and Development, Univ. of Illinois, Urbana, IL,  1991, Oct."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/0909042"},{"key":"R19","volume-title":"Matrix computations","author":"Golub Gene H.","year":"1989"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-8675-3_4"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/1033099"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(87)90002-5"},{"key":"R23","volume-title":"The Art of Computer Programming","author":"Knuth D. E.","year":"1973"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.3.3.255"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1109\/12.61043"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"P. Sadayappan, S. K. Rao,  Communication reduction for distributed sparse matrix factorization on a processor mesh,  Proc. Supercomputing '89, ACM Press, New York,  1989,  371\u2013379","DOI":"10.1145\/76263.76304"},{"key":"R27","unstructured":"M. K. Seager,  G. F. Carey,  A SLAP for the masses,  Parallel Supercomputing: Methods, Algorithms and Applications, John Wiley, Chichester, U.K.,  1989,  135\u2013155 0863.70012"},{"key":"R28","unstructured":"A. Skjellum, Ph.D. Thesis,  Concurrent dynamic simulation: Multicomputer algorithms research applied to ordinary differential-algebraic process systems in chemical engineering, California Institute of Technology, Pasadena, CA,  1990, May"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"D. Smart, J. White,  Reducing the parallel solution time of sparse circuit matrices using reordered Gaussian elimination and relaxation,  Proc. IEEE Internat. Symp. Circuits and Systems,  1988,  627\u2013630 0691.65011","DOI":"10.1109\/ISCAS.1988.15004"},{"key":"R30","unstructured":"A. F. van der Stappen, Masters Thesis,  Distributed data structures for sparse linear algebra, Master's thesis, Eindhoven Univ. of Technology, the Netherlands,  1988, June"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4330020102"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1007\/BF02915443"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1137\/0717003"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-017-1116-6"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-10874-2"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0614059","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:45:24Z","timestamp":1787316324000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0614059"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,7]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1993,7]]}},"alternative-id":["10.1137\/0614059"],"URL":"https:\/\/doi.org\/10.1137\/0614059","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,7]]}}}