[petsc-users] Using edge-weights for partitioning

[Eda Oktay]

Dear Barry,

I attached test code and a small binary matrix whose elements are less than
10 which you can use to test. In the code, as an output, the index set
"partitioning" will be given. As you will see, when ParMETIS is used, index
set changes when edge weights are used, whereas when the option changes to
chaco, index set remains the same.

Thanks!

Eda

Eda Oktay <eda.oktay at metu.edu.tr>, 30 Ağu 2020 Paz, 11:05 tarihinde şunu
yazdı:

> And is edge weights being less than 10 still valid? Although I am not
> getting any errors, when the elements in my matrix are larger than 10, even
> ParMETIS doesn't give different results.
>
> Eda Oktay <eda.oktay at metu.edu.tr>, 30 Ağu 2020 Paz, 10:57 tarihinde şunu
> yazdı:
>
>> 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);
>>
>> 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/e25ea691/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test_adj.zip
Type: application/zip
Size: 2408 bytes
Desc: not available
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20200830/e25ea691/attachment.zip>