New Horizons

This blog entry will be entirely dedicated to a subject that absorbed me for more than one year: support graph preconditioners . When one have to solve say a laplacian equation on a mesh the numerical discretization  the problem to solve is generally of the form Ax=b, where A is a sparse matrix with many zero entries. More importantly the non-zero entries have a pattern direclty inherited from the mesh connectivity. For linear elements, (i,j) entry is non void if and only if there is an edge between node i and node j (what's cool with the laplacian is that a node is a degree of freedom). So, as long as the mesh has a moderate connectivity pattern, the matrix inherits  that pattern and is therefore relatively sparse. If you factorize your matrix with a direct solver then the work your computer has to do is directly linked to the connectivity of the underlying mesh. For instance if the underlying mesh is a tree , then the complexity of the direct solver will be linear with r...