A New Algorithm for Finding a Pseudoperipheral Node in a Graph

Autor:	Horst D. Simon, Roger G. Grimes, Daniel J. Pierce
Rok vydání:	1990
Předmět:	Simplex algorithm Ramer–Douglas–Peucker algorithm Cuthill–McKee algorithm Minimum degree algorithm Johnson's algorithm Sparse approximation Algorithm Analysis Mathematics FSA-Red Algorithm Sparse matrix
Zdroj:	SIAM Journal on Matrix Analysis and Applications. 11:323-334
ISSN:	1095-7162 0895-4798
DOI:	10.1137/0611022
Popis:	A new algorithm for the computation of a pseudoperipheral node of a graph is presented, and the application of this algorithm to reordering algorithms for the solution of sparse linear systems is discussed. Numerical tests on large sparse matrix problems show the efficiency of the new algorithm. When used for some of the reordering algorithms for reducing the profile and bandwidth of a sparse matrix, the results obtained with the pseudoperipheral nodes of the new algorithm are comparable to the results obtained with the pseudoperipheral nodes produced by the SPARSPAK version of the Gibbs—Poole—Stockmeyer algorithm. The advantage of the new algorithm is that it accesses the adjacency structure of the sparse matrix in a regular pattern. Thus this algorithm is much more suitable both for a parallel and for an out-of-core implementation of the ordering phase for sparse matrix problems.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::6f2f6bd91a5468a5269a4fb236a28135 https://doi.org/10.1137/0611022 Zobrazit plný text záznamu