Multicoloring for Fast Sparse Matrix-Vector Multiplication in Solving PDE Problems
H.C. Wang, Kai Hwang · 1993
A new multicoloring technique is proposed for parallel sparse matrix-vector multiplication, which dominates the computing cost of iterative PDE (partial differential equation) solvers. The new technique enables parallel solution of grid-structured nonsymmetric PDE problems on shared-memory multiprocessors through resolving memory access conflicts by multiple processors. The coloring scheme is formulated as an algebraic mapping which can be implemented with low overhead.