Distributed sparse matrix factorization: QR and Cholesky decompositions
Padma Raghavan · 1992
The problem of decomposing a sparse matrix into factors on a distributed memory machine is considered. The factorization involves a symbolic phase in which a sparsity preserving ordering is computed. The symbolic phase is followed by a numeric phase, which has a higher sequential computational complexity. Algorithms are developed to exploit medium- and large-grain parallelism for the numeric computation of factors. The two problems considered are the orthogonal factorization of an overdetermined sparse matrix of full column rank, and the Cholesky decomposition of a sparse symmetric positive definite system. The parallelization of these two factorization schemes requires the efficient solution of the attendant data distribution and task allocation problem. The latter is formulated on an appropriate task graph which is a tree structure for medium- and large-grain parallelism. In the context of distributed orthogonal factorization, a distributed submatrix merge scheme is developed based on a task graph called the merge tree. A task involves merging dense submatrices obtained as a result of predecessor tasks. The large-grain, 'proportional heuristic' assigns subtrees composed of smaller and earlier tasks to a processor for local processing without any communication. Larger and later tasks are assigned to groups of processors for effective load balance at the expense of communication overheads. Experiments were performed on the iPSC/2 for a model grid problem and for systems of linear equations arising from graded L-shaped regions. Analysis for the model problem indicates that the parallel arithmetic complexity is optimal and that the communication complexity is of lower order. A related problem is that of task and data assignment for distributed column-oriented Cholesky factorization. Two column-oriented schemes are considered for distributed computation of the Cholesky factor. The assignment problem is closely related to the classical one-task-to-one-processor, multiprocessor scheduling problem. An extension of list scheduling is developed to incorporate message passing latencies. Worst case performance bounds are derived analytically. A variant of the proportional heuristic is also developed, which has low time and space complexities. Implementations of the numeric factorization phase on the Intel iPSC/2 exhibit good speed-ups.