Some experiments with SuiteSparse

Internals & Design
1

Hi.

I would like to share some experiences regarding some modifications on SuiteSparse and its Julia interface. As a disclaimer, I state that I only tested the modifications in a linux machine, with fedora 27, gcc and intel hardware. All the modifications where performed over the current master (02/27/2018)

After some experiments, I played with the following:

  1. I changed cholfact function to allow the user to set a specific ordering method, via

unsafe_store!(common_nmethods, ordering)

where ordering in [0,2,…9] is a new information provided by the user, with a default value of 0 (this is the actual behaviour). The other options are:

  1. AMD with default parameters.
  2. METIS with default parameters.
  3. NESDIS with default parameters: stopping the partitioning when the graph is of size nd small
    = 200 or less, remove nodes with more than max (16, prune dense * sqrt (n)) nodes
    where prune dense = 10, and follow partitioning with constrained minimum degree ordering
    (CAMD for the symmetric case, CCOLAMD for the unsymmetric case).
  4. natural ordering (with weighted postorder).
  5. NESDIS, nd small = 20000, prune dense = 10.
  6. NESDIS, nd small = 4, prune dense = 10, no constrained minimum degree.
  7. NESDIS, nd small = 200, prune dense = 0.
  8. COLAMD for A*A’ or AMD for A

This modification is very easy and provides some fine tunning to the well written Julia interface.

  1. I bumped the SuiteSparse version to 5.1.2. This version has two very interesting advantages over the current version used in Julia master: it includes Metis (Option 3 above) and has a good support for CUDA (when compared to the actual version). So far I played with METIS only.

Regarding METIS, its inclusion in Julia is also quite easy. First, I added a new entry to Make.inc: SUITE_SPARSE_METIS =0/1. If 0 (METIS disabled) one has to add -DNPARTITION to CHOLMOD_CONFIG. Its done.

If METIS is enabled, than, in deps/suitesparse.mk:

a) set LDLIBS:=-fopenmp
b) copy libmetis.so from SuiteSparse/lib to usr/lib (under julia source tree)
c) include -lmetis when converting the cholmod library from static to shared. Also, add $(LDLIBS) to include openmp
d) add -lmetis in SUITESPARSE_LIB

SUITESPARSE_LIB := -lumfpack -lcholmod -lamd -lcamd -lcolamd -lspqr -lmetis

With those modifications, I have been able to use METIS and also to properly choose the partition method.

In a first test, I was realy disapointed with the performance of the default scheme (ordering=0). Actually, for a very large sparse matrix, CHOLMOD first try AMD and then uses METIS. Thus, the time increases when compared to a system without METIS. On the other hand, subsequent uses of the factorization are faster:

C = cholfact(A) → time increases if METIS is needed
cholfact!(C,A) → faster

Sincerely yours,
Eduardo.

6 Likes