{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/17044"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/17044","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Generalizing smoothed aggregation-based algebraic multigrid","abstract":"Smoothed aggregation-based (SA) algebraic multigrid (AMG) is a popular and effective solver for systems of linear equations that arise from discretized partial differential equations. While SA has been effective over a broad class of problems, it has several limitations and weaknesses that this thesis is intended to address. This includes the development of a more robust strength-of-connection measure which guides coarsening and the choice of interpolation sparsity patterns. Unfortunately, the classic strength measure is only well-founded for M-matrices, leading us to develop a new measure based on local knowledge of both algebraically smooth error and the behavior of interpolation. Another limitation is that classic SA is only formally defined for Hermitian positive definite problems. For non-Hermitian operators, the operator-induced energy-norm does not exist, which impacts the complementary relationship between relaxation and interpolation. This requires a redesign of SA, such that restriction and prolongation operators approximate the left and right near null-spaces, respectively. As a result, we develop general SA setup algorithms for both the Hermitian positive-definite and the non-Hermitian cases. To realize these algorithms, we develop general prolongation smoothing methods so that restriction and prolongation target the left and right near null-spaces, respectively. Overall, the proposed methods do not assume any user-input beyond what standard SA does and the result is a new direction for multigrid methods for non-Hermitian systems. Several problem areas motivate our development. For example, rotated anisotropic diffusion and linearized elasticity problems using standard discretizations can easily generate non-M-matrices that prove difficult for standard SA and AMG. High- and low-order discontinuous Galerkin discretizations also generate difficult non-M-matrices for elliptic problems. Target non-Hermitian problems include flow problems and wave-like problems, e.g., Helmholtz. Additionally for wave-like problems, there is a rich non-standard wave-like near null-space, which must be captured by the coarse levels—a task beyond the scope of traditional AMG or SA coarsening techniques.","abstract_html":"Smoothed aggregation-based (SA) algebraic multigrid (AMG) is a popular and effective solver for systems of linear equations that arise from discretized partial differential equations. While SA has been effective over a broad class of problems, it has several limitations and weaknesses that this thesis is intended to address. This includes the development of a more robust strength-of-connection measure which guides coarsening and the choice of interpolation sparsity patterns. Unfortunately, the classic strength measure is only well-founded for M-matrices, leading us to develop a new measure based on local knowledge of both algebraically smooth error and the behavior of interpolation. Another limitation is that classic SA is only formally defined for Hermitian positive definite problems. For non-Hermitian operators, the operator-induced energy-norm does not exist, which impacts the complementary relationship between relaxation and interpolation. This requires a redesign of SA, such that restriction and prolongation operators approximate the left and right near null-spaces, respectively. As a result, we develop general SA setup algorithms for both the Hermitian positive-definite and the non-Hermitian cases. To realize these algorithms, we develop general prolongation smoothing methods so that restriction and prolongation target the left and right near null-spaces, respectively. Overall, the proposed methods do not assume any user-input beyond what standard SA does and the result is a new direction for multigrid methods for non-Hermitian systems. Several problem areas motivate our development. For example, rotated anisotropic diffusion and linearized elasticity problems using standard discretizations can easily generate non-M-matrices that prove difficult for standard SA and AMG. High- and low-order discontinuous Galerkin discretizations also generate difficult non-M-matrices for elliptic problems. Target non-Hermitian problems include flow problems and wave-like problems, e.g., Helmholtz. Additionally for wave-like problems, there is a rich non-standard wave-like near null-space, which must be captured by the coarse levels—a task beyond the scope of traditional AMG or SA coarsening techniques.","abstract_has_math":false,"creators":["Schroder, Jacob B."],"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 N.","Gropp, William D.","Heath, Michael T.","Tuminaro, Raymond S."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2010,"date_issued":"2010-08-31T20:30:25Z","date_published":"2010-08-31T20:30:25Z","updated_at":"2026-07-22T22:25:09Z","subjects":["smoothed aggregation","algebraic multigrid","Helmholtz","indefinite","nonsymmetric","algebraic coarsening","discontinuous Galerkin","high-order","prolongation smoothing","strength-of-connection"],"languages":["en"],"rights":["Copyright 2010 Jacob B. Schroder"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/17044","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Olson, Luke N.","Gropp, William D.","Heath, Michael T.","Tuminaro, Raymond S."]},{"key":"dc:creator","label":"Author","values":["Schroder, Jacob B."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2010-08-31T20:30:25Z","2012-09-07T16:43:38Z","2010-08"]},{"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":["smoothed aggregation","algebraic multigrid","Helmholtz","indefinite","nonsymmetric","algebraic coarsening","discontinuous Galerkin","high-order","prolongation smoothing","strength-of-connection"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2010 Jacob B. Schroder"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/17044"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Smoothed aggregation-based (SA) algebraic multigrid (AMG) is a popular and effective solver for systems of linear equations that arise from discretized partial differential equations. While SA has been effective over a broad class of problems, it has several limitations and weaknesses that this thesis is intended to address. This includes the development of a more robust strength-of-connection measure which guides coarsening and the choice of interpolation sparsity patterns. Unfortunately, the classic strength measure is only well-founded for M-matrices, leading us to develop a new measure based on local knowledge of both algebraically smooth error and the behavior of interpolation. Another limitation is that classic SA is only formally defined for Hermitian positive definite problems. For non-Hermitian operators, the operator-induced energy-norm does not exist, which impacts the complementary relationship between relaxation and interpolation. This requires a redesign of SA, such that restriction and prolongation operators approximate the left and right near null-spaces, respectively. As a result, we develop general SA setup algorithms for both the Hermitian positive-definite and the non-Hermitian cases. To realize these algorithms, we develop general prolongation smoothing methods so that restriction and prolongation target the left and right near null-spaces, respectively. Overall, the proposed methods do not assume any user-input beyond what standard SA does and the result is a new direction for multigrid methods for non-Hermitian systems. Several problem areas motivate our development. For example, rotated anisotropic diffusion and linearized elasticity problems using standard discretizations can easily generate non-M-matrices that prove difficult for standard SA and AMG. High- and low-order discontinuous Galerkin discretizations also generate difficult non-M-matrices for elliptic problems. Target non-Hermitian problems include flow problems and wave-like problems, e.g., Helmholtz. Additionally for wave-like problems, there is a rich non-standard wave-like near null-space, which must be captured by the coarse levels—a task beyond the scope of traditional AMG or SA coarsening techniques.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2010-05-28T20:49:46Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Schroder_Jacob.pdf: 4166896 bytes, checksum: 690ee904ff70049ee8fe5e76dc835a6b (MD5)","Made available in DSpace on 2010-08-31T20:30:25Z (GMT). No. of bitstreams: 2 Schroder_Jacob.pdf: 4166896 bytes, checksum: 690ee904ff70049ee8fe5e76dc835a6b (MD5) license.txt: 4064 bytes, checksum: 342a962b1cda329aedb2f0a2dfcd4478 (MD5)","Item marked as restricted to the 'Administrator' Group (id=1) by William Ingram (wingram2@illinois.edu) on 2010-08-31T20:32:53Z Item is restricted until 2012-08-31T20:32:49Z","Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2012-09-07T16:43:38Z Item was in collections: University of Illinois Dissertations and Theses (ID: 204) Dissertations and Theses - Computer Science (ID: 587) No. of bitstreams: 3 Schroder_Jacob.pdf: 4166896 bytes, checksum: 690ee904ff70049ee8fe5e76dc835a6b (MD5) license.txt: 4064 bytes, checksum: 342a962b1cda329aedb2f0a2dfcd4478 (MD5) Schroder_Jacob.pdf.txt: 260845 bytes, checksum: 5154726544219a0269ce5bd1400777ab (MD5)","Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2012-09-07T16:43:38Z"]},{"key":"dc:title","label":"Title","values":["Generalizing smoothed aggregation-based algebraic multigrid"]}]}],"canonical_facts":{"dc:contributor":["Olson, Luke N.","Gropp, William D.","Heath, Michael T.","Tuminaro, Raymond S."],"dc:creator":["Schroder, Jacob B."],"dc:date":["2010-08-31T20:30:25Z","2012-09-07T16:43:38Z","2010-08"],"dc:description":["Smoothed aggregation-based (SA) algebraic multigrid (AMG) is a popular and effective solver for systems of linear equations that arise from discretized partial differential equations. While SA has been effective over a broad class of problems, it has several limitations and weaknesses that this thesis is intended to address. This includes the development of a more robust strength-of-connection measure which guides coarsening and the choice of interpolation sparsity patterns. Unfortunately, the classic strength measure is only well-founded for M-matrices, leading us to develop a new measure based on local knowledge of both algebraically smooth error and the behavior of interpolation. Another limitation is that classic SA is only formally defined for Hermitian positive definite problems. For non-Hermitian operators, the operator-induced energy-norm does not exist, which impacts the complementary relationship between relaxation and interpolation. This requires a redesign of SA, such that restriction and prolongation operators approximate the left and right near null-spaces, respectively. As a result, we develop general SA setup algorithms for both the Hermitian positive-definite and the non-Hermitian cases. To realize these algorithms, we develop general prolongation smoothing methods so that restriction and prolongation target the left and right near null-spaces, respectively. Overall, the proposed methods do not assume any user-input beyond what standard SA does and the result is a new direction for multigrid methods for non-Hermitian systems. Several problem areas motivate our development. For example, rotated anisotropic diffusion and linearized elasticity problems using standard discretizations can easily generate non-M-matrices that prove difficult for standard SA and AMG. High- and low-order discontinuous Galerkin discretizations also generate difficult non-M-matrices for elliptic problems. Target non-Hermitian problems include flow problems and wave-like problems, e.g., Helmholtz. Additionally for wave-like problems, there is a rich non-standard wave-like near null-space, which must be captured by the coarse levels—a task beyond the scope of traditional AMG or SA coarsening techniques.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2010-05-28T20:49:46Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Schroder_Jacob.pdf: 4166896 bytes, checksum: 690ee904ff70049ee8fe5e76dc835a6b (MD5)","Made available in DSpace on 2010-08-31T20:30:25Z (GMT). No. of bitstreams: 2 Schroder_Jacob.pdf: 4166896 bytes, checksum: 690ee904ff70049ee8fe5e76dc835a6b (MD5) license.txt: 4064 bytes, checksum: 342a962b1cda329aedb2f0a2dfcd4478 (MD5)","Item marked as restricted to the 'Administrator' Group (id=1) by William Ingram (wingram2@illinois.edu) on 2010-08-31T20:32:53Z Item is restricted until 2012-08-31T20:32:49Z","Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2012-09-07T16:43:38Z Item was in collections: University of Illinois Dissertations and Theses (ID: 204) Dissertations and Theses - Computer Science (ID: 587) No. of bitstreams: 3 Schroder_Jacob.pdf: 4166896 bytes, checksum: 690ee904ff70049ee8fe5e76dc835a6b (MD5) license.txt: 4064 bytes, checksum: 342a962b1cda329aedb2f0a2dfcd4478 (MD5) Schroder_Jacob.pdf.txt: 260845 bytes, checksum: 5154726544219a0269ce5bd1400777ab (MD5)","Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2012-09-07T16:43:38Z"],"dc:identifier":["http://hdl.handle.net/2142/17044"],"dc:language":["en"],"dc:rights":["Copyright 2010 Jacob B. Schroder"],"dc:subject":["smoothed aggregation","algebraic multigrid","Helmholtz","indefinite","nonsymmetric","algebraic coarsening","discontinuous Galerkin","high-order","prolongation smoothing","strength-of-connection"],"dc:title":["Generalizing smoothed aggregation-based algebraic multigrid"],"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:25:09Z"}