Aggregation Methods for Solving Sparse Triangular Systems on Multiprocessors

Abstract

Efficient methods are presented for solving large sparse triangular systems on multiprocessors. These methods use heuristics for the aggregation, mapping, and scheduling of relatively fine-grained computations whose data dependencies are specified by directed acyclic graphs. Results of experiments run on the Encore Multimax, as well as model problem analysis, measure the performance of the partitioning strategies on shared-memory architectures with varying synchronization costs.