Efficient preconditioning for Laplacian systems

Efficient and practical tree preconditioning for solving Laplacian systems

(Luca Castelli Aleardi, Maks Ovsjankov and Alexandre Nolin)

We consider the problem of designing efficient iterative methods for solving linear systems. In its full generality, this is one of the oldest problems in numerical analysis with a tremendous number of practical applications. We focus on a particular type of linear systems, associated with Laplacian matrices of undirected graphs, and study a class of iterative methods for which it is possible to speed up the convergence through combinatorial preconditioning. We consider a class of preconditioners, known as tree preconditioners, introduced by Vaidya, that have been shown to lead to asymptotic speed-up in certain cases. Rather than trying to improve the structure of the trees used in preconditioning, we propose a very simple modification to the basic tree preconditioner, which can significantly improve the performance of the iterative linear solvers in practice. We show that our modification leads to better conditioning for some special graphs, and provide extensive experimental evidence for the decrease in the complexity of the preconditioned conjugate gradient method for several graphs, including 3D meshes and complex networks.

(14th International Symposium, SEA 2015, Paris, France, June 29 – July 1, 2015, Springer LNCS, www)

Data sets (2d meshes and complex networks)

2D meshes in OFF format (made available by AIM@SHAPE project)
Complex networks (from Stanford Large Network Dataset Collection)

Solving (random) laplacian systems on 2d meshes

Libraries to download:

Jcg.jar: Jcg library (java library for computational geometry, by L. Castelli Aleardi and S. Oudot)
JMatComp.jar: Java Matrix Computations library (java library for linear algebra computations: it provides sparse matrix representations and iterative linear solvers for laplacian systems, by L. Castelli Aleardi, M. Ovsjanikov and A. Nolin)
TC.jar (for dealing with input/output)

Files to download (for tests and benchmarks)

TestJMCLInearSolver.jar: a runnable .jar file for testing and comparing iterative linear solvers (its include all required java libraries)
(optional) TestJMCLinearSolver.java (source code)
config_linear-solvers.txt: config file containing all input parameters.

Usage example (from a Terminal):

java -jar TestJMCLinearSolver.jar config_linear-solvers.txt

Output example:

Reading config file: config_linear-solvers.txt
input_mesh		OFF/aphro.off
solver_method		-JTPCG
spanning_tree		max
precision		0.000001
verbosity		1
random_seed		10

Initializing iterative linear solver: tree diagonal preconditioner
Input file: OFF/aphro.off
Reading mesh graph from file...done (46096 vertices, 92188 faces)
Computing edge weights (geometric)...done
Solving linear system of size 46096
	 - Preconditioned Conjugate Gradient: solved in 532 turns, dist = 9.959453296712046E-7
Linear system solved
Checking solution (iterative solver)... ok
norm(Ax-b)=9.959453313310549E-7
Computation time: 3.752915577 seconds