Dear Richard, >From now on, I am actually trying to write a parallel k-means algorithm by using petsc routines (I don't have to use petsc but I believe it will be easier) and I used the algorithm you mentioned before about finding cluster centroids. However, something is bothering me:
You said that by using MPI_Allreduce, I should "calculate the global element wise sum of all the local sums and finally divide by the number of members of that cluster to get the centroid." But if I do it this way, I think each cluster centroid will be the same, right? But when I read the k-means algorithm, I thought that each cluster centroid should be different since elements in each cluster are different. Can you enlighten me? Thanks! Eda Mills, Richard Tran <[email protected]>, 30 Nis 2020 Per, 02:07 tarihinde şunu yazdı: > > Hi Eda, > > Thanks for your reply. I'm still trying to understand why you say you need to > duplicate the row vectors across all processes. When I have implemented > parallel k-means, I don't duplicate the row vectors. (This would be very > unscalable and largely defeat the point of doing this with MPI parallelism in > the first place.) > > Earlier in this email thread, you said that you have used Matlab to get > cluster IDs for each row vector. Are you trying to then use this information > to calculate the cluster centroids from inside your PETSc program? If so, you > can do this by having each MPI rank do the following: For cluster i in 0 to > (k-1), calculate the element-wise sum of all of the local rows that belong to > cluster i, then use MPI_Allreduce() to calculate the global elementwise sum > of all the local sums (this array will be replicated across all MPI ranks), > and finally divide by the number of members of that cluster to get the > centroid. Note that MPI_Allreduce() doesn't work on PETSc objects, but simple > arrays, so you'll want to use something like MatGetValues() or MatGetRow() to > access the elements of your row vectors. > > Let me know if I am misunderstanding what you are aiming to do, or if I am > misunderstanding something. > > It sounds like you would benefit from having some routines in PETSc to do > k-means (or other) clustering, by the way? > > Best regards, > Richard > > On 4/29/20 3:47 AM, Eda Oktay wrote: > > Dear Richard, > > I am trying to use spectral clustering algorithm by using k-means clustering > algorithm at some point. I am doing this by producing a matrix consisting of > eigenvectors (of the adjacency matrix of the graph that I want to partition), > then forming row vectors of this matrix. This is the part that I am using > parallel vector. By using the output from k-means, I am trying to cluster > these row vectors. To cluster these vectors, I think I need all row vectors > in all processes. I wanted to use sequential vectors, however, I couldn't > find a different way that I form row vectors of a matrix. > > I am trying to use VecScatterCreateToAll, however, since my vector is > parallel crated by VecDuplicateVecs, my input is not in correct type, so I > get error. I still can't get how can I use this function in parallel vector > created by VecDuplicateVecs. > > Thank you all for your help. > > Eda > > Mills, Richard Tran <[email protected]>, 7 Nis 2020 Sal, 01:51 tarihinde şunu > yazdı: >> >> Hi Eda, >> >> I think that you probably want to use VecScatter routines, as Junchao >> has suggested, instead of the lower level star forest for this. I >> believe that VecScatterCreateToZero() is what you want for the broadcast >> problem you describe, in the second part of your question. I'm not sure >> what you are trying to do in the first part. Taking a parallel vector >> and then copying its entire contents to a sequential vector residing on >> each process is not scalable, and a lot of the design that has gone into >> PETSc is to prevent the user from ever needing to do things like that. >> Can you please tell us what you intend to do with these sequential vectors? >> >> I'm also wondering why, later in your message, you say that you get >> cluster assignments from Matlab, and then "to cluster row vectors >> according to this information, all processors need to have all of the >> row vectors". Do you mean you want to get all of the row vectors copied >> onto all of the processors so that you can compute the cluster >> centroids? If so, computing the cluster centroids can be done without >> copying the row vectors onto all processors if you use a communication >> operation like MPI_Allreduce(). >> >> Lastly, let me add that I've done a fair amount of work implementing >> clustering algorithms on distributed memory parallel machines, but >> outside of PETSc. I was thinking that I should implement some of these >> routines using PETSc. I can't get to this immediately, but I'm wondering >> if you might care to tell me a bit more about the clustering problems >> you need to solve and how having some support for this in PETSc might >> (or might not) help. >> >> Best regards, >> Richard >> >> On 4/4/20 1:39 AM, Eda Oktay wrote: >> > Hi all, >> > >> > I created a parallel vector UV, by using VecDuplicateVecs since I need >> > row vectors of a matrix. However, I need the whole vector be in all >> > processors, which means I need to gather all and broadcast them to all >> > processors. To gather, I tried to use VecStrideGatherAll: >> > >> > Vec UVG; >> > VecStrideGatherAll(UV,UVG,INSERT_VALUES); >> > VecView(UVG,PETSC_VIEWER_STDOUT_WORLD); >> > >> > however when I try to view the vector, I get the following error. >> > >> > [3]PETSC ERROR: Invalid argument >> > [3]PETSC ERROR: Wrong type of object: Parameter # 1 >> > [3]PETSC ERROR: See >> > http://www.mcs.anl.gov/petsc/documentation/faq.html for trouble shooting. >> > [3]PETSC ERROR: Petsc Release Version 3.11.1, Apr, 12, 2019 >> > [3]PETSC ERROR: ./clustering_son_final_edgecut_without_parmetis on a >> > arch-linux2-c-debug named localhost.localdomain by edaoktay Sat Apr 4 >> > 11:22:54 2020 >> > [3]PETSC ERROR: Wrong type of object: Parameter # 1 >> > [0]PETSC ERROR: See >> > http://www.mcs.anl.gov/petsc/documentation/faq.html for trouble shooting. >> > [0]PETSC ERROR: Petsc Release Version 3.11.1, Apr, 12, 2019 >> > [0]PETSC ERROR: ./clustering_son_final_edgecut_without_parmetis on a >> > arch-linux2-c-debug named localhost.localdomain by edaoktay Sat Apr 4 >> > 11:22:54 2020 >> > [0]PETSC ERROR: Configure options --download-mpich --download-openblas >> > --download-slepc --download-metis --download-parmetis --download-chaco >> > --with-X=1 >> > [0]PETSC ERROR: #1 VecStrideGatherAll() line 646 in >> > /home/edaoktay/petsc-3.11.1/src/vec/vec/utils/vinv.c >> > ./clustering_son_final_edgecut_without_parmetis on a >> > arch-linux2-c-debug named localhost.localdomain by edaoktay Sat Apr 4 >> > 11:22:54 2020 >> > [1]PETSC ERROR: Configure options --download-mpich --download-openblas >> > --download-slepc --download-metis --download-parmetis --download-chaco >> > --with-X=1 >> > [1]PETSC ERROR: #1 VecStrideGatherAll() line 646 in >> > /home/edaoktay/petsc-3.11.1/src/vec/vec/utils/vinv.c >> > Configure options --download-mpich --download-openblas >> > --download-slepc --download-metis --download-parmetis --download-chaco >> > --with-X=1 >> > [3]PETSC ERROR: #1 VecStrideGatherAll() line 646 in >> > /home/edaoktay/petsc-3.11.1/src/vec/vec/utils/vinv.c >> > >> > I couldn't understand why I am getting this error. Is this because of >> > UV being created by VecDuplicateVecs? How can I solve this problem? >> > >> > The other question is broadcasting. After gathering all elements of >> > the vector UV, I need to broadcast them to all processors. I found >> > PetscSFBcastBegin. However, I couldn't understand the PetscSF concept >> > properly. I couldn't adjust my question to the star forest concept. >> > >> > My problem is: If I have 4 processors, I create a matrix whose columns >> > are 4 smallest eigenvectors, say of size 72. Then by defining each row >> > of this matrix as a vector, I cluster them by using k-means >> > clustering algorithm. For now, I cluster them by using MATLAB and I >> > obtain a vector showing which row vector is in which cluster. After >> > getting this vector, to cluster row vectors according to this >> > information, all processors need to have all of the row vectors. >> > >> > According to this problem, how can I use the star forest concept? >> > >> > I will be glad if you can help me about this problem since I don't >> > have enough knowledge about graph theory. An if you have any idea >> > about how can I use k-means algorithm in a more practical way, please >> > let me know. >> > >> > Thanks! >> > >> > Eda > >
