Numerical solutions of partial differential equations (pde's) are required in many physical problems arising in areas such as computational fluid dynamics, atmospheric sciences, electromagnetics etc. One of the most popular methods of solving pde's is the use of the multigrid algorithm. However, the implementation of the multigrid algorithm on massively parallel machines is not very efficient because of (i) low processor utilization and (ii) high communication overheads. These problems need to be addressed to make better use of massively parallel machines for solving pde's using the multigrid algorithm.
In this dissertation, we present three parallel multigrid algorithms which address the above mentioned problems and thus obtain a better performance on massively parallel machines than the standard multigrid algorithm. The first of these, the Overlap Parallel Multigrid (OPMG) algorithm, uses unutilized processors on the coarse grids of the multigrid hierarchy to do additional computation. The additional computation improves the convergence rate of the multigrid algorithm and thus reduces the total parallel execution time to solve a problem. The second algorithm, the Chopped Parallel Multigrid (CPMG) algorithm, reduces the computational work on the coarse grids of the multigrid hierarchy, while keeping the convergence rate per cycle almost the same. The reduction in the computational work reduces the average parallel execution time per cycle, which in turn results in a reduced total parallel execution time. A combination of the complementary approaches used by these two algorithms is the source for our third algorithm, the hybrid algorithm. The hybrid algorithm obtains a better performance than the standard multigrid algorithm by improving the convergence rate per cycle and also by reducing the average parallel execution time per cycle. Both these factors reduce the total parallel execution time for solving pde's using the multigrid algorithm.
We implemented the above three algorithms and also the standard multigrid algorithm on a massively parallel SIMD machine, the AMT-DAP/510, consisting of 1024 processors. The parallel implementation results show that our algorithms obtain a significant advantage over the standard multigrid algorithm. On the average, a speed-up of approximately 30%, 40% and 60% over the standard multigrid algorithm is obtained by the OPMG algorithm, the CPMG algorithm and the hybrid algorithm respectively.
","abstract_html":"<p>Numerical solutions of partial differential equations (<em>pde's</em>) are required in many physical problems arising in areas such as computational fluid dynamics, atmospheric sciences, electromagnetics etc. One of the most popular methods of solving <em>pde's</em> is the use of the multigrid algorithm. However, the implementation of the multigrid algorithm on massively parallel machines is not very efficient because of (i) low processor utilization and (ii) high communication overheads. These problems need to be addressed to make better use of massively parallel machines for solving <em>pde's</em> using the multigrid algorithm.</p> <p>In this dissertation, we present three parallel multigrid algorithms which address the above mentioned problems and thus obtain a better performance on massively parallel machines than the standard multigrid algorithm. The first of these, the <em>Overlap Parallel Multigrid</em> (<em>OPMG</em>) algorithm, uses unutilized processors on the coarse grids of the multigrid hierarchy to do additional computation. The additional computation improves the convergence rate of the multigrid algorithm and thus reduces the total parallel execution time to solve a problem. The second algorithm, the <em>Chopped Parallel Multigrid</em> (<em>CPMG</em>) algorithm, reduces the computational work on the coarse grids of the multigrid hierarchy, while keeping the convergence rate per cycle almost the same. The reduction in the computational work reduces the average parallel execution time per cycle, which in turn results in a reduced total parallel execution time. A combination of the complementary approaches used by these two algorithms is the source for our third algorithm, the hybrid algorithm. The hybrid algorithm obtains a better performance than the standard multigrid algorithm by improving the convergence rate per cycle and also by reducing the average parallel execution time per cycle. Both these factors reduce the total parallel execution time for solving <em>pde's</em> using the multigrid algorithm.</p> <p>We implemented the above three algorithms and also the standard multigrid algorithm on a massively parallel SIMD machine, the AMT-DAP/510, consisting of 1024 processors. The parallel implementation results show that our algorithms obtain a significant advantage over the standard multigrid algorithm. On the average, a speed-up of approximately 30%, 40% and 60% over the standard multigrid algorithm is obtained by the <em>OPMG</em> algorithm, the <em>CPMG</em> algorithm and the hybrid algorithm respectively.</p>","abstract_has_math":false,"creators":["Gupta, Satyanarayan"],"institution":null,"degree_name":"Doctor of Philosophy (PhD)","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Mohammed Zubair","Chester E. Grosch","Kurt Maly","Thomas L. Jackson"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":1992,"date_issued":"1992-07-01T07:00:00Z","date_published":"1992-07-01T07:00:00Z","updated_at":"2026-07-24T03:35:08Z","subjects":["Execution time","Parallel machines","Multigrid algorithms","Computer Sciences"],"languages":[],"rights":["In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.odu.edu/computerscience_etds/101","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Mohammed Zubair","Chester E. Grosch","Kurt Maly","Thomas L. Jackson"]},{"key":"dc:creator","label":"Author","values":["Gupta, Satyanarayan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2019-09-25T07:00:00Z"]},{"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":["Doctor of Philosophy (PhD)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Execution time","Parallel machines","Multigrid algorithms","Computer Sciences"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.odu.edu/computerscience_etds/101"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Numerical solutions of partial differential equations (pde's) are required in many physical problems arising in areas such as computational fluid dynamics, atmospheric sciences, electromagnetics etc. One of the most popular methods of solving pde's is the use of the multigrid algorithm. However, the implementation of the multigrid algorithm on massively parallel machines is not very efficient because of (i) low processor utilization and (ii) high communication overheads. These problems need to be addressed to make better use of massively parallel machines for solving pde's using the multigrid algorithm.
In this dissertation, we present three parallel multigrid algorithms which address the above mentioned problems and thus obtain a better performance on massively parallel machines than the standard multigrid algorithm. The first of these, the Overlap Parallel Multigrid (OPMG) algorithm, uses unutilized processors on the coarse grids of the multigrid hierarchy to do additional computation. The additional computation improves the convergence rate of the multigrid algorithm and thus reduces the total parallel execution time to solve a problem. The second algorithm, the Chopped Parallel Multigrid (CPMG) algorithm, reduces the computational work on the coarse grids of the multigrid hierarchy, while keeping the convergence rate per cycle almost the same. The reduction in the computational work reduces the average parallel execution time per cycle, which in turn results in a reduced total parallel execution time. A combination of the complementary approaches used by these two algorithms is the source for our third algorithm, the hybrid algorithm. The hybrid algorithm obtains a better performance than the standard multigrid algorithm by improving the convergence rate per cycle and also by reducing the average parallel execution time per cycle. Both these factors reduce the total parallel execution time for solving pde's using the multigrid algorithm.
We implemented the above three algorithms and also the standard multigrid algorithm on a massively parallel SIMD machine, the AMT-DAP/510, consisting of 1024 processors. The parallel implementation results show that our algorithms obtain a significant advantage over the standard multigrid algorithm. On the average, a speed-up of approximately 30%, 40% and 60% over the standard multigrid algorithm is obtained by the OPMG algorithm, the CPMG algorithm and the hybrid algorithm respectively.
"]},{"key":"dc:title","label":"Title","values":["Multigrid Algorithms for Massively Parallel Machines"]}]}],"canonical_facts":{"dc:contributor":["Mohammed Zubair","Chester E. Grosch","Kurt Maly","Thomas L. Jackson"],"dc:creator":["Gupta, Satyanarayan"],"dc:date.available":["2019-09-25T07:00:00Z"],"dc:description.abstract":["Numerical solutions of partial differential equations (pde's) are required in many physical problems arising in areas such as computational fluid dynamics, atmospheric sciences, electromagnetics etc. One of the most popular methods of solving pde's is the use of the multigrid algorithm. However, the implementation of the multigrid algorithm on massively parallel machines is not very efficient because of (i) low processor utilization and (ii) high communication overheads. These problems need to be addressed to make better use of massively parallel machines for solving pde's using the multigrid algorithm.
In this dissertation, we present three parallel multigrid algorithms which address the above mentioned problems and thus obtain a better performance on massively parallel machines than the standard multigrid algorithm. The first of these, the Overlap Parallel Multigrid (OPMG) algorithm, uses unutilized processors on the coarse grids of the multigrid hierarchy to do additional computation. The additional computation improves the convergence rate of the multigrid algorithm and thus reduces the total parallel execution time to solve a problem. The second algorithm, the Chopped Parallel Multigrid (CPMG) algorithm, reduces the computational work on the coarse grids of the multigrid hierarchy, while keeping the convergence rate per cycle almost the same. The reduction in the computational work reduces the average parallel execution time per cycle, which in turn results in a reduced total parallel execution time. A combination of the complementary approaches used by these two algorithms is the source for our third algorithm, the hybrid algorithm. The hybrid algorithm obtains a better performance than the standard multigrid algorithm by improving the convergence rate per cycle and also by reducing the average parallel execution time per cycle. Both these factors reduce the total parallel execution time for solving pde's using the multigrid algorithm.
We implemented the above three algorithms and also the standard multigrid algorithm on a massively parallel SIMD machine, the AMT-DAP/510, consisting of 1024 processors. The parallel implementation results show that our algorithms obtain a significant advantage over the standard multigrid algorithm. On the average, a speed-up of approximately 30%, 40% and 60% over the standard multigrid algorithm is obtained by the OPMG algorithm, the CPMG algorithm and the hybrid algorithm respectively.
"],"dc:identifier":["https://digitalcommons.odu.edu/computerscience_etds/101"],"dc:rights":["In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
"],"dc:subject":["Execution time","Parallel machines","Multigrid algorithms","Computer Sciences"],"dc:title":["Multigrid Algorithms for Massively Parallel Machines"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Doctor of Philosophy (PhD)"]},"updated_at":"2026-07-24T03:35:08Z"}