5.1.1 Algorithmic Complexity

First the computational effort is considered, which is necessary for setting up the system matrix of (5.6). In principle, every pair of surface elements must be tested, if reemitted particles from one element can reach the other. A reasonable lower bound estimation for the complexity of such a visibility test is ${\mathcal{O}}(\log{{N}_\text{S}})$ . Hence, the total complexity for the setup of the system matrix is at least ${\mathcal{O}}( {{N}_\text{S}}^2\log{{N}_\text{S}})$ .

Solving the system of linear equations also exhibits a bad scaling behavior. The expected number of non-zero entries is ${\mathcal{O}}({{N}_\text{S}}^2)$ [41]. A very efficient approach to solve the system is an iterative technique described in [6]. In this way usually only a small number of matrix-vector multiplications is necessary to obtain a convergent solution. Since the complexity of a matrix-vector multiplication is ${\mathcal{O}}({{N}_{\Gamma}}{{N}_\text{S}}^2)$ , a quadratic scaling with surface size also governs the solution of the system.