Analysis of a nearly-linear time Laplacian solver and its application in finite element method

Solving linear system is of fundamental importance in science and engineering. Recent researches lead to the development of fast algorithms to solve symmetric diagonally dominant (SDD) linear systems. One extremely important class of matrices that is SDD are called Laplacian matrices of graphs. There are many real life applications where such systems need to be solved. These come, for example, from solving partial differential, applications in networks (Link prediction, recommendation system, protein interaction networks, ...), applications in computer vision (image denoising, image impainting, image segmentation, ...) and many others. There exists various SDD solvers that work empirically well for specific applications. However, they often do not generalize well for other problems. Moreover, the existing SDD solvers lack theoretical guarantees on their performances. The recent researches lead to the creation of algorithms called combinatorial preconditioner with provably good running time. Very briefly, a combinatorial preconditioner of the Laplacian matrix L_G of a graph G is the Laplacian matrix L_H of a subgraph H of G with some additional edges. It was a breakthrough from Vaidya in 1990 that allowed to design an algorithm with provably good bounds ! There have been many combinatorial preconditioners since the first idea emerged. The most important one came from Spielman and Teng, who were able to create the first ever almost-linear time algorithm to solve SDD systems, ie the solver has a total complexity of O(n log^c n) for some huge constant c. All the solvers that followed then optimized the value of this constant. These were crucial in the design of the solver of Koutis, Miller and Peng (KMP) which has a theoretical complexity of O(m log n). This solver has never been implemented and will be the main focus of this thesis. The algorithms that generate the preconditioner work as follows: they start by generating a good subtree of the system and then add some of the important edges to the tree based on some algorithm. The subtree is called a low-stretch spanning tree. It is the key to obtaining the almost-linear run-time. The preconditioner is easier to solve and leads to the resolution of a much smaller system, which is then solved recursively. By controlling the quality and the size of the successive smaller systems, it is possible to prove that the solver runs in almost-linear time. This master thesis extensively tests and analyzes every part of the KMP algorithm in practice. Then, the solver is tested on concrete applications arising from finite element method.