Re: [boost] My ideas for GSoC project

Subject: Re: [boost] My ideas for GSoC project
From: Bal¹a Raièeviæ (balsa.raicevic_at_[hidden])
Date: 2009-04-05 16:28:07

Hello again,
As I was asked to be more specific than I was in my proposal I am sending
you this addition, which is also posted as a comment at my proposal page.

Regards,
Balsa

I'll be glad to give more details. Like stated in my proposal, my idea would
be to discuss all the algorithms with all interested parties before
implementing them, so these would be just some of my ideas.

In many current graph partitioning packages the multilevel partitioning is
included. For me, this is where I would start, since from studies I've seen,
high quality partitions with moderate computational complexity are produced
with this approach.

Multilevel partitioning has 3 phases: coarsening, partitioning and
uncoarsening.

To coarsen a graph for me the best solution would be the edge collapsing.
METIS reduces the size of the graph by collapsing vertices and edges using a
heavy-edge matching scheme. Some other heuristics for coarsening the graph
iteratively, could also be implemented (random matching or gain vertex
matching).

The partitioning algorithm would probably be some sort of a recursive
bisection algorithm. I know also METIS uses greedy graph growing algorithm.

For uncoarsening and refinement phase, my choice would be Kernighan - Lin
heuristic. It seems to me that multilevel algorithms that adopt K-L during
the uncoarsening and refinement phase are proven to be superior.

Like I said, multilevel algorithms would be primary, but expanding The BGL
with some geometric or spectral partitioning algorithms could be very useful
for some users.

Since the main purpose of partitioning is the prospect of implementing the
application code on parallel machines, the logical next step would be to
include parallel partitioning similar to ParMETIS.

Also, like stated in my proposal, if the hypergraph data structure gets
developed by then, I would like to implement some partitioning algorithms on
hypergraphs.

I am aware that implementing, testing, optimizing and documenting all this
would be too much for a duration of GSoC,so I would put my priorities in
multilevel partitioning on existing graph data structures in The BGL, and if
time allows or afterwards get to other ideas.

Thank you very much for taking interest and I'll be glad to answer any
further questions regarding this proposal.

Regards,

Balsa

On Tue, Mar 31, 2009 at 10:46 AM, Bal¹a Raièeviæ
<balsa.raicevic_at_[hidden]>wrote:

> Hello,
>
> I'm a Computer Science student from Faculty of Mathematics, University of
> Belgrade. I am interested in working on The BGL. I have a lot of experience
> with C++ and code refactoring also, since I've done a lot of tutoring and
> encountered a lot of strange students' code :)
>
> I have taken a deep look at BGL ( which is why I'm writing my proposal so
> late :) ) and to some extend its extension - The Parallel Boost Graph
> Library.
>
> I am mostly interested in graph partitioning, as I find them very useful
> for parallel computing. I understood the importance of it when I had to do
> some major calculations for numerical approximations and wanted to use all
> the CPU power available :)
>
> In the project idea list (
> https://svn.boost.org/trac/boost/wiki/soc2009#Graphpartitioning) it's said
> that it would be good to implement algorithms similar to those in METIS (
> http://www.cs.umn.edu/~metis <http://www.cs.umn.edu/%7Emetis>).  I've read
> some of George Karypis' "Publications Related to Graph Partitioning", so I
> was wondering if I could discuss with someone which algorithms would be good
> to implement, and of course, how. I found little, if any, discussion about
> that in mailing list archive.
>
> Other thing I would really like to see is hypergraph partitioning. I see
> that implementing hypergraphs in the BGL is one of GSoC projects, so I would
> like to know would it be possible, if that project is not awarded to anyone
> for this summer, to do basic implementation of a hypergraph, or (since I
> see there is already a discussion about that) if somebody else would do that
> project, to collaborate on hypergraph partitioning algorithms.
>
> Last, but not least, an important question: I would like to use this work
> as part of my Master's Thesis. I looked at GSoC FAQ (
> http://socghop.appspot.com/document/show/program/google/gsoc2009/faqs#course_credit),
> so I guess it is OK with the program, but I would still like to discuss it
> with potential mentor.
>
> Thanks ahead,
> Balsa
>