Sparse matrix ordering with Scotch

1. P. Amestoy, T. Davis, and I. Duff. An approximate minimum degree ordering algorithm. Technical Report RT/APO/95/5, ENSEEIHT-IRIT, 1995. To appear in SIAM Journal of Matrix Analysis and Applications.

   Google Scholar 

2. 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.

   Google Scholar 

3. S. T. Barnard and H. D. Simon. A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurrency: Practice and Experience, 6(2):101–117, 1994.

   Google Scholar 

4. P. Charrier and J. Roman. Algorithmique et calculs de complexité pour un solveur de type dissections emboîtées. Numerische Mathematik, 55:463–476, 1989.

   Google Scholar 

5. I. Duff. On algorithms for obtaining a maximum transversal. ACM Trans. Math. Software, 7(3):315–330, September 1981.

   Google Scholar 

6. C. M. Fiduccia and R. M. Mattheyses. A linear-time heuristic for improving network partitions. In Proc. 19th Design Autom. Conf., pages 175–181. IEEE, 1982.

   Google Scholar 

7. G. A. Geist and E. G.-Y. Ng. Task scheduling for parallel sparse Cholesky factorization. International Journal of Parallel Programming, 18(4):291–314, 1989.

   Google Scholar 

8. A. George, M. T. Heath, J. W.-H. Liu, and E. G.-Y. Ng. Sparse Cholesky factorization on a local memory multiprocessor. SIAM Journal on Scientific and Statistical Computing, 9:327–340, 1988.

   Google Scholar 

9. J. A. George and J. W.-H. Liu. Computer solution of large sparse positive definite systems. Prentice Hall, 1981.

   Google Scholar 

10. A. Gupta, G. Karypis, and V. Kumar. Highly scalable parallel algorithms for sparse matrix factorization. TR 94-063, University of Minnesota, 1994. To appear in IEEE Trans. on Parallel and Distributed Systems, 1997.

    Google Scholar 

11. A. Gupta, G. Karypis, and V. Kumar. Scalable parallel algorithms for sparse linear systems. In Proc. Stratagem'96, Sophia-Antipolis, pages 97–110. INRIA, July 1996.

    Google Scholar 

12. B. Hendrickson and R. Leland. The Chaco user's guide — version 2.0. Technical Report SAND94-2692, Sandia National Laboratories, 1994.

    Google Scholar 

13. J. Hopcroft and R. Karp. An n ^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal of Computing, 2(4):225–231, December 1973.

    Google Scholar 

14. G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. TR 95-035, University of Minnesota, June 1995.

    Google Scholar 

15. G. Karypis and V. Kumar. MeTiS — Unstructured Graph Partitioning and Sparse Matrix Ordering System — Version 2.0. University of Minnesota, June 1995.

    Google Scholar 

16. G. Karypis and V. Kumar. Parallel multilevel k-way partitioning scheme for irregular graphs. TR 96-036, University of Minnesota, 1996.

    Google Scholar 

17. C. Leiserson and J. Lewis. Orderings for parallel sparse symmetric factorization. In Third SIAM Conference on Parallel Processing for Scientific Computing, Tromsø. SIAM, 1987.

    Google Scholar 

18. J. W.-H. Liu. Modification of the minimum-degree algorithm by multiple elimination. ACM Trans. Math. Software, 11(2):141–153, 1985.

    Google Scholar 

19. F. Pellegrini. Static mapping by dual recursive bipartitioning of process and architecture graphs. In Proc. SHPCC'94, Knoxville, pages 486–493. IEEE, May 1994.

    Google Scholar 

20. F. Pellegrini. Application of graph partitioning techniques to static mapping and domain decomposition. In ETPSC 3, Faverges-de-la-Tour, August 1996. To appear in a special issue of Parallel Computing.

    Google Scholar 

21. F. Pellegrini. Scotch 3.2 User's guide. Technical Report, LaBRI, Université Bordeaux I, April 1997. Available at URL http://www.labri.u-bordeaux.fr/∼pelegrin/papers/scotch_user3.2.ps.gz.

    Google Scholar 

22. F. Pellegrini and J. Roman. Scotch: A Software Package for Static Mapping by Dual Recursive Bipartitioning of Process and Architecture Graphs. In Proceedings of HPCN'96, Brussels, LNCS 1067, pages 493–498, April 1996.

    Google Scholar 

23. A. Pothen and C.-J. Fan. Computing the block triangular form of a sparse matrix. ACM Trans. Math. Software, 16(4):303–324, December 1990.

    Google Scholar 

24. A. Pothen, H. D. Simon, and K.-P. Liou. Partitioning sparse matrices with eigen-vectors of graphs. SIAM Journal of Matrix Analysts, 11(3):430–452, July 1990.

    Google Scholar 

25. E. Rothberg. Performance of panel and block approaches to sparse Cholesky factorization on the iPSC/860 and Paragon multicomputers. In Proceedings of SH-PCC'94, Knoxville, pages 324–333. IEEE, May 1994.

    Google Scholar 

26. E. Rothberg and A. Gupta. An efficient block-oriented approach to parallel sparse Cholesky factorization. In Supercomputing'93 Proceedings. IEEE, 1993.

    Google Scholar 

27. E. Rothberg and R. Schreiber. Improved load distribution in parallel sparse Cholesky factorization. In Supercomputing'94 Proceedings. IEEE, 1994.

    Google Scholar 

28. R. Schreiber. Scalability of sparse direct solvers. Technical Report TR 92.13, RIACS, NASA Ames Research Center, May 1992.

    Google Scholar 

Download references