Geodesic
Building graph separators with the recursive rotation algorithm for nested dissections method
Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 13 (2010) no. 3, pp. 297-321 
L. V. Maslovskaya; O. M. Maslovskaya. Building graph separators with the recursive rotation algorithm for nested dissections method. Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 13 (2010) no. 3, pp. 297-321. http://geodesic.mathdoc.fr/item/SJVM_2010_13_3_a4/
@article{SJVM_2010_13_3_a4,
     author = {L. V. Maslovskaya and O. M. Maslovskaya},
     title = {Building graph separators with the recursive rotation algorithm for nested dissections method},
     journal = {Sibirskij \v{z}urnal vy\v{c}islitelʹnoj matematiki},
     pages = {297--321},
     year = {2010},
     volume = {13},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SJVM_2010_13_3_a4/}
}
TY  - JOUR
AU  - L. V. Maslovskaya
AU  - O. M. Maslovskaya
TI  - Building graph separators with the recursive rotation algorithm for nested dissections method
JO  - Sibirskij žurnal vyčislitelʹnoj matematiki
PY  - 2010
SP  - 297
EP  - 321
VL  - 13
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/SJVM_2010_13_3_a4/
LA  - ru
ID  - SJVM_2010_13_3_a4
ER  - 
%0 Journal Article
%A L. V. Maslovskaya
%A O. M. Maslovskaya
%T Building graph separators with the recursive rotation algorithm for nested dissections method
%J Sibirskij žurnal vyčislitelʹnoj matematiki
%D 2010
%P 297-321
%V 13
%N 3
%U http://geodesic.mathdoc.fr/item/SJVM_2010_13_3_a4/
%G ru
%F SJVM_2010_13_3_a4

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] George A., “Solution of sparse systems of equations on multiprocessor architectures”, Numerical analysis and parallel processing (Lancaster, 1987), Lecture Notes in Math., 1397, Springer, Berlin, 1989, 31–94 | MR

[2] Liu J. W. H., “Reordering sparse matrices for parallel elimination”, Parallel computing, 11:1 (1989), 73–91 | DOI | MR | Zbl

[3] Liu J. W. H., “Equivalent sparse matrix reordering by elimination tree rotations”, SIAM J. Sci. Stat. Comput., 9:3 (1988), 424–444 | DOI | MR | Zbl

[4] Maslovskaya L. V., Maslovskaya O. M., Kravchenko I. A., “Algoritm rekursivnogo vrascheniya postroeniya razdelitelei grafa dlya metoda vlozhennykh sechenii”, Tezisy Ukrainskogo matematicheskogo kongressa (Lvov, 29 avgusta – 4 sentyabrya 2009 g.)

[5] Liu J. W. H., “A compact storage scheme for Cholesky factors using elimination trees”, ACM Trans. Math. Software, 12 (1986), 127–148 | DOI | MR | Zbl

[6] Tarjan R. E., Data structures and network algorithms, CBMS–NSF Regional Conference Series in Applied Mathematics, SIAM, Philadelphia, 1983 | MR | Zbl

[7] Dzhordzh A., Lyu Dzh., Chislennoe reshenie bolshikh razrezhennykh sistem, Mir, M., 1984 | MR

[8] Lipton R. J., Rose D. J., Tarjan R. E., “Generalized nested dissection”, SIAM J. Numer. Anal., 16 (1979), 346–358 | DOI | MR | Zbl

[9] Gilbert J. R., Tarjan R. E., “The analysis of a nested dissection algorithm”, Numer. Math., 50:4 (1987), 377–404 | DOI | MR | Zbl