[IPOL announce] new article: An Analysis and Implementation of Multigrid Poisson Solvers With Verified Linear Complexity

[announcements about the IPOL journal]

A new article is available in IPOL: http://www.ipol.im/pub/art/2018/228/

Matías Di Martino, and Gabriele Facciolo,
An Analysis and Implementation of Multigrid Poisson Solvers With 
Verified Linear Complexity,
Image Processing On Line, 8 (2018), pp. 192–218.
https://doi.org/10.5201/ipol.2018.228

Abstract
The Poisson equation is the most studied partial differential equation, 
and it allows to formulate many useful image processing methods in an 
elegant and efficient mathematical framework. Using different variations 
of data terms and boundary conditions, Poisson-like problems can be 
developed, e.g., for local contrast enhancement, inpainting, or image 
seamless cloning among many other applications. Multigrid solvers are 
among the most efficient numerical solvers for discrete Poisson-like 
equations. However, their correct implementation relies on: (i) the 
proper definition of the discrete problem, (ii) the right choice of 
interpolation and restriction operators, and (iii) the adequate 
formulation of the problem across different scales and layers. In the 
present work we address these aspects, and we provide a mathematical and 
practical description of multigrid methods. In addition, we present an 
alternative to the extended formulation of Poisson equation proposed in 
2011 by Mainberger et al. The proposed formulation of the problem suits 
better multigrid methods, in particular, because it has important 
mathematical properties that can be exploited to define the problem at 
different scales in a intuitive and natural way. In addition, common 
iterative solvers and Poisson-like problems are empirically analyzed and 
compared. For example, the complexity of problems is compared when the 
topology of Dirichlet boundary conditions changes in the interior of the 
regular domain of the image. The main contribution of this work is the 
development and detailed description of an implementation of a multigrid 
numerical solver which converges in linear time.