A conjugate gradient method for the spectral partitioning of graphs

Nicolaas P. Kruyt

doi:10.1016/S0167-8191(96)00059-2

A conjugate gradient method for the spectral partitioning of graphs

Nicolaas P. Kruyt

Faculty of Engineering Technology

Research output: Contribution to journal › Article › Academic

6 Citations (Scopus)

181 Downloads (Pure)

Abstract

The partitioning of graphs is a frequently occurring problem in science and engineering. The spectral graph partitioning method is a promising heuristic method for this class of problems. Its main disadvantage is the large computing time required to solve a special eigenproblem. Here a simple and efficient method is proposed to reduce this computing time. This method is based on the conjugate gradient minimization method. The convergence properties of the new method are studied for the case of regular one-, two-, and three-dimensional grids. The influence of the aspect ratio of the graph on the convergence rate is also investigated.

Original language	Undefined
Pages (from-to)	1493-1502
Journal	Parallel computing
Volume	22
Issue number	11
DOIs	https://doi.org/10.1016/S0167-8191(96)00059-2
Publication status	Published - 1997

Keywords

IR-57232

Access to Document

10.1016/S0167-8191(96)00059-2

Kruyt97conjugate

Cite this

@article{f6a2c55d991846959632ea11b4557ec3,

title = "A conjugate gradient method for the spectral partitioning of graphs",

abstract = "The partitioning of graphs is a frequently occurring problem in science and engineering. The spectral graph partitioning method is a promising heuristic method for this class of problems. Its main disadvantage is the large computing time required to solve a special eigenproblem. Here a simple and efficient method is proposed to reduce this computing time. This method is based on the conjugate gradient minimization method. The convergence properties of the new method are studied for the case of regular one-, two-, and three-dimensional grids. The influence of the aspect ratio of the graph on the convergence rate is also investigated.",

keywords = "IR-57232",

author = "Kruyt, {Nicolaas P.}",

year = "1997",

doi = "10.1016/S0167-8191(96)00059-2",

language = "Undefined",

volume = "22",

pages = "1493--1502",

journal = "Parallel computing",

issn = "0167-8191",

publisher = "Elsevier B.V.",

number = "11",

}

TY - JOUR

T1 - A conjugate gradient method for the spectral partitioning of graphs

AU - Kruyt, Nicolaas P.

PY - 1997

Y1 - 1997

N2 - The partitioning of graphs is a frequently occurring problem in science and engineering. The spectral graph partitioning method is a promising heuristic method for this class of problems. Its main disadvantage is the large computing time required to solve a special eigenproblem. Here a simple and efficient method is proposed to reduce this computing time. This method is based on the conjugate gradient minimization method. The convergence properties of the new method are studied for the case of regular one-, two-, and three-dimensional grids. The influence of the aspect ratio of the graph on the convergence rate is also investigated.

AB - The partitioning of graphs is a frequently occurring problem in science and engineering. The spectral graph partitioning method is a promising heuristic method for this class of problems. Its main disadvantage is the large computing time required to solve a special eigenproblem. Here a simple and efficient method is proposed to reduce this computing time. This method is based on the conjugate gradient minimization method. The convergence properties of the new method are studied for the case of regular one-, two-, and three-dimensional grids. The influence of the aspect ratio of the graph on the convergence rate is also investigated.

KW - IR-57232

U2 - 10.1016/S0167-8191(96)00059-2

DO - 10.1016/S0167-8191(96)00059-2

M3 - Article

SN - 0167-8191

VL - 22

SP - 1493

EP - 1502

JO - Parallel computing

JF - Parallel computing

IS - 11

ER -