CMU-CS-13-121Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-13-121
Richard Peng August 2013 Ph.D. Thesis
Keywords:
Combinatorial Preconditioning, Linear System Solvers, Spectral Graph Theory,
Parallel Algorithms, Low Stretch Embeddings, Image Processing
Spectral graph theory is the interplay between linear algebra and combinatorial graph theory. Laplace's equation and its discrete form, the Laplacian matrix, appear ubiquitously in mathematical physics. Due to the recent discovery of very fast solvers for these equations, they are also becoming increasingly useful in combinatorial optimization, computer vision, computer graphics, and machine learning.
In this thesis, we develop highly efficient and parallelizable algorithms
for solving linear systems involving graph Laplacian matrices. These solvers
can also be extended to symmetric diagonally dominant matrices and We give two solver algorithms that take diametrically opposite approaches. The first is motivated by combinatorial algorithms, and aims to gradually break the problem into several smaller ones. It represents major simplifications over previous solver constructions, and has theoretical running time comparable to sorting. The second is motivated by numerical analysis, and aims to rapidly improve the algebraic connectivity of the graph. It is the first highly efficient solver for Laplacian linear systems that parallelizes almost completely. Our results improve the performances of applications of fast linear system solvers ranging from scientific computing to algorithmic graph theory. We also show that these solvers can be used to address broad classes of image processing tasks, and give some preliminary experimental results 180 pages
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |