Efficient parallel algorithm for dense matrix LU decomposition with pivoting on hypercubes

Abstract

LU decomposition is intensively used in various scientific and engineering computations. A parallel algorithm for dense matrix LU decomposition with pivoting on hypercubes is presented. Using n processors, the presented algorithm can finish LU decomposition of an n x n matrix in O(n2/3 + O(n√nlog2 n)) steps, including computations as well as communications, and its efficiency is 1 asymptotically when n becomes large. The algorithm employs row-column-as well as block-parallelisms interchangeably so that the n processors are used efficiently in the whole computation process. Using the rich connectivity, all the data alignment requirements can be realized in O(log2 n) steps. The algorithm proposed here not only is suitable for systems with small numbers of processors, but also is suitable for systems with large numbers of processors.