{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/72802"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/72802","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Data parallel algebraic multigrid","abstract":"Algebraic multigrid methods for large, sparse linear systems are central to many computational simulations. Parallel algorithms for such solvers are generally decomposed into coarse-grain tasks suitable for distributed computers with traditional processing cores. Accelerating multigrid methods on massively parallel throughput-oriented processors, on the other hand, demands algorithms with abundant fine-grained parallelism. In this dissertation we analyze and decompose the smoothed aggregation algebraic multigrid method into parallel primitives effectively mapped to emerging architectures. Our formulation is performed in two phases, the first building on high-level generic abstractions to construct our solver in a architecture agnostic manner. Though effective we show that performance is severely limited by irregular sparse matrix operations, most notably sparse matrix-matrix multiplication. In the second phase, we address this performance bottleneck using novel techniques to optimize irregular sparse matrix operations. This dissertation is also concerned with irregular graph operations necessary to partition sparse matrices into disjoint sets for parallel processing. We apply our solver to accelerate eigenvector computations necessary during spectral partitioning methods and find that performance is limited by multigrid construction. We propose and analyze a novel strategy to accelerate graph Laplacian eigenvector computations by combining iterative methods, namely blocked Lanczos, with breadth first search operations on graphs. By basing our partitioner on primitives with substantial parallelism we demonstrate notable performance improvement compared with generic eigensolvers.","abstract_html":"Algebraic multigrid methods for large, sparse linear systems are central to many computational simulations. Parallel algorithms for such solvers are generally decomposed into coarse-grain tasks suitable for distributed computers with traditional processing cores. Accelerating multigrid methods on massively parallel throughput-oriented processors, on the other hand, demands algorithms with abundant fine-grained parallelism. In this dissertation we analyze and decompose the smoothed aggregation algebraic multigrid method into parallel primitives effectively mapped to emerging architectures. Our formulation is performed in two phases, the first building on high-level generic abstractions to construct our solver in a architecture agnostic manner. Though effective we show that performance is severely limited by irregular sparse matrix operations, most notably sparse matrix-matrix multiplication. In the second phase, we address this performance bottleneck using novel techniques to optimize irregular sparse matrix operations. This dissertation is also concerned with irregular graph operations necessary to partition sparse matrices into disjoint sets for parallel processing. We apply our solver to accelerate eigenvector computations necessary during spectral partitioning methods and find that performance is limited by multigrid construction. We propose and analyze a novel strategy to accelerate graph Laplacian eigenvector computations by combining iterative methods, namely blocked Lanczos, with breadth first search operations on graphs. By basing our partitioner on primitives with substantial parallelism we demonstrate notable performance improvement compared with generic eigensolvers.","abstract_has_math":false,"creators":["Dalton, Steven"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Olson, Luke","Gropp, William","Heath, Michael","Brown, Jed"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-01-21T19:48:20Z","date_published":"2015-01-21T19:48:20Z","updated_at":"2026-07-22T22:26:07Z","subjects":["graphics processing unit (GPU)","algebraic multigrid (AMG)","Sparse matrix"],"languages":["en"],"rights":["Copyright 2014 Steven Dalton"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/72802","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Olson, Luke","Gropp, William","Heath, Michael","Brown, Jed"]},{"key":"dc:creator","label":"Author","values":["Dalton, Steven"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-01-21T19:48:20Z","2014-12","2015-01-21"]},{"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":["graphics processing unit (GPU)","algebraic multigrid (AMG)","Sparse matrix"]}]},{"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 Steven Dalton"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/72802"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Algebraic multigrid methods for large, sparse linear systems are central to many computational simulations. Parallel algorithms for such solvers are generally decomposed into coarse-grain tasks suitable for distributed computers with traditional processing cores. Accelerating multigrid methods on massively parallel throughput-oriented processors, on the other hand, demands algorithms with abundant fine-grained parallelism. In this dissertation we analyze and decompose the smoothed aggregation algebraic multigrid method into parallel primitives effectively mapped to emerging architectures. Our formulation is performed in two phases, the first building on high-level generic abstractions to construct our solver in a architecture agnostic manner. Though effective we show that performance is severely limited by irregular sparse matrix operations, most notably sparse matrix-matrix multiplication. In the second phase, we address this performance bottleneck using novel techniques to optimize irregular sparse matrix operations. This dissertation is also concerned with irregular graph operations necessary to partition sparse matrices into disjoint sets for parallel processing. We apply our solver to accelerate eigenvector computations necessary during spectral partitioning methods and find that performance is limited by multigrid construction. We propose and analyze a novel strategy to accelerate graph Laplacian eigenvector computations by combining iterative methods, namely blocked Lanczos, with breadth first search operations on graphs. By basing our partitioner on primitives with substantial parallelism we demonstrate notable performance improvement compared with generic eigensolvers.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2014-12-05T18:17:58Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Dalton_Steven.pdf: 6152425 bytes, checksum: 92d92a16424dcf7fd1bbcb755ab4bfcb (MD5)","Made available in DSpace on 2015-01-21T19:48:20Z (GMT). No. of bitstreams: 1 Steven_Dalton.pdf: 6152244 bytes, checksum: 56c6b06130afd0dd1ac1126ec720737d (MD5)"]},{"key":"dc:title","label":"Title","values":["Data parallel algebraic multigrid"]}]}],"canonical_facts":{"dc:contributor":["Olson, Luke","Gropp, William","Heath, Michael","Brown, Jed"],"dc:creator":["Dalton, Steven"],"dc:date":["2015-01-21T19:48:20Z","2014-12","2015-01-21"],"dc:description":["Algebraic multigrid methods for large, sparse linear systems are central to many computational simulations. Parallel algorithms for such solvers are generally decomposed into coarse-grain tasks suitable for distributed computers with traditional processing cores. Accelerating multigrid methods on massively parallel throughput-oriented processors, on the other hand, demands algorithms with abundant fine-grained parallelism. In this dissertation we analyze and decompose the smoothed aggregation algebraic multigrid method into parallel primitives effectively mapped to emerging architectures. Our formulation is performed in two phases, the first building on high-level generic abstractions to construct our solver in a architecture agnostic manner. Though effective we show that performance is severely limited by irregular sparse matrix operations, most notably sparse matrix-matrix multiplication. In the second phase, we address this performance bottleneck using novel techniques to optimize irregular sparse matrix operations. This dissertation is also concerned with irregular graph operations necessary to partition sparse matrices into disjoint sets for parallel processing. We apply our solver to accelerate eigenvector computations necessary during spectral partitioning methods and find that performance is limited by multigrid construction. We propose and analyze a novel strategy to accelerate graph Laplacian eigenvector computations by combining iterative methods, namely blocked Lanczos, with breadth first search operations on graphs. By basing our partitioner on primitives with substantial parallelism we demonstrate notable performance improvement compared with generic eigensolvers.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2014-12-05T18:17:58Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Dalton_Steven.pdf: 6152425 bytes, checksum: 92d92a16424dcf7fd1bbcb755ab4bfcb (MD5)","Made available in DSpace on 2015-01-21T19:48:20Z (GMT). No. of bitstreams: 1 Steven_Dalton.pdf: 6152244 bytes, checksum: 56c6b06130afd0dd1ac1126ec720737d (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/72802"],"dc:language":["en"],"dc:rights":["Copyright 2014 Steven Dalton"],"dc:subject":["graphics processing unit (GPU)","algebraic multigrid (AMG)","Sparse matrix"],"dc:title":["Data parallel algebraic multigrid"],"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:26:07Z"}