Parallelized ICCG method using block-multicolor orderings in real symmetric linear system derived from voltage-driven FEM in time domain

Abstract

Purpose

The purpose of this paper is to improve the performance of block-multicolor (BMC) ordering for the parallelized incomplete-Cholesky-preconditioned conjugate gradient (ICCG) method. Then, the BMC ordering based on level structure arising in reverse Cuthill-McKee RCM ordering is newly proposed. The name of proposed method is abbreviated as “RBMC”. This paper shows the validity of proposed method by comparison with greedy-based multicolor (MC) and conventional BMC on the real symmetric linear system derived from the voltage-driven finite element method in time domain.

Design/methodology/approach

In RBMC, the blocking and coloring is performed level by level. The number of synchronizations in forward and backward substitution is reduced so that all blocks can be colored with two colors. However, the load-balance in forward and backward substitution might deteriorate because the irregular block matrices are distributed around diagonal. To uniformize load-balance in forward and backward substitution, the RBMC combined with the concept of block red-black ordering has been developed.

Findings

The modified RBMC was the most effective for reduction of the elapsed time among four orderings (MC, BMC, RBMC, modified RBMC) owing to improvement of convergence characteristic and load-balance.

Originality/value

The proposed method had two advantages: although the number of unknowns per block must be previously determined in BMC, its parameter is automatically determined in proposed method, the number of synchronization in forward and backward substitution can be reduced.

Citation

Tsuburaya, T., Okamoto, Y. and Sato, S. (2015), "Parallelized ICCG method using block-multicolor orderings in real symmetric linear system derived from voltage-driven FEM in time domain", COMPEL - The international journal for computation and mathematics in electrical and electronic engineering, Vol. 34 No. 5, pp. 1433-1446. https://doi.org/10.1108/COMPEL-02-2015-0069