PMORSy: parallel sparse matrix ordering software for fill-in minimizationFootnote^†

† This work was presented at the 5th International Conference on Network Analysis, held in Nizhni Novgorod, Russia, 18–20 May 2015.

References

• P.R. Amestoy, T. Davis, and I. Duff, An approximate minimum degree ordering algorithm, SIAM J. Matrix Anal. Appl. 17(4) (1996), pp. 886–905.
   Web of Science ®Google Scholar
• C. Aschcraft and J.W.H. Liu, A partition improvement algorithm for generalized nested dissection, Tech. Rep. BCSTECH-94-020, Boeing Computer Services, Seattle, WA, 1994.
   Google Scholar
• Ch.-Ed. Bichot and P. Siarry (eds.), Graph Partitioning, John Wiley and Sons, New York, 2013.
   Google Scholar
• T.N. Bui and C. Jones, A heuristic for reducing fill-in in sparse matrix factorization, No. DOE/ER/25151--1-Vol. 1; CONF-930331-Vol. 1. SIAM, Philadelphia, PA, 1993.
   Google Scholar
• C. Chevalier and F. Pellegrini, PT-Scotch: A tool for efficient parallel graph ordering, Parallel Comput. 34(6) (2008), pp. 318–331.
   Web of Science ®Google Scholar
• T.A. Davis, J.R. Gilbert, S.I. Larimore, and E.G. Ng, A column approximate minimum degree ordering algorithm, ACM Trans. Math. Software. 30(3) (2004), pp. 353–376.
   Web of Science ®Google Scholar
• T.A. Davis and Y. Hu, The University of Florida sparse matrix collection, ACM Trans. Math. Software. 38(1) (2011), p. 1.
   Web of Science ®Google Scholar
• A. Ferreira and P.M. Pardalos, Solving Combinatorial Optimization Problems in Parallel-Methods and Techniques. Lecture Notes in Comput. Sci., Springer Verlag, Berlin, Vol. 1054, 1996.
   Google Scholar
• C.M. Fiduccia and R.M. Mattheyses, A linear time heuristic for improving network partitions, 19th IEEE Conference on Design Automation, 1982, pp. 175–181.
   Google Scholar
• A. George, Nested dissection of a regular finite element mesh, SIAM J. Numer. Anal. 10(2) (1973), pp. 345–363.
   Web of Science ®Google Scholar
• A. George, M.T. Heath, J.W.H. Liu, and E. Ng, Sparse Cholesky factorization on a local-memory multiprocessor, SIAM J. Sci. Stat. Comp. 9(2) (1988), pp. 327–340.
   Web of Science ®Google Scholar
• A. George and J.W.H. Liu, An automatic nested dissection algorithm for irregular finite element problems, SIAM J. Numer. Anal. 15(5) (1978), pp. 1053–1069.
   Web of Science ®Google Scholar
• GraphViz, Graph Visualization Software; software available at http://www.graphviz.org/.
   Google Scholar
• B. Hendrickson and R. Leland, A multi-level algorithm for partitioning graphs. Tech. Rep. SAND93-1301, Sandia National Laboratories, 1993.
   Google Scholar
• B. Hendrickson and E. Rothberg, Improving the run time and quality of nested dissection ordering, SIAM J. Sci. Comput. 20 (1999), pp. 468–489.
   Web of Science ®Google Scholar
• Intel Math Kernel Library Reference Manual. Available at http://software.intel.com/sites/default/files/managed/9d/c8/mklman.pdf.
   Google Scholar
• Intel MKL PARDISO— Parallel Direct Sparse Solver Interface. Available at https://software.intel.com/en-us/node/521677.
   Google Scholar
• G. Karipis, METIS. A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. V. 5.0. Tech. Rep., University Of Minnesota, Department of Computer Science and Engineering, 2011.
   Google Scholar
• G. Karypis and V. Kumar, ParMetis: Parallel graph partitioning and sparse matrix ordering library. Tech. Rep. TR 97-060, Department of Computer Science, University Of Minnesota, 1997.
   Google Scholar
