Scotch Brand 5.1.10 - Manual (Page 133)

• Alex Pothen kindly gave me a version of his Multiple Minimum Degree algo-
rithm, which was embedded into Scotch from version 3.2 to version 3.4;
• Luca Scarano, visiting Erasmus student from the Universit´ a degli Studi di
Bologna , coded the multi-level graph algorithm in Scotch 3.1;
• Yves Secretan contributed to the MinGW32 port;
• David Sherman proofread version 3.2 of this manual.
References
[1] P. Amestoy, T. Davis, and I. Duff. An approximate minimum degree ordering
algorithm. SIAM J. Matrix Anal. and Appl., 17:886–905, 1996.
[2] C. Ashcraft. Compressed graphs and the minimum degree algorithm. SIAM
J. Sci. Comput. , 16(6):1404–1411, 1995.
[3] C. Ashcraft, S. Eisenstat, J. W.-H. Liu, and A. Sherman. A comparison of
three column based distributed sparse factorization schemes. In Proc. Fifth
SIAM Conf. on Parallel Processing for Scientific Computing
, 1991.
[4] S. T. Barnard and H. D. Simon. A fast multilevel implementation of recur-
sive spectral bisection for partitioning unstructured problems. Concurrency:
Practice and Experience
, 6(2):101–117, 1994.
[5] R. F. Boisvert, R. Pozo, and K. A. Remington. The Matrix Market exchange
formats: initial design. NISTIR 5935, National Institute of Standards and
Technology, December 1996.
[6] CeCILL: “CEA-CNRS-INRIA Logiciel Libre” free/libre software license. Avail-
able from http://www.cecill.info/licenses.en.html.
[7] P. Charrier and J. Roman. Algorithmique et calculs de complexit´e pour un
solveur de type dissections emboˆıt´ees. Numerische Mathematik, 55:463–476,
1989.
[8] C. Chevalier and F. Pellegrini. Improvement of the efficiency of genetic algo-
rithms for scalable parallel graph partitioning in a multi-level framework. In
Proc. EuroPar, Dresden
, LNCS 4128, pages 243–252, September 2006.
[9] I. Duff. On algorithms for obtaining a maximum transversal. ACM Trans.
Math. Software , 7(3):315–330, September 1981.
[10] I. S. Duff, R. G. Grimes, and J. G. Lewis. Users’ guide for the Harwell-
Boeing sparse matrix collection. Technical Report TR/PA/92/86, CERFACS,
Toulouse, France, October 1992.
[11] F. Ercal, J. Ramanujam, and P. Sadayappan. Task allocation onto a hyper-
cube by recursive mincut bipartitionning. Journal of Parallel and Distributed
Computing
, 10:35–44, 1990.
[12] C. M. Fiduccia and R. M. Mattheyses. A linear-time heuristic for improving
network partitions. In Proceedings of the 19th Design Automation Conference,
pages 175–181. IEEE, 1982.
133