[petsc-dev] [petsc-maint #150081] RE: Diagonal entires in MPIAdj matrices

[Jed Brown]

This doesn't have to be specific to MATMPIADJ, and could be orthogonal to
changing the MatConvert API (which I still think is a good idea). That is,
the linear transformation A is a map from a (distributed) vector space X to
another space Y. If X=Y, then A is an endomorphism, and when interpreted as
a weighted (directed) graph, the diagonal entries are implicit (and
ParMetis can't handle them). If instead, X is different from Y, then the
diagonal has no implicit meaning.

Should we add a MAT_ENDOMORPHISM option? (Easier name?)


On Sat, Jan 26, 2013 at 11:12 AM, Jed Brown <jedbrown at mcs.anl.gov> wrote:

> I am inclined to change the MatConvert() interface to require the caller
> to have created the dest matrix already (similar to MatLoad). In that case,
> the user would create a MATMPIADJ and set an option instructing it whether
> rows and columns denote the same graph vertices (in which case the diagonal
> is implied) or whether they form disjoint sets in a bipartite graph (in
> which case the diagonal has no special meaning and thus must be copied
> faithfully).
>
>
> On Fri, Jan 25, 2013 at 6:04 PM, Hammond, Glenn <glenn.hammond at pnnl.gov>wrote:
>
>> Some more detail:
>>
>> Bear in mind that the arrays passed to  ParMETIS_V3_Mesh2Dual()
>> essentially represent entries within rectangular adjacency matrices:
>>
>> N_elements x N vertices
>>
>> Or
>>
>> N_cells x N connections
>>
>> If an element and vertex or cell and connection have the same id, they
>> will have a diagonal entry.  When I read in the explicit grid, I set up a
>> AIJ matrix of size N_cells x N_connections.  For every connection, I fill
>> in two entries (one for each cell) in the corresponding column.  I then
>> convert to an Adj matrix and sent it off to ParMETIS.  However, during the
>> MatConvert process, diagonal entries are being removed (which changeset
>> 1bdcc2952450 prevented).
>>
>> Thanks,
>>
>> Glenn
>>
>> -----Original Message-----
>> From: Hammond, Glenn
>> Sent: Friday, January 25, 2013 3:18 PM
>> To: Barry Smith
>> Cc: petsc-maint at mcs.anl.gov; Gautam Bisht (gbisht at lbl.gov)
>> Subject: Diagonal entires in MPIAdj matrices
>>
>> Barry,
>>
>> I see that the diagonal entries in the MPIAdj matrix that Barry added in
>> changeset 1bdcc2952450 (and requested through the discussion below) were
>> removed at the end of November (Jed's changeset from Nov 30: cl1b2d1f).
>>  Since I use the adjacency matrix to decompose and set up connectivity for
>> an explicit grid (a grid where connections are listed explicitly in the
>> input file), I need the diagonal entries back in the adjacency matrix as my
>> Adjacency matrix has num_cells rows and num_connections columns (i.e. a
>> cell id can match a column id and thus an entry on the diagonal).
>>
>> Or is there an alternative approach to resolve this issue?
>>
>> Thanks,
>>
>> Glenn
>>
>> -----Original Message-----
>> From: Barry Smith [mailto:bsmith at mcs.anl.gov]
>> Sent: Thursday, October 04, 2012 5:33 PM
>> To: Hammond, Glenn
>> Cc: petsc-maint at mcs.anl.gov
>> Subject: Re: [petsc-maint #134803] MatConvert for MATMPIAIJ -> MATMPIADJ
>>
>>
>>   Ok, the way to deal with this is to remove the diagonal entries just
>> before calling the "broken" ParMETIS V3 PartMeshKway() and which ever other
>> ones are broken.
>>
>>    Barry
>>
>> On Oct 4, 2012, at 7:02 PM, Barry Smith <bsmith at mcs.anl.gov> wrote:
>>
>> >
>> >  Goddamn that stupid George!
>> >
>> >   Ok, too late, its been pushed so now ParMETIS V3 PartMeshKway will
>> break.
>> >
>> >   We can't have a completely different matrix type just because George
>> is an imbecile who should not be allowed to write code.
>> >
>> >   Barry
>> >
>> > On Oct 4, 2012, at 4:46 PM, "Hammond, Glenn" <glenn.hammond at pnnl.gov>
>> wrote:
>> >
>> >> Thanks.  I will test this.
>> >>
>> >> I looked into the ParMETIS docs and ParMETIS_V3_Mesh2Dual() is
>> designed solely for meshes where elements are defined through a list of
>> vertices.  In other words, rectangular matrices where diagonal entries will
>> potentially exist.
>> >>
>> >> However, I fear that altering the MATMPIADJ will lead to bugs
>> elsewhere where diagonals are ignored or should not be considered (e.g.
>> line 65 of src/mat/partition/impls/pmetis/pmetis.c).  I fear that this is
>> the issue for ParMETIS V3 PartMeshKway().
>> >>
>> >> Perhaps a new matrix type, MATMPIMESH where the matrix defines a mesh
>> by elements (rows) and vertices (cols)...?  Then, the adjacency matrix does
>> not need to include the diagonal.
>> >>
>> >> I have to agree that the ParMETIS docs are not clear on this!
>> >>
>> >> Glenn
>> >>
>> >>
>> >>
>> >>> -----Original Message-----
>> >>> From: Barry Smith [mailto:bsmith at mcs.anl.gov]
>> >>> Sent: Thursday, October 04, 2012 2:12 PM
>> >>> To: petsc-maint at mcs.anl.gov; Hammond, Glenn
>> >>> Subject: Re: [petsc-maint #134803] MatConvert for MATMPIAIJ ->
>> >>> MATMPIADJ
>> >>>
>> >>>
>> >>>   Ok, changed petsc-dev to include diagonals in the adjacency matrix
>> >>>
>> >>>
>> >>> On Oct 4, 2012, at 1:51 PM, "Hammond, Glenn"
>> >>> <glenn.hammond at pnnl.gov> wrote:
>> >>>
>> >>>>> Glenn,
>> >>>>>
>> >>>>>  The reason I wrote it originally to skip diagonals was because
>> >>>>> Metis/Parmetis crashed if you gave it diagonal entries at that time!
>> >>>>>
>> >>>>>   So, what do we need? Sometimes have diagonal entries, sometime
>> >>> not?
>> >>>>> How to know when? Does Metis/parmetis still not like diagonal
>> >>>>> entries
>> >>> when
>> >>>>> partitioning?   We can certainly change this but we need more
>> information
>> >>>>> about use cases and what we should change it to.
>> >>>>
>> >>>> I propose that we include diagonals in the adjacency matrix.  The
>> >>>> adjacency
>> >>> matrices that I have been using for several years now with the
>> >>> implicit mesh formation include the diagonals and ParMetis has not
>> >>> complained.  The question is whether others are using MatConvert and
>> will this affect them.
>> >>> If we want to be backwards compatible, can we add a flag and a
>> >>> function call to set the flag?
>> >>>>
>> >>>> Glenn
>> >>>>
>> >>>>>
>> >>>>>
>> >>>>> Barry
>> >>>>>
>> >>>>>
>> >>>>> On Oct 4, 2012, at 12:07 PM, "Hammond, Glenn"
>> >>>>> <glenn.hammond at pnnl.gov> wrote:
>> >>>>>
>> >>>>>> PETSc,
>> >>>>>>
>> >>>>>> I am using MatConvert() to convert a MATMPIAIJ to a MATMPIADJ.
>> >>>>>> In
>> >>>>> stepping through the MatConvert() routine (i.e.
>> >>>>> MatConvertFrom_MPIAdj), I notice that diagonal entries are ignored:
>> >>>>>>
>> >>>>>>
>> >>>>>> /* count the number of nonzeros per row */  for (i=0; i<m; i++) {
>> >>>>>> ierr   = MatGetRow(A,i+rstart,&len,&rj,PETSC_NULL);CHKERRQ(ierr);
>> >>>>>> for (j=0; j<len; j++) {
>> >>>>>> -->    if (rj[j] == i+rstart) {len--; break;}    /* don't count
>> diagonal */
>> >>>>>> }
>> >>>>>> ierr   =
>> >>> MatRestoreRow(A,i+rstart,&len,&rj,PETSC_NULL);CHKERRQ(ierr);
>> >>>>>> nzeros += len;
>> >>>>>> }
>> >>>>>>
>> >>>>>> which would be fine if my matrix were NxN.  However, my AIJ
>> >>>>>> matrix is
>> >>>>> rectangular (MxN, or # cells X # connections), and therefore, I
>> >>>>> need diagonal entries in my MATMPIADJ matrix.  Am I missing
>> >>>>> something? I know that several years ago, Barry had to go in and
>> >>>>> fix MATMPIADJ for rectangular matrices so that they would include
>> the diagonal (see below).
>> >>>>>>
>> >>>>>> Thanks,
>> >>>>>>
>> >>>>>> Glenn
>> >>>>>>
>> >>>>>> From 10/1/2009
>> >>>>>>
>> >>>>>> Glenn,
>> >>>>>>
>> >>>>>>
>> >>>>>>
>> >>>>>> Ok, I do not understand this properly. I didn't even know this
>> >>>>>> mesh matrix
>> >>>>> was rectangular. The Metis users manual is short on detail.
>> >>>>>>
>> >>>>>> I will have to spend more time to understand what Metis does and
>> >>>>>> fix up
>> >>>>> things for you.
>> >>>>>>
>> >>>>>>
>> >>>>>>
>> >>>>>> Barry
>> >>>>>>
>> >>>>>>
>> >>>>
>> >>>>
>> >>
>> >
>>
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20130126/934b32c6/attachment.html>