[petsc-users] Using edge-weights for partitioning

[Eda Oktay]

Okay, thank you so much!

Eda

On Sun, Aug 30, 2020, 9:36 PM Jose E. Roman <jroman at dsic.upv.es> wrote:

> The user interface of Chaco includes an argument for edge weights (don't
> know which methods within Chaco take them into account). The original PETSc
> wrapper to Chaco was developed by a student of mine (together with Scotch,
> Party and Jostle) at around 2003. At that time, MatPartitioning only had
> support for vertex weights (edge weight support has been introduced very
> recently), so we just passed a NULL in this argument.
>
> Jose
>
>
> > El 30 ago 2020, a las 16:35, Barry Smith <bsmith at petsc.dev> escribió:
> >
> >
> >
> >> On Aug 30, 2020, at 2:57 AM, Eda Oktay <eda.oktay at metu.edu.tr> wrote:
> >>
> >> Dear Matt,
> >>
> >> First of all I figured out that I asked wrongly. It's not ParMETIS
> giving the same result. It is CHACO. ParMETIS gives different results when
> I use edge weights.
> >>
> >> Thanks!
> >>
> >> Dear Barry,
> >>
> >> I am trying to partition the matrix to compare the edge cuts when it is
> partitioned with CHACO, ParMETIS and the spectral partitioning algorithm
> with the k-means clustering (I wrote this code in PETSc).  In the end, I
> will conclude that if a linear system is to be solved and the coefficient
> matrix is large in size, then partitioning the coefficient matrix by using
> one of these algorithms will help one to solve the linear system faster and
> with small communication.
> >>
> >> What is forcing matrix to have all positive values? Isn't it done by
> using MatPartitioningGetUseEdgeWeights and MatPartitioningSetUseEdgeWeights?
> >>
> >> I will send the test case but I am already passing my original matrix
> directly to SetAdjacency (SymmA is my symmetric matrix with positive
> values):
> >>
> >>   ierr =
> MatConvert(SymmA,MATMPIADJ,MAT_INITIAL_MATRIX,&AL);CHKERRQ(ierr);
>
> >>   ierr = MatPartitioningCreate(MPI_COMM_WORLD,&part);CHKERRQ(ierr);
> >>   ierr = MatPartitioningSetAdjacency(part,AL);CHKERRQ(ierr);
> >>    ierr = MatPartitioningSetFromOptions(part);CHKERRQ(ierr);
> >
> >   You should not need this. Just
> >
> >     ierr = MatPartitioningCreate(MPI_COMM_WORLD,&part);CHKERRQ(ierr);
> >     ierr = MatPartitioningSetAdjacency(part,SymmA);CHKERRQ(ierr);
> >     ierr = MatPartitioningSetFromOptions(part);CHKERRQ(ierr);
> >
> >
> >   MatPartitioningSetAdjacency takes any MatType directly.
> >
> >
> >>
> >> So, if ParMETIS gives different edge cut as it is expected,
> MatPartitioningGetUseEdgeWeights and MatPartitioningSetUseEdgeWeights works
> correctly. Why can't CHACO?
> >>
> >> Thanks!
> >>
> >> Eda
> >>
> >> Barry Smith <bsmith at petsc.dev>, 30 Ağu 2020 Paz, 03:00 tarihinde şunu
> yazdı:
> >>
> >>
> >> > On Aug 29, 2020, at 2:23 PM, Eda Oktay <eda.oktay at metu.edu.tr> wrote:
> >> >
> >> > Hi all,
> >> >
> >> > I am trying to partition a sparse matrix by using ParMETIS. I am
> converting my matrix to adjacency type and then applying partitioning.
> >>
> >>  You don't need to do this. Just pass your original matrix directly
> into MatPartitioningSetAdjacency() it will handle any conversions needed.
> >>
> >>  Edge weights need to be positive, since they represent how much
> communication is to take place over that link. You may need to force your
> matrix to have all positive values before giving it to
> MatPartitioningSetAdjacency and using edge weights.
> >>
> >>   I this doesn't work than our code is broken, please send us a simple
> test case
> >>
> >>   Question: Why are you partitioning a matrix? Is it for load balancing
> of solves or matrix vector products with the matrix? To reduce interprocess
> communication during solves or matrix vector products with the matrix? If
> so the numerical values in the matrix don't affect load balance or
> interprocess communication for these operations.
> >>
> >>
> >>   Barry
> >>
> >>
> >>
> >>
> >> > Default, I understood that partitioning doesn't use edge-weights.
> However, when I used the following codes I saw from ex15 and used
> "-test_use_edge_weights 1", I am getting the same results as when I don't
> consider edge weights.
> >> >
> >> > PetscBool use_edge_weights=PETSC_FALSE;
> >> >
>  PetscOptionsGetBool(NULL,NULL,"-test_use_edge_weights",&use_edge_weights,NULL);
> >> >   if (use_edge_weights) {
> >> >       MatPartitioningSetUseEdgeWeights(part,use_edge_weights);
> >> >
> >> >       MatPartitioningGetUseEdgeWeights(part,&use_edge_weights);
> >> >       if (!use_edge_weights)
> SETERRQ(PETSC_COMM_SELF,PETSC_ERR_ARG_INCOMP, "use_edge_weights flag does
> not setup correctly \n");
> >> >     }
> >> >
> >> > My matrix does not consist of 1s and 0s, so I want partitioning to
> consider all the nonzero elements in the matrix as edge weights. Don't
> MatPartitioningSetUseEdgeWeights and MatPartitioningGetUseEdgeWeights do
> that? Should I add something more? In the page of
> MatPartitioningSetUseEdgeWeights, it is written that "If set
> use_edge_weights to TRUE, users need to make sure legal edge weights are
> stored in an ADJ matrix.". How can I make sure of this?
> >> >
> >> > I am trying to compare the use of ParMETIS with the spectral
> partitioning algorithm when I used a weighted Laplacian.
> >> >
> >> > Thanks!
> >> >
> >> > Eda
> >> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20200830/f885ab0e/attachment.html>