Multilevel Algorithms for Generating Coarse Grids for Multigrid Methods

Irene Moulitsas; George Karypis

doi:10.1145/582034.582079

Multilevel Algorithms for Generating Coarse Grids for Multigrid Methods

Irene Moulitsas, George Karypis

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

26 Scopus citations

Abstract

Geometric Multigrid methods have gained widespread acceptance for solving large systems of linear equations, especially for structured grids. One of the challenges in successfully extending these methods to unstructured grids is the problem of generating an appropriate set of coarse grids. The focus of this paper is the development of robust algorithms, both serial and parallel, for generating a sequence of coarse grids from the original unstructured grid. Our algorithms treat the problem of coarse grid construction as an optimization problem that tries to optimize the overall quality of the resulting fused elements. We solve this problem using the multilevel paradigm that has been very successful in solving the related grid/graph partitioning problem. The parallel formulation of our algorithm incurs a very small communication overhead, achieves high degree of concurrency, and maintains the high quality of the coarse grids obtained by the serial algorithm.

Original language	English (US)
Title of host publication	Proceedings of the 2001 ACM/IEEE Conference on Supercomputing, SC 2001
Publisher	Association for Computing Machinery
Pages	45
Number of pages	1
ISBN (Electronic)	158113293X
DOIs	https://doi.org/10.1145/582034.582079
State	Published - Nov 10 2001
Event	2001 ACM/IEEE Conference on Supercomputing, SC 2001 - Denver, United States Duration: Nov 10 2001 → Nov 16 2001

Publication series

Name	Proceedings of the International Conference on Supercomputing

Conference

Conference	2001 ACM/IEEE Conference on Supercomputing, SC 2001
Country/Territory	United States
City	Denver
Period	11/10/01 → 11/16/01

Bibliographical note

Funding Information:
∗This work was supported by NSF CCR-9972519, EIA-9986042, ACI-9982274, by Army Research Office contract DA/DAAG55-98-1-0441, by the DOE ASCI program, and by Army High Performance Computing Research Center contract number DAAH04-95-C-0008. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage, and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. SC2001 November 2001, Denver (c) 2001 ACM 1-58113-293-X/01/0011 $5.00

Publisher Copyright:
© 2001 ACM.

Publisher link

10.1145/582034.582079

Find It

Find It at U of M Libraries

Cite this

Multilevel Algorithms for Generating Coarse Grids for Multigrid Methods. / Moulitsas, Irene; Karypis, George.

