Building graph separators with the recursive rotation algorithm for nested dissections method

L. V. Maslovskaya, O. M. Maslovskaya

Odessa, Ukraine

Abstract: The recursive rotation algorithm is built and investigated. This algorithm is one of versions of the nested dissections algorithm. The Liu algorithm builds a matrix graph separator by the rotation of an elimination tree. The rotation of the elimination tree decreases its height. In this case, the nodes of a matrix graph are previously re-ordered by one of the well-known Cuthill–McKee algorithms, reverse to the Cuthill–McKee algorithm, or King algorithm. Then this procedure is recursively repeated. Comparison between the recursive rotation algorithm and the multilevel and spectral methods of graph separation for the 2D finite elements grids is made.

Key words: rotation of elimination tree, separators, recursive rotation algorithm, finite elements grids.

UDC: 519.6

Received: 20.10.2009
Revised: 18.11.2009

 English version: Numerical Analysis and Applications, 2010, 3:3, 241–262

Bibliographic databases:

•