[petsc-users] Using edge-weights for partitioning

[Matthew Knepley]

On Sun, Aug 30, 2020 at 3:58 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.
>

ParMetis is the only partitioner that can use edge weights I believe.

  Thanks,

     Matt


> 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);
>
> 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
>> >
>>
>>

-- 
What most experimenters take for granted before they begin their
experiments is infinitely more interesting than any results to which their
experiments lead.
-- Norbert Wiener

https://www.cse.buffalo.edu/~knepley/ <http://www.cse.buffalo.edu/~knepley/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20200830/72df8192/attachment.html>