$LU$ Factorization Algorithms on Distributed-Memory Multiprocessor Architectures
George A. Geist, Charles H. Romine · SIAM Journal on Scientific and Statistical Computing · 1988
In this paper, we consider the effect that the data-storage scheme and pivoting scheme have on the efficiency of $LU$ factorization on a distributed-memory multiprocessor. Our presentation will focus on the hypercube architecture, but most of our results are applicable to distributed-memory architectures in general. We restrict our attention to two commonly used storage schemes (storage by rows and by columns) and investigate partial pivoting both by rows and by columns, yielding four factorization algorithms. Our goal is to determine which of these four algorithms admits the most efficient parallel implementation. We analyze factors such as load distribution, pivoting cost, and potential for pipelining. We conclude that, in the absence of loop-unrolling, $LU$ factorization with partial pivoting is most efficient when pipelining is used to mask the cost of pivoting. The two schemes that can be pipelined are pivoting by interchanging rows when the coefficient matrix is distributed to the processors by columns, and pivoting by interchanging columns when the matrix is distributed to the processors by rows.
Cited by 87 works. doi:10.1137/0909042
Authors
References
- Implementing Linear Algebra Algorithms for Dense Matrices on a Vector Pipeline Machine
- Solution of Partial Differential Equations on Vector and Parallel Computers
- Parallel Solution of Triangular Systems on Distributed-Memory Multiprocessors
- Parallel solution of triangular systems of equations
- Gaussian elimination with partial pivoting and load balancing on a multiprocessor
- Implementing Dense Linear Algebra Algorithms Using Multitasking on the CRAY X-MP-4 (or Approaching the Gigaflop)
- The ijk forms of factorization methods II. Parallel systems
- Column LU Factorization with Pivoting on a Message-Passing Multiprocessor
- A New Variant of Gaussian Elimination