Solving Sparse Triangular Linear Systems: A Review of Parallel and Distributed Solutions

Solving sparse triangular linear systems (spTRSV) represents a basic core in numerous scientific and computational applications such as numerical linear algebra routines including Gaussian Elimination, LU and Cholesky decompositions, etc. Finding a parallel implementation for SpTRSV is a challenging task owing to the sequential structure of the steps concerned. In this study, we review various existing approaches for spTRSV. These methods broadly split into two major categories based on sets (level or color) and methods without set creation. Another classification consists of fine-grained parallelism (small tasks) and coarse-grained parallelism (large tasks). This paper discusses and provides a performance comparison of several recent approaches for spTRSV carried out on different types of parallel and distributed architectures. It investigates the literature in terms of the structure of sparse matrices, task granularity, scheduling, data dependencies, and architecture of the target parallel machine. Ultimately, the relevant findings and future research challenges are also addressed.