• G. Karypis and V. Kumar, A parallel algorithm for multilevel graph partitioning and sparse matrix ordering, J. Parallel Distrib. Comput. 48 (1998), pp. 71–95.
   Web of Science ®Google Scholar
• G. Karypis and V. Kumar, A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM J. Sci. Comput. 20(1) (1998), pp. 359–392.
   Web of Science ®Google Scholar
• B.W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs, Bell Syst. Tech. J. 49 (1970), pp. 291–307.
   Google Scholar
• D. Lasalle and G. Karypis, Multi-threaded Graph Partitioning. Parallel & Distributed Processing (IPDPS), 2013, pp. 225–236.
   Google Scholar
• D. LaSalle and G. Karypis, Efficient Nested Dissection for Multicore Architectures. Euro-Par 2015: Parallel Processing, 2015, Springer Berlin Heidelberg, pp. 467–478.
   Google Scholar
• J.-Y. L’Excellent, Multifrontal methods: Parallelism, memory usage and numerical aspects, Doctoral diss., École normale supérieure de Lyon, 2012.
   Google Scholar
• R.J. Lipton, D.J. Rose, and R.E. Tarjan, Generalized nested dissection, SIAM J. Numer. Anal. 16(2) (1979), pp. 346–358.
   Web of Science ®Google Scholar
• J.W.H. Liu, Modification of the minimum-degree algorithm by multiple elimination, ACM Trans. Math. Software. 11(2) (1985), pp. 141–153.
   Web of Science ®Google Scholar
• MORSy software; software available at http://hpc-education.unn.ru/research/overview/sparse-algebra/morsy.
   Google Scholar
• P.M. Pardalos (ed.), Parallel Processing of Discrete Problems. The IMA Volumes in Mathematics and its Applications, Vol. 106, Springer, New York, 1999.
   Google Scholar
• F. Pellegrini, Scotch and Libscotch 6.0 User’s guide, Tech. Rep., LABRI, 2012.
   Google Scholar
• F. Pellegrini, Shared memory parallel algorithms in Scotch 6. Available at http://graal.ens-lyon.fr/mumps/doc/ud_2013/pellegrini.pdf.
   Google Scholar
• F. Pellegrini, J. Roman, and P. Amestoy, Hybridizing nested dissection and halo approximate minimum degree for efficient sparse matrix ordering, Concurr. Comput. 12 (2000), pp. 69–84.
   Web of Science ®Google Scholar
• A. Pirova and I. Meyerov, MORSy – a new tool for sparse matrix reordering, An Int. Conf. On Engineering and Applied Sciences Optimization, 2014, pp. 1952–1964.
   Google Scholar
• V.N. Rechkin, V.F. Spiridonov, K.V. Tsibarev, D.Yu. Dyanov, A.O. Naumov, S.S. Kosarim, E.A. Finimonkin, Yu.G. Bartenev, E.B. Schanikova, V.A. Erzunov, V.A. Ryabov, and Yu.A. Vyatkin, Software Package LOGOS. Module for Solving the Quasi-static Strength Problems and Modal Analysis, Proc. of XIII International seminar ‘Supercomputations and mathematical modeling’, Sarov, 2011 (in Russian).
   Google Scholar
• K. Schloegel, G. Karypis, and V. Kumar. Parallel Multilevel Algorithms for Multi-constraint Graph Partitioning, Euro-Par 2000 Parallel Processing, 2000, pp. 296–310.
   Google Scholar
• W. Tinney and J. Walker, Direct solutions of sparse network equations by optimally ordered triangular factorization, Proc. IEEE. 55(11) (1967), pp. 1801–1809.
   Web of Science ®Google Scholar
• M. Yannakakis, Computing the minimum fill-in is NP-complete, SIAM J. Algebra. Discr. 2(1) (1981), pp. 77–79.
   Web of Science ®Google Scholar