Graphs and a Multilevel Preconditioner for the Conjugate Gradient Method
The students explored the conjugate gradient method, an iterative algorithm that solves linear systems with symmetric positive-definite coefficient matrices. Using C++ they implemented and compared different preconditioners. A recursive multilevel method was introduced, for which METIS graph partitioning and parallel coarsening based on Luby's graph matching algorithm were used. Because the multilevel method converged in few iterations, it was applied to large sparse matrices coming from network datasets with over a million nodes. To improve time performance further, OpenMP was used to parallelize some matrix operations such as matrix-vector multiplication. Then the computations were carried out on the Coeus Cluster. Former PSU postdoc Kirill Voronin presented a lecture on OpenMP programming to the students. At the end of the project they gave presentations of their work. Links to the slides and code of each participant are below their photos.