ACM SRC: Structure-Aware Parallel Algorithm for Solution of Sparse Triangular Linear Systems

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.

@inproceedings{ehsan2013src,
  author = {Ehsan Totoni and Michael T. Heath and Laxmikant V. Kale},
  title = {ACM SRC: Structure-Aware Parallel Algorithm for Solution of Sparse Triangular Linear Systems},
  year = {2013},
booktitle = {Proceedings of the 2013 companion on High Performance Computing Networking, Storage and Analysis Companion},
 series = {SC '13 Companion},
 publisher = {ACM},
}