next up previous index
Next: Gauss-Seidel iteration Up: RADIOSITY METHOD Previous: Cubic tetrahedral algorithm

Solution of the linear equation


The most obvious way to solve a linear equation is to apply the Gauss elimination method [PFTV88]. Unfortunately it fails to solve the radiosity equation for more complex models effectively, since it has tex2html_wrap_inline2254 complexity, and also it accumulates the round of errors of digital computers and magnifies these errors to the extent that the matrix is close to singular.

  Fortunately another technique, called iteration, can overcome both problems. Examining the radiosity equation,


we will see that it gives the equality of the energy which has to be radiated due to emission and reflection (right side) and the energy really emitted (left side). Suppose that only estimates are available for tex2html_wrap_inline2258 radiosities, not exact values. These estimates can be regarded as right side values, thus having substituted them into the radiosity equation, better estimates can be expected on the left sides. If these estimates were exact -- that is they satisfied the radiosity equation --, then the iteration would not alter the radiosity values. Thus, if this iteration converges, its limit will be the solution of the original radiosity equation.

In order to examine the method formally, the matrix version of the radiosity equation is used to describe a single step of the iteration:


A similar equation holds for the previous iteration too. Subtracting the two equations, and applying the same consideration recursively, we get:


The iteration converges if


for some matrix norm. Let us use the tex2html_wrap_inline2262 norm defined as the maximum of absolute row sums


and a vector norm that is compatible with it:


Denoting tex2html_wrap_inline2264 by q, we have:



according to the properties of matrix norms. Since tex2html_wrap_inline1862 represents the portion of the radiated energy of surface i, which actually reaches surface j, tex2html_wrap_inline2276 is that portion which is radiated towards any other surface. This obviously cannot exceed 1, and for physically correct models, diffuse reflectance tex2html_wrap_inline2278 , giving a norm that is definitely less than 1. Consequently q<1, which provides the convergence with, at least, the speed of a geometric series.

The complexity of the iteration solution depends on the operations needed for a single step and the number of iterations providing convergence. A single step of the iteration requires the multiplication of an N dimensional vector and an tex2html_wrap_inline2284 dimensional matrix, which requires tex2html_wrap_inline2286 operations.

Concerning the number of necessary steps, we concluded that the speed of the convergence is at least geometric by a factor tex2html_wrap_inline2288 . The infinite norm of tex2html_wrap_inline2290 is close to being independent of the number of surface elements, since as the number of surface elements increases, the value of form factors decreases, sustaining a constant sum of rows, representing that portion of the energy radiated by surface i, which is gathered by other surfaces, multiplied by the diffuse coefficient of surface i. Consequently, the number of necessary iterations is independent of the number of surface elements, making the iteration solution an tex2html_wrap_inline2286 process.  

next up previous index
Next: Gauss-Seidel iteration Up: RADIOSITY METHOD Previous: Cubic tetrahedral algorithm

Szirmay-Kalos Laszlo
Mon Oct 21 14:07:41 METDST 1996