Collaborators
Projects
- PETSc Implementation of the LAMG partitioner
- PETSc Implementation of the Miller-Teng partitioner
Get SC paper by Raghavan and Miller-Teng (in Mendeley). We just need an embedding of our exsiting coordinates to the sphere ("lifting").
Considerations:
- Spectral Bisection
- High quality
- Must play games to get k partitions
- Multilevel k-way
- Like Bisection-type on the coarse level
- Kernighan-Lin as a smoother
- Random walk
- Nibble algorithm of Shang-Hua and Dan
- Makes lots of small pieces with low conductance
- How is this related to low-stretch stuff?
- What are the partitioning costs?
- High synchronization cost
- Current models are inaccurate
- What are the partitioning requirements?
- Better model of computation weights
- Better model of interconnects (contention)
- Add dynamism to partition?
- Update the partition and weights
- Feedback from computation
- Spectral Bisection
Finished Projects
- MG for power-law graphs
Analysis
We compared to LAMG and it was superior in every case. It turns out that the matrix structure was not as big an impediment as we thought.Motivation
A scalable multigrid solver for graph Laplacian problems on power law graphs would represent a significant advance for computational learning, graph analysis, and theory. Currently, no effective coarsening method method exists for multigrid.
Background
Based on an idea from Fan Chung, which characterizes a power-law graph as one with a power-law degree distribution. I have this in my Mendeley account. She shows that such a graph has a large planar component, which can be extracted by subtracting edges.
Project
- Form a vertex partition based upon this edge partition and prove this is still large.
- Run standard MG on the large planar part
- Use block elimination (Schur complement) for the remaining edges