Algebraic Block Multi-Color Ordering Method for Parallel Multi-Threaded Sparse Triangular Solver in ICCG Method

This paper covers the multi-threaded parallel processing of a sparse triangular solver for a linear system with a sparse coefficient matrix, focusing on its application to a parallel ICCG solver. We propose algebraic block multi-color ordering, which is an enhanced version of block multi-color ordering for general unstructured analysis. We present blocking and coloring strategies that achieve a high cache hit ratio and fast convergence. Five numerical tests on a shared memory parallel computer verify that the computation time of the proposed method is between 1.7 and 2.6 times faster than that of the conventional multi-color ordering method.