The Taub Faculty of Computer Science Events and Talks

I will present a new multi-level preconditioning scheme for Laplacian matrices that arise in various computer vision and mathematical physics applications. The new approach combines principles from the multigrid and combinatorial preconditioning methodologies in order to overcome various shortcomings. In a first step, the new method adaptively eliminates a set of uncoupled variables from the linear system and by that simplifies the solution of nearly half of the variables in the system. A recursive application of this elimination step over the remaining variables leads to a computationally-unacceptable growth in the number of non-zero matrix elements. To avoid this growth, we introduce a novel adaptive matrix sparsification procedure that carefully removes non-zero elements from the matrix. In addition, we derive a new compensation rule that minimizes the error due to sparsification by modifying the remaining matrix elements. By applying these operations before each elimination step and repeating the procedure recursively on the resulting smaller systems, we obtain a highly efficient multi-level preconditioning scheme with linear time and memory requirements. The derivation of this scheme is based on formal insights that motivate its algorithmic design. (br>(br> Experiments show that the new scheme outperforms or equals other state of the art methods, both in terms of operation count and wall-clock time. This speedup is achieved by the new method's ability to reduce the condition number of irregular Laplacian matrices as well as homogeneous systems. It can therefore be used for a wide variety of problems, including 3D meshes, without the need to carefully match the algorithm to the problem characteristics. (br> (br> This is a joint work with: Dilip Krishnan and Rick Szeliski.