{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/50498"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/50498","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Fast algorithms for small particle scattering problems","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.","abstract_html":"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 <span class=\"etd-inline-math\">\\mathcal{O}(N<sup>2</sup>)</span>. 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&#x27;s function and is useful only in those cases where the Green&#x27;s function of the system can be decomposed into a product of special functions. The decomposition of the free space Green&#x27;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&#x27;s function and can be sped up using the FMM also, which requires much less computational time than the matrix decomposition method.","abstract_has_math":true,"creators":["Sarathy, Aditya"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Chew, Weng Cho"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-09-16T17:18:03Z","date_published":"2014-09-16T17:18:03Z","updated_at":"2026-07-22T22:25:40Z","subjects":["Method of Moments","Computational Electromagnetics","Fast Multipole Method","Matrix Projection Algorithms"],"languages":["en"],"rights":["Copyright 2014 Aditya Sarathy"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/50498","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Chew, Weng Cho"]},{"key":"dc:creator","label":"Author","values":["Sarathy, Aditya"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-09-16T17:18:03Z","2016-09-22T20:59:03Z","2014-08","2014-09-16"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Method of Moments","Computational Electromagnetics","Fast Multipole Method","Matrix Projection Algorithms"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2014 Aditya Sarathy"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/50498"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2014-05-28T21:00:49Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Sarathy_Aditya.pdf: 1090884 bytes, checksum: 7eaec0737b1aa594bb562d29e907aec3 (MD5)","Made available in DSpace on 2014-09-16T17:18:03Z (GMT). No. of bitstreams: 2 Aditya_Sarathy.pdf: 1090884 bytes, checksum: 7eaec0737b1aa594bb562d29e907aec3 (MD5) license.txt: 4064 bytes, checksum: 3697ee6b0098a49fa40f8be6849b1b19 (MD5)","Embargo set by: Seth Robbins for item 50609 Lift date: 2016-09-16T17:18:17Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 50609 on 2016-09-22T20:59:03Z."]},{"key":"dc:title","label":"Title","values":["Fast algorithms for small particle scattering problems"]}]}],"canonical_facts":{"dc:contributor":["Chew, Weng Cho"],"dc:creator":["Sarathy, Aditya"],"dc:date":["2014-09-16T17:18:03Z","2016-09-22T20:59:03Z","2014-08","2014-09-16"],"dc:description":["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.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2014-05-28T21:00:49Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Sarathy_Aditya.pdf: 1090884 bytes, checksum: 7eaec0737b1aa594bb562d29e907aec3 (MD5)","Made available in DSpace on 2014-09-16T17:18:03Z (GMT). No. of bitstreams: 2 Aditya_Sarathy.pdf: 1090884 bytes, checksum: 7eaec0737b1aa594bb562d29e907aec3 (MD5) license.txt: 4064 bytes, checksum: 3697ee6b0098a49fa40f8be6849b1b19 (MD5)","Embargo set by: Seth Robbins for item 50609 Lift date: 2016-09-16T17:18:17Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 50609 on 2016-09-22T20:59:03Z."],"dc:identifier":["http://hdl.handle.net/2142/50498"],"dc:language":["en"],"dc:rights":["Copyright 2014 Aditya Sarathy"],"dc:subject":["Method of Moments","Computational Electromagnetics","Fast Multipole Method","Matrix Projection Algorithms"],"dc:title":["Fast algorithms for small particle scattering problems"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:40Z"}