An LU factorization algorithm for parallel supercomputers with memory hierarchies

A parallel algorithm for solving LU factorization of huge dense matrices was developed for parallel vector supercomputers with a hierarchy of memory layers (i.e., local memories, shared memory, semiconductor extended storage, and magnetic disk). The algorithm is based on Gaussian elimination and optimizes data transfers among memory layers by recursively using a block partitioning method. Using four memory layers, an LU factorization for a 32768×32768 dense matrix was calculated in 640 min on the HPP-LHS supercomputer system developed under the MITI (Ministry of International Trade and Industry) Supercomputer Project. Required memory capacity for the gigantic matrix is 8 GB, and the whole matrix data area was allocated to magnetic disk for this calculation. The execution speed with four processors was 2.8 times faster than that with one processor, even using a magnetic disk, and the algorithm was proved to be effective