A Large Grain Parallel Unsymmetric Sparse Linear System Solver

Members of the project team

Research objectives

Although there has been a substantial research effort in parallelizing unsymmetric sparse linear system solvers, the most commonly used linear system solver is still the inherently sequential MA28 (MA48) solver, developed by Harwell. Further, most existing research concentrated on defining linear system solvers which rely on small to medium size grain parallelism.
The objective of this project is to develop an unsymmetric sparse linear system solver (MCSPARSE) which is based on large grain parallelism as well as medium and small grain parallelism. In order to exploit large grain parallelism, tearing techniques are employed that maintain reasonable stability. This is accomplished by a combination of a novel reordering technique and pivoting strategy.

An initial implementation of MCSPARSE specifically targeted for the Cedar multiprocessor is already developed at the Center for Supercomputing Research and Development, University of Illinois in collaboration with Dr. K. Gallivan and B. Marsolf.

Within this project we intend to parallelize the reordering on which the particular tearing techniques rely on, and modify the factorization phase of the solver in such a way that efficient implementations are obtained for both shared and distributed memory platforms.

Collaborations

Collaborations exist with CSRD (Dr. K. Gallivan, B. Marsolf) and with the French Aerospace Laboratory ONERA (Dr. P. Leca, Dr. F. Roux).

Timetable

Starting date: September 1992
Ending date: ...

Intended results, deliverables

Efficient implementations of MCSPARSE specifically targeted for multiple CPU CRAY systems, Intel iPSC860, Thinking Machines CM-5, and IBM SP1 and SP2. Integration of MCSPARSE in real application codes.

Recent publications

J.P. Geschiere, H.A.G. Wijshoff, B.A. Marsolf, and K.A. Gallivan. Targeting a Sparse Unsymmetric Linear System Solver Towards a Variety of High-Performance Platforms. Under revision for publication in a special issue of the BIT Numerical Mathematics Journal.
J.P. Geschiere and H.A.G. Wijshoff. Exploiting Large Grain Parallelism in a Sparse Direct Linear System Solver. Parallel Computing Journal, Vol. 21 (1995), Number 8, August 1995, pp. 1339-1364.
F.X. Roux and J.P. Geschiere. Domain Decomposition Techniques for Solving Linear Systems. APPARC Esprit deliverable PaA4, July 1994 (available via ftp at ftp.wi.leidenuniv.nl).
J.P. Geschiere and H.A.G. Wijshoff. Exploiting Large Grain Parallellism in a Sparse Direct Linear System Solver. Technical Report 93-18, Department of Computer Science, Leiden University, May 1993 (Earlier version of the Journal paper listed above).
J.P. Geschiere. Research on Parallelizing the Reordering Phase of MCSPARSE, a large grain parallel sparse unsymmetric linear system solver. Technical Report INF/SCR-92-23, Department of Computer Science, Utrecht University, August 1992, Master Thesis.

Last modified on July 2, 1996 by Lex Wolters.