Proceedings of the 2001 ACM/IEEE Conference on Supercomputing, SC 2001. Association for Computing Machinery, 2001. p. 45 (Proceedings of the International Conference on Supercomputing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Moulitsas, I & Karypis, G 2001, Multilevel Algorithms for Generating Coarse Grids for Multigrid Methods. in Proceedings of the 2001 ACM/IEEE Conference on Supercomputing, SC 2001. Proceedings of the International Conference on Supercomputing, Association for Computing Machinery, pp. 45, 2001 ACM/IEEE Conference on Supercomputing, SC 2001, Denver, United States, 11/10/01. https://doi.org/10.1145/582034.582079

@inproceedings{9daedb757bc4421f93eea94d2abd2560,

title = "Multilevel Algorithms for Generating Coarse Grids for Multigrid Methods",

abstract = "Geometric Multigrid methods have gained widespread acceptance for solving large systems of linear equations, especially for structured grids. One of the challenges in successfully extending these methods to unstructured grids is the problem of generating an appropriate set of coarse grids. The focus of this paper is the development of robust algorithms, both serial and parallel, for generating a sequence of coarse grids from the original unstructured grid. Our algorithms treat the problem of coarse grid construction as an optimization problem that tries to optimize the overall quality of the resulting fused elements. We solve this problem using the multilevel paradigm that has been very successful in solving the related grid/graph partitioning problem. The parallel formulation of our algorithm incurs a very small communication overhead, achieves high degree of concurrency, and maintains the high quality of the coarse grids obtained by the serial algorithm.",

author = "Irene Moulitsas and George Karypis",

note = "Funding Information: ∗This work was supported by NSF CCR-9972519, EIA-9986042, ACI-9982274, by Army Research Office contract DA/DAAG55-98-1-0441, by the DOE ASCI program, and by Army High Performance Computing Research Center contract number DAAH04-95-C-0008. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage, and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. SC2001 November 2001, Denver (c) 2001 ACM 1-58113-293-X/01/0011 $5.00 Publisher Copyright: {\textcopyright} 2001 ACM.; 2001 ACM/IEEE Conference on Supercomputing, SC 2001 ; Conference date: 10-11-2001 Through 16-11-2001",

year = "2001",

month = nov,

day = "10",

doi = "10.1145/582034.582079",

language = "English (US)",

series = "Proceedings of the International Conference on Supercomputing",

publisher = "Association for Computing Machinery",

pages = "45",

booktitle = "Proceedings of the 2001 ACM/IEEE Conference on Supercomputing, SC 2001",

}

TY - GEN

T1 - Multilevel Algorithms for Generating Coarse Grids for Multigrid Methods

AU - Moulitsas, Irene

AU - Karypis, George

N1 - Funding Information: ∗This work was supported by NSF CCR-9972519, EIA-9986042, ACI-9982274, by Army Research Office contract DA/DAAG55-98-1-0441, by the DOE ASCI program, and by Army High Performance Computing Research Center contract number DAAH04-95-C-0008. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage, and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. SC2001 November 2001, Denver (c) 2001 ACM 1-58113-293-X/01/0011 $5.00 Publisher Copyright: © 2001 ACM.

PY - 2001/11/10

Y1 - 2001/11/10

N2 - Geometric Multigrid methods have gained widespread acceptance for solving large systems of linear equations, especially for structured grids. One of the challenges in successfully extending these methods to unstructured grids is the problem of generating an appropriate set of coarse grids. The focus of this paper is the development of robust algorithms, both serial and parallel, for generating a sequence of coarse grids from the original unstructured grid. Our algorithms treat the problem of coarse grid construction as an optimization problem that tries to optimize the overall quality of the resulting fused elements. We solve this problem using the multilevel paradigm that has been very successful in solving the related grid/graph partitioning problem. The parallel formulation of our algorithm incurs a very small communication overhead, achieves high degree of concurrency, and maintains the high quality of the coarse grids obtained by the serial algorithm.

AB - Geometric Multigrid methods have gained widespread acceptance for solving large systems of linear equations, especially for structured grids. One of the challenges in successfully extending these methods to unstructured grids is the problem of generating an appropriate set of coarse grids. The focus of this paper is the development of robust algorithms, both serial and parallel, for generating a sequence of coarse grids from the original unstructured grid. Our algorithms treat the problem of coarse grid construction as an optimization problem that tries to optimize the overall quality of the resulting fused elements. We solve this problem using the multilevel paradigm that has been very successful in solving the related grid/graph partitioning problem. The parallel formulation of our algorithm incurs a very small communication overhead, achieves high degree of concurrency, and maintains the high quality of the coarse grids obtained by the serial algorithm.

UR - http://www.scopus.com/inward/record.url?scp=84945280574&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84945280574&partnerID=8YFLogxK

U2 - 10.1145/582034.582079

DO - 10.1145/582034.582079

M3 - Conference contribution

AN - SCOPUS:84945280574

T3 - Proceedings of the International Conference on Supercomputing

SP - 45

BT - Proceedings of the 2001 ACM/IEEE Conference on Supercomputing, SC 2001

PB - Association for Computing Machinery

T2 - 2001 ACM/IEEE Conference on Supercomputing, SC 2001

Y2 - 10 November 2001 through 16 November 2001

ER -

Multilevel Algorithms for Generating Coarse Grids for Multigrid Methods

Abstract

Publication series

Conference

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this