Multilevel fast multipole algorithm for the discrete dipole approximation

The discrete dipole approximation, originally developed by Purcell and Penn ypacker is a quite general method for solving scattering from irregularly s haped targets and/or a cluster of targets. Computationally, the method requ ires the solution of large dense systems of linear equations and various it erative methods have been employed in the literature for the purpose. In th is work, the multi-level fast multipole algorithm is used to compute the ma trix-vector product in the iterative methods. This algorithm has O(N) compl exity and thus makes it feasible to solve hundreds of thousands of unknowns . Different formulas that has been proposed in the literature for determini ng the dipole polarizabilities in the discrete dipole approximation are com pared. The method is checked by computing the scattering from spherical tar gets.