Downloads & Free Reading Options - Results

There are at least two-critical components required to obtain extremely fast methods for solving sparse linear systems. One is the use of efficient and robust numerical algorithms, and the other is the employment of effective techniques for delivering a large amount of computing power. These requirements can conflict with one another in a variety of ways. Many modern methods of solving reasonably general classes of linear systems involve a degree of implicitness; this implicitness can limit the amount of available concurrency. When Krylov space linear solvers are used, the choice of preconditioner can play a major role in determining the operation count of the resulting algorithm. Unfortunately, some of the most powerful preconditioners are obtained by using incompletely factored matrices. To apply these preconditioners, we must repeatedly solve sparse triangular systems. The efficiency with which such solutions could be carried out was characterized by Saad and Schultz. Sparse triangular systems arising from a range of problems have been solved efficiently on a number of shared memory architectures 1,3,4,9. Because data dependencies limit the concurrency available from a sparse triangular solve, it has not been clear that triangular solves could be employed usefully in programs written for massively parallel architectures.