The International Conference for High Performance Computing, Networking, Storage and Analysis
Structure-Aware Parallel Algorithm for Solution of Sparse Triangular Linear Systems.
Student: Ehsan Totoni (University of Illinois at Urbana-Champaign)
Supervisor: Laxmikant V. Kale (University of Illinois at Urbana-Champaign)
Abstract: Solution of sparse triangular systems of linear equations is a
performance bottleneck in many methods for solving more general
sparse systems. In both direct methods and iterative preconditioners,
it is used to solve the system or refine the solution, often across
many iterations. Triangular solution is notoriously resistant to
parallelism, however, and existing parallel linear algebra packages
appear to be ineffective in exploiting much parallelism for this
problem.
We develop a novel parallel algorithm based on various heuristics
that adapts to the structure of the matrix and extracts parallelism
that is unexploited by conventional methods. By analysis and
reordering operations, our
algorithm can extract parallelism of many different sparse matrix structures.
