Title: A Parallel Scaled Conjugate-Gradient Algorithm for the Solution Phase of Gathering Radiosity
Authors: Tahsin M. Kurc, Cevdet Aykanat, and Bulent Ozguc
Status: Published in Visual Computer, vol. 13, pp. 1-19, 1997


The gathering radiosity is a popular method for investigating the lighting effects in a closed environment. In lighting simulations, the locations of
objects and light sources usually remain fixed, whereas the intensity and color of light sources and/or reflectivity of objects vary in time. For lighting simulations, after the form-factor values are computed and stored, the linear system of equations are solved repeatedly to visualize the effect of these changes. Therefore, efficient implementation of the solution phase becomes crucial for such applications. The Scaled Conjugate-Gradient (SCG) method is known to be a powerful technique for the solution of large sparse linear system of equations with symmetric positive definite matrices. In this paper, the utilization and parallelization of SCGmethod is investigated for the solution phase. The non-symmetric form-factor matrix is efficiently transformed into a symmetric matrix. An efficient data redistribution scheme is proposed to achieve almost perfect load balance in the solution phase. Several parallel algorithms for the form-factor computation phase are also presented. The relative performance of the proposed algorithms are experimented on a 16-processor Intel's iPSC/2 hypercube multicomputer. Very high efficiency values are obtained for sufficiently large granularity.

Full paper