A parallel scaled conjugate-gradient algorithm for the solution phase of gathering radiosity on hypercubes

Gathering radiosity is a popular method for investigating lighting effects in a closed environment. In lighting simulations, with fixed locations of objects and light sources, the intensity and color and/or reflectivity vary. After the form-factor values are computed, the linear system of equations is solved repeatedly to visualize these changes. The scaled conjugate-gradient method is a powerful technique for solving large sparse linear systems of equations with symmetric positive definite matrices. We investigate this method for the solution phase. The nonsymmetric form-factor matrix is transformed into a symmetric matrix. We propose an efficient data redistribution scheme to achieve almost perfect load balance. We also present several parallel algorithms for form-factor computation.