Efficient Block Algorithms for Parallel Sparse Triangular Solve
Zhengyang Lu, Yuyao Niu, Weifeng Liu
Abstract
The sparse triangular solve (SpTRSV) kernel is an important building block for a number of linear algebra routines such as sparse direct and iterative solvers. The major challenge of accelerating SpTRSV lies in the difficulties of finding higher parallelism. Existing work mainly focuses on reducing dependencies and synchronizations in the level-set methods. However, the 2D block layout of the input matrix has been largely ignored in designing more efficient SpTRSV algorithms.
Topics & Concepts
Computer scienceBlock (permutation group theory)Kernel (algebra)Parallelism (grammar)Sparse matrixParallel computingSet (abstract data type)Linear algebraTriangular matrixMatrix (chemical analysis)Iterative methodAlgorithmTheoretical computer scienceMathematicsDiscrete mathematicsProgramming languageMaterials sciencePhysicsInvertible matrixGaussianComposite materialGeometryPure mathematicsQuantum mechanicsMatrix Theory and AlgorithmsParallel Computing and Optimization TechniquesNumerical Methods and Algorithms