Tel Aviv University, Applied Mathematics Seminar
Date:       Tuesday February 26, 2013, 15:10
Place:      Schreiber Bldg, Room 309
Speaker: Raanan Fattal, Hebrew University
Title: Efficient preconditioning for Laplacian matrices
I will present a new multi-level preconditioning scheme for discrete
Poisson equations that arise in various computer graphics
applications such as image colorization, edge-preserving
decomposition, and geodesic distances on three-dimensional meshes.
The new approach interleaves the selection of fine and coarse-level
variables with the removal of weak connections between potential
fine-level variables sparsification and the compensation for these
changes by strengthening nearby connections. 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 experiments demonstrate 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.
Webpage of the applied mathematics seminar:
Dr. Yoel Shkolnisky
Department of Applied Mathematics
School of Mathematical Sciences        phone:  972-3-640-8705
Tel Aviv University,                   fax  :  972-3-640-9357
Tel Aviv, 69978 Israel                 email:   <>
Technion Math Net-2 (TECHMATH2)
Editor: Michael Cwikel   <> 
Announcement from: Yoel Shkolnisky   <>