Fast algorithms for small particle scattering problems

Sarathy, Aditya

Permalink

https://hdl.handle.net/2142/50498 Copy

Description

Title

Fast algorithms for small particle scattering problems

Author(s)

Sarathy, Aditya

Issue Date

2014-09-16

Director of Research (if dissertation) or Advisor (if thesis)

Chew, Weng Cho

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

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

Abstract

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.

Graduation Semester

2014-08

Permalink

http://hdl.handle.net/2142/50498

Copyright and License Information

Copyright 2014 Aditya Sarathy

Owning Collections