Enhanced Parallel Multicolor Preconditioning Techniques for Linear Systems.
Yousef El-Mabruk Saad, Masha Sosonkina · 1999
When solving a linear system in parallel, a large overhead in using an incomplete LU factorization as a preconditioner may annihilate any gains made from the improved convergence. This overhead is due to the inherently sequential nature of such a preconditioning. Multicoloring of the subdomains assigned to processors is a common remedy for increasing the parallelism of a global ordering. However, the achieved degree of parallelism is still limited since different colors must be processed sequentially. Further reductions of the parallel overhead are possible. Here we suggest several strategies to decrease the idle time in the multicolor block Gauss-Seidel preconditioning. 1 Introduction Parallel preconditioners may be developed in two distinct ways: extracting parallelism from efficient sequential techniques or designing a preconditioner from the start specifically for parallel platforms. Preconditioners developed from the first approach yield the same good convergence properti...