Fast algorithms for small particle scattering problems

Method of Moments;Computational Electromagnetics;Fast Multipole Method;Matrix Projection Algorithms

Sarathy, Aditya ; Chew ; Weng Cho

关键词: Method of Moments;    Computational Electromagnetics;    Fast Multipole Method;    Matrix Projection Algorithms;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/50498/Aditya_Sarathy.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

In scattering problems, commonly used techniques are surface and volume integral equations. Discrete dipole approximation (DDA) is an alternate and useful discretization technique to solve these problems where the continuum scatterer is replaced by a set of polarizable dipoles. It is an alternative to volume integral equations and produces a dense matrix equation to be solved. Computationally, the method requires the solution of large dense systems of linear equations, and various iterative methods have been employed in the literature for the purpose. In this work, two distinct methods are proposed that can reduce the cost of computation.The first method to reduce the computation time of the solution is using matrix decomposition methods. The idea in this method is using randomized algorithms for low rank approximating of matrices. When implemented using special kinds of random matrices, the computational complexity of the multilevel solver is comparable to that of the fast multipole method. These methods, however, require visiting every entry of the interaction matrix at least once, thereby incurring a computational bottleneck of $\mathcal{O}(N^2)$. They are error controllable and a greater error margin can reduce the computation time. The second method to reduce the computational complexity is the fast multipole method (FMM). This is based on the factorization of the Green's function and is useful only in those cases where the Green's function of the system can be decomposed into a product of special functions. The decomposition of the free space Green's function is well known using the addition theorem. However, in more complicated cases, this factorization is extremely complicated. In the case considered in this thesis, however, the scattering problem is formulated using the free space Green's function and can be sped up using the FMM also, which requires much less computational time than the matrix decomposition method.