Parallel graph coloring heuristics to color large-scale general jacobian matrices

Barry Smith bsmith at
Thu Sep 24 13:09:44 CDT 2009

On Sep 24, 2009, at 11:53 AM, Rafael Santos Coelho wrote:

> Hello, Hong,
> thank you very much for the help. Well, I'm not positive wether I  
> really understood what that code snippet does, but I'll definitely  
> take a closer look at it later. For now, I have some doubts I'd like  
> to clear out. As far as I'm concerned, the following line
> ierr = MatGetColoring(Jac,MATCOLORING_SL,&iscoloring);CHKERRQ(ierr);
> gives me the coloring, right? But what if I want to test my own  
> parallel coloring routine, instead of just using PETSc's? Please,  
> correct me if I'm wrong: the way I see it, the MatFDColoring context  
> in PETSc is always built on top of 1) the coloring (ISColoring) and  
> 2) the sparsity pattern of the underlying matrix, right?
> The thing is that I've developed my code completely separate from  
> the PETSc API, I mean, it's written in "pure" ANSI C language/MPI.  
> My goal now is to link it to the PETSc framework, so that I can  
> benefit from all the other things already implemented within PETSc.  
> As I'm not quite the expert in the "inner workings" of the PETSc  
> library, my first guess was that I would have to provide a special  
> routine to create the MatFDColoring context on each processor based  
> on the coloring I found and on how my code "represents" the sparsity  
> pattern of the jacobian matrix.
> Rafael

    There are two distinct parts of using coloring in PETSc to compute  

1) computing the coloring of the sparse matrix: done with  
MatGetColoring(), this is done in PETSc with classes allowing one to  
easily and transparently  provide new coloring algorithms.

2) using the computed coloring to actually compute a Jacobian  
(efficiently): done with MatFDColoringCreate() and its methods. This  
is hardwired in PETSc to use one particular data structure for  
actually computing the Jacobian.

What you should:

1)    Write a "wrapper" for your code that computes the coloring. It  
should have the calling sequence (Mat mat,MatColoringType  
name,ISColoring *iscoloring) you ignore the name
argument (since it is the name you select). Then you call  
MatColoringRegisterDynamic() to register it.  Now one can use it by  
simply calling  
MatGetColoring(mat,"yournameyouregisteredwith",&iscoloring); just like  
the "built in" colorings.  I would do this first because having an  
efficient parallel coloring for PETSc would be great!

2) MatFDColoring code was not designed to allow other implementations  
to be easily plugged in. (There is no MatFDColoringType to allow  
having different ways of computing this).
So you need to decide if your code that does 2) is possibly "better"  
then in PETSc, or if 1) is really the useful thing you are providing.  
If you want to also provide 2) then write new routines
MyMatFDColoringCreate(), MyFDColoringDestroy(), MatFDColoringApply()  
etc with the same calling sequences as PETSc's and make them wrappers  
to call your code (do not try to reproduce the data structures inside  
the MatFDColoring data structure (use whatever data structures you  
currently use), why because if you use the same data structure then  
you are just rewriting MatFDColoringCreate() to do what it already  
does, the only reason to use your own is if it uses its own data  
structures that may be better then in PETSc. If you do write MyMatFD..  
routines etc and they are as good or better then PETSc's then we will  
change PETSc's MatFDColoringCreate() code to support multiple  
instances (that is introduce a MatFDColoringType) and your new  
MyMatFDColoring stuff would be registratable.

    Hope this clarifies things, feel free to direct further questions  
to petsc-dev at since that is the mailing list for people  
extending PETSc code.


More information about the petsc-users mailing list