ISBN:  Unavailable

Category: Unavailable

Page count: 18

Abstract: "This paper presents a new partitioned algorithm for LU decomposition with partial pivoting. The new algorithm, called the recursively-partitioned algorithm, is based on a recursive partitioning of the matrix. The paper analyzes the locality of reference in the new algorithm and the locality of reference in a known and widely used partitioned algorithm for LU decomposition called the right-looking algorithm. The analysis reveals that the new algorithm performs a factor of [theta]([square root ofM/n]) fewer I/O operations (or cache misses) than the right-looking algorithm, where n is the order of matrix and M is the size of primary memory. The analysis also determines the optimal block size for the right-looking alglrithm [sic]. Experimental comparisons between the new algorithm and the right-looking algorithm show that an implementation of the new algorithm outperforms a similarly coded right- looking algorithm on 6 different RISC architectures, that the new algorithm performs fewer cache misses than any other algorithm tested, and that it benefits more from Strassen's matrix-multiplication algorithm."