[petsc-dev] proposed minor PetscPartitioner changes

Vaclav Hapla vaclav.hapla at erdw.ethz.ch
Fri Nov 10 17:09:15 CST 2017

> 10. 11. 2017 v 22:34, Jed Brown <jed at jedbrown.org>:
> Vaclav Hapla <vaclav.hapla at erdw.ethz.ch> writes:
>>>> Yes. Mat can represent any graph in several different ways -
>>>> e.g. Laplacian, adjacency, incidence, oriented incidence matrix. The
>>>> graph could be also represented in other way like a list of vertices
>>>> and edges. 
>>> Also known as COO format for a matrix.
>> You could represent by COO any of the matrices above. I don't understand how it relates to listing vertices and edges of a graph.
> COO is literally a list of edges.  

For the adjacency matrix of a weighted graph this is true.

> Square matrices and graphs are the
> same thing.
>>>> MatPartitioning picks just one representation as an input - the
>>>> adjacency matrix. But I mean the picked representation does not
>>>> matter, and the result is not a partitioning of any matrix, but
>>>> partitioning of the graph. The graph is the underlying concept. This
>>>> is why I don't consider the Mat prefix optimal.
>>> Matrix and graph are equivalent concepts.  
>> I think that's an overly strong statement. It sounds like a matrix and a graph are bijectively interchangeable things which is certainly not true:
>> 1) As I mentioned, there are multiple ways of representing a graph by a matrix, and for a given graphs these matrix representations don't even have the same dimensions.
>> 2) Even if you stick to the adjacency matrix (which you apparently do), it's still not bijective with the graph - the adjacency matrix is a square symmetric Boolean matrix. You can just say that the _sparse pattern_ of the _symmetric_ matrix is bijective with the respective graph. This is a by far weaker statement.
> Graphs can have edge weights.  

Weighted graphs are already an extension. But OK.

> A symmetric matrix is an undirected
> graph.  A nonsymmetric matrix is a directed graph.

OK. And non-square matrices are graphs?
Matrices definitely "are" linear operators. Are graphs linear operators?

>> Why you then have a special matrix type MATMPIADJ which is value-less 
> MatCreateMPIAdj literally has an argument named "values".

This argument is optional the same way as graphs are optionally weighted. But OK.

>> and automatically symmetric if all matrices "are" graphs?
> It is not "automatically symmetric" -- you have to declare that with
> MatSetOption as documented in the man page.

Fair. But it is automatically square at least.

>  A partitioner for an
> undirected graph may require that the input is symmetric, much like how
> CG will fail if the input is not SPD.

More information about the petsc-dev mailing list