[petsc-dev] proposed minor PetscPartitioner changes

[Jed Brown]

Vaclav Hapla <vaclav.hapla at erdw.ethz.ch> writes:

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

Partitioners can use non-uniform edge weights so if you had a
PetscGraph, it would have to support non-uniform weights.

>> 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?

Laplacians are usually written as

  L = diag(A * 1) - A

where A is the adjacency matrix and 1 is the vector of all ones (so A*1
is the vector of row sums).  There is no question that the Laplacian is
a linear operator.  If we compute a factorization L U = A, we almost
never have a reason to multiply by L (we solve with it, i.e., apply
L^{-1}), but I think we would all agree that it is a linear operator.
So yes, I would say a graph is a linear operator.

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

Sure.  The input to almost all KSPs also must be square.  We don't have
a special type for a square matrix.