{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/121351"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/121351","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Automatic synthesis of high performance translation operators and execution plans for the fast multipole method","abstract":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2025-08-01","abstract_html":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2025-08-01","abstract_has_math":false,"creators":["Fernando, Isuru Dilanka"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Klöckner, Andreas","Olson, Luke","Fischer, Paul","Askham, Travis"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-08","date_published":"2023-08","updated_at":"2026-07-22T22:24:57Z","subjects":["Scientific Computing","Fast Multipole Method","Gpu"],"languages":["en","eng"],"rights":["© 2023 Isuru Fernando"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/121351","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Klöckner, Andreas","Olson, Luke","Fischer, Paul","Askham, Travis"]},{"key":"dc:creator","label":"Author","values":["Fernando, Isuru Dilanka"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-08","2023-07-11"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"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":["Scientific Computing","Fast Multipole Method","Gpu"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["© 2023 Isuru Fernando"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/121351"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2025-08-01","The student, Isuru Fernando, accepted the attached license on 2023-07-10 at 19:11.","The student, Isuru Fernando, submitted this Dissertation for approval on 2023-07-10 at 19:15.","This Dissertation was approved for publication on 2023-07-11 at 14:15.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19613 on 2023-12-04 at 17:18:27","The Fast Multipole Method (FMM) is the leading approach for attaining linear complexity in the evaluation of long-range (e.g. Coulomb) many-body interactions. The intricacies of implementing a high performant FMM for different potentials are a major barrier to the widespread use of the FMM. In the application of the Fast Multipole Method to the computation of potentials for elliptic PDEs and systems thereof, I present methods that, given various small amounts of user-supplied problem knowledge automatically exploit this knowledge to optimize evaluating the potentials. The first part of the thesis is devoted to the automatic synthesis of translation operators (e.g. multipole-to-local, point-to-multipole, etc.) for arbitrary kernels. I describe the asymptotic cost of variants of our algorithm available given certain pieces of information, as well as the methods by which they are attained. I present theoretical cost bounds as well as numerical evidence that our algorithms attain them. The second part of the thesis describes my work in extending the first to a system of PDEs. I introduce algorithms to automatically synthesize execution plans for expressions of potential operators involving multiple inputs and outputs, multiple different kernels, as well as source and target derivatives. Given a symbolic description of such an operator, the system outputs a sequence of operations that realizes cost savings through an algebraic procedure based on syzygies. Finally, I describe the work of using the above algorithms to generate fast code for graphical processing units (GPUs) that achieve near peak performance and explaining the performance characteristics of the different operations in the FMM using a performance model."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Automatic synthesis of high performance translation operators and execution plans for the fast multipole method"]}]}],"canonical_facts":{"dc:contributor":["Klöckner, Andreas","Olson, Luke","Fischer, Paul","Askham, Travis"],"dc:creator":["Fernando, Isuru Dilanka"],"dc:date":["2023-08","2023-07-11"],"dc:description":["Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2025-08-01","The student, Isuru Fernando, accepted the attached license on 2023-07-10 at 19:11.","The student, Isuru Fernando, submitted this Dissertation for approval on 2023-07-10 at 19:15.","This Dissertation was approved for publication on 2023-07-11 at 14:15.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19613 on 2023-12-04 at 17:18:27","The Fast Multipole Method (FMM) is the leading approach for attaining linear complexity in the evaluation of long-range (e.g. Coulomb) many-body interactions. The intricacies of implementing a high performant FMM for different potentials are a major barrier to the widespread use of the FMM. In the application of the Fast Multipole Method to the computation of potentials for elliptic PDEs and systems thereof, I present methods that, given various small amounts of user-supplied problem knowledge automatically exploit this knowledge to optimize evaluating the potentials. The first part of the thesis is devoted to the automatic synthesis of translation operators (e.g. multipole-to-local, point-to-multipole, etc.) for arbitrary kernels. I describe the asymptotic cost of variants of our algorithm available given certain pieces of information, as well as the methods by which they are attained. I present theoretical cost bounds as well as numerical evidence that our algorithms attain them. The second part of the thesis describes my work in extending the first to a system of PDEs. I introduce algorithms to automatically synthesize execution plans for expressions of potential operators involving multiple inputs and outputs, multiple different kernels, as well as source and target derivatives. Given a symbolic description of such an operator, the system outputs a sequence of operations that realizes cost savings through an algebraic procedure based on syzygies. Finally, I describe the work of using the above algorithms to generate fast code for graphical processing units (GPUs) that achieve near peak performance and explaining the performance characteristics of the different operations in the FMM using a performance model."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/121351"],"dc:language":["en","eng"],"dc:rights":["© 2023 Isuru Fernando"],"dc:subject":["Scientific Computing","Fast Multipole Method","Gpu"],"dc:title":["Automatic synthesis of high performance translation operators and execution plans for the fast multipole method"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:57Z"}