Sangback Ma
Department of Computer Science
Hanyang University, Ansan, Korea
email: sangback@cse.hanyang.ac.kr
and
Ho-jong Jang
Department of Mathematics
Hanyang University, Seoul, Korea
email: hjang@hanyang.ac.kr
We consider the generalized eigenvalue problem A x = Lambda B x, where A and B are large sparse symmetric definite, and B is further positive definite. These problems arise in various applications, such as structural analysis, magnetohydrodynamics and computational chemistry, to name a few. Since A and B are large and sparse we use CG-like iterative method to compute the minimization of Rayleigh-quotient, and after the smallest eigenvalue is found we use the orthogonal deflation technique for the next eigenvalues. As in the case of the conventional CG-like methods this method is also amenable to parallel computation and also the preconditioning often accelerates the convergence.
In this paper we address ourselves to the problem of finding efficient parallel preconditioner. As in the case of iterative methods for the linear systems there is no widely accepted preconditioner for our problem. Our candidates are ILU(0) in the wafefront order, ILU(0) in the Multi-Coloring order, Point-SSOR(Successive Symmetric OverRelaxation), and Multi-Color Block SOR. ILU(0) in the wavefront order is most natural and seems to work for most problems, but the ILU(0) method is inherently serial and its speedup is limited due to the wavefront lengths. As for the ILU(0) in the Multi-Coloring order the Multi-Coloring can easily achieve the speedup of order(N), where N is the order of the matrix, but often the rate of convergence deteriorates. Finally, the Block SOR method in the Multi-Coloring order is expected to show good performance in parallel computers with the distribued memory, since the Block method minimizes the interprocessor communications and good speedup from the Multi-Coloring.
As for the experiments we set B=I, and m to be 5, the number of the eigenvalues to be found. Test matrices were created by discretizing the elliptic partial differential equations on a square grid by finite difference method. The matrix dimensions range up to 262,144. The CRAY-T3E with 128 nodes at the KISTI, Korea was used. The MPI library was used for the interprocessor communications. We used a direct sparse solver for the inversion of the diagonal blocks for the Block SOR method.
Our results show that for small number of processors the Multi-Color ILU(0) gives the best performance, while for large number of processors the Multi-Color Block SOR gives the best performance.