Parallel Complexity of Conjugate Gradient Method with Circulant
Block-Factorization Preconditioners for 3D Elliptic Problems

Ivan Lirkov and Svetozar Margenov
Central Laboratory for Parallel Processing
Bulgarian Academy of Sciences
Acad.G.Bonchev Str., Bl.25A, 1113 Sofia, Bulgaria

The numerical solution of large scale 3D elliptic boundary value
problems is discussed in this article. After discretization, such
problems are reduced to the solution of linear systems. We use a
preconditioner based on a block-circulant approximation of the blocks
of the stiffness matrix. We analyze the parallel complexity of the
circulant block-factorization preconditioners when solving elliptic
problems by Preconditioned Conjugate Gradient (PCG) method. We exploit
the fast inversion of block-circulant matrices. Both, the conjugate
gradient method and the inversion of circulant matrices using Fast
Fourier Transform (FFT), are highly parallelizable. Estimates for the
parallel time, the speed-up and the parallel efficiency are
derived. For the used timing model we conclude that for relatively
large problems or for relatively small number of processors the
influence of the architecture on the execution time is negligible. The
numerical tests have been executed on a symmetric multiprocessor
systems. The results presented in this paper indicate that the
parallel performance characteristics of the CBF preconditioner are
very good even for relatively small discrete problems. The developed
MPI (Message Passing Interface) code provide new effective tool for
solving of large-scale real-life problems in realistic time on a class
of coarse-grain parallel computer systems with currently increasing
cost-efficiency.

Key words: parallel algorithms, PCG method, preconditioner,
circulant, performance