Abstract
A recursive rotation algorithm is built and investigated. The algorithm is a possible version of the nested dissection algorithm. The Liu algorithm builds a matrix graph separator by means of rotation of an elimination tree, which reduces the height of the latter. In this case, the nodes of the matrix graph are previously reordered by one of the well-known Cuthill-McKee algorithms, the reverse Cuthill-McKee algorithm, and the King algorithm. Then this procedure is recursively repeated. The recursive rotation algorithm is compared with the multilevel and spectral methods of graph separation for 2D finite-element grids.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
George, A., Solution of Sparse Systems of Equations on Multiprocessor Architectures, Lect. Notes Math., 1989, vol. 1394, pp. 31–94.
Liu, J.W., Reordering Sparse Matrices for Parallel Elimination, in Parallel Computing, North-Holland, 1989, pp. 73–91.
Liu, J.W., Equivalent Sparse Matrix Reordering by Elimination Tree Rotations, SIAM J. Sci. Stat. Comput., 1988, vol. 9, no. 3, pp. 424–444.
Maslovskaya, L.V., Maslovskaya, O.M., and Kravchenko, A.I., Recursive Rotation Algorithm for Building Graph Separators for the Nested Dessection Method, Abstr. Ukranian Mathematical Congress, L’vov, 2009; http://www.imath.kiev.ua/congress2009/Abstracts/KravchenkoMaslovski.pdf.
Liu, J.W., A Compact Storage Scheme for Cholesky Factors Using Elimination Trees, ACM Trans. Math. Soft., 1986, vol. 12, pp. 127–148.
Tarjan, R.E., Data Structures and Network Algorithms, CBMS-NSF Reg. Conf. Ser. Appl. Math., SIAM, Philadelphia, 1983.
George, A. and Liu, J.W., Computer Solution of Large Sparse Positive Definite Systems, Prentice Hall, 1981.
Lipton, R.J., Rose, D.J., and Tarjan, R.E., Generalized Nested Dissection, SIAM J. Num. Anal., 1979, vol. 16, pp. 346–358.
Gilbert, J.R. and Tarjan, R.E., The Analysis of a Nested Dissection Algorithm, Num. Math., 1987, vol. 50, pp. 377–404.
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © L.V. Maslovskaya, O.M. Maslovskaya, 2010, published in Sibirskii Zhurnal Vychislitel’noi Matematiki, 2010, Vol. 13, No. 3, pp. 297–321.
Rights and permissions
About this article
Cite this article
Maslovskaya, L.V., Maslovskaya, O.M. Building graph separators with the recursive rotation algorithm for the nested dissection method. Numer. Analys. Appl. 3, 241–262 (2010). https://doi.org/10.1134/S1995423910030055
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1995423910030055