JCJC SIMI 1 - JCJC - SIMI 1 - Mathématiques et interactions

Numerical Schemes using Lattice Basis Reduction – NS-LBR

Numerical Schemes using Lattice Basis Reduction

In this project, we will develop, study, and distribute in open source software, new methods for the discretization of anisotropic Partial Differential Equations (PDEs) on two or three dimensional grids.

Objective: efficient discretizations of anisotropic PDE via adequate stencil constructions

We will focus on the setting where at least one of the operators involved in the PDE is anisotropic, in the sense that it involves position dependent, non axis- aligned, privileged directions. Grid discretizations are natural in medical image or volume processing, and numerous fundamental isotropic PDE operators are known to have efficient representations in this form.<br />Discretizing anisotropic PDE operators on grids is regarded as a challenging task, because natural approaches involving the classical isotropic stencils (i.e. made of k-nearest grid neighbors), typically face issues of accuracy, performance, and stability. We intend to address this technological lock, by constructing new anisotropic stencils specifically tailored for the discretization of anisotropic PDE operators.<br />

Our strategy for the stencil construction will be based on lattice basis reduction, a classical tool from discrete geometry which allows to efficiently construct twisted bases and neighborhoods in a lattice (here the discretization grid), well adapted to an ambient geometry defined through an anisotropic metric (here given with the anisotropic PDE operator).

For anisotropic static Hamilton-Jacobi PDEs, this program has already shown some success: a variant of the classical Fast Marching algorithm, using our anisotropic stencils, is studied mathematically and numerically in recent papers of the project coordinator.
Improvements of the accuracy vs complexity compromise, between one and four (!) orders of magnitude, were reported in classical test cases for this problem over earlier state of the art. This is the end of a technological lock for some image and volume processing applications, such as the segmentation problems studied by project members Cohen and Benmansour. A significant part of the project will be devoted to the valorization of this mathematical research, by its implementation in image processing free software, and the development of image and volume processing applications.

Anisotropic diffusion is another fundamental PDE, with applications ranging from image processing to hydraulic simulation. The project coordinator and Fehrenbach have developed for this purpose a small stencil, non-negative numerical scheme, which is currently under study. Both its mathematical guarantees - discrete maximum principle, spectral correctness - and numerical properties - solution accuracy, low complexity - are extremely promising. A significant part of this project will be devoted to finishing the study of this method, implementing it in free software, and developing applications.

Prospective studies of other PDEs are also under work. An important problem in economics is the solution of variational problems under global convexity constraints. Current numerical approaches face a numerical lock, since they either have a prohibitive computational cost, or lack convergence guarantees. Early theoretical studies strongly suggest that a grid discretization, using our adaptive anisotropic stencils, could bring strong improvements. The use of our stencils in optimal transport will also be investigated.

This project is architectured around a fundamental innovation: the use of Lattice Basis Reduction in the discretization of anisotropic PDEs. It combines basic research (exploration of new PDEs), development of medical imaging applications (around anisotropic HJ and diffusion PDEs), and the distribution of code in high impact free software. These will be based on the Insight ToolKit, a C++ library known for its high quality and growing diffusion, which already incorporates contributions by project member Benmansour.

In this project, we will develop, study, and distribute in open source software, new methods for the discretization of anisotropic Partial Differential Equations (PDEs) on two or three dimensional grids. We will focus on the setting where at least one of the operators involved in the PDE is anisotropic, in the sense that it involves position dependent, non axis-aligned, privileged directions. Grid discretizations are natural in medical image or volume processing, and numerous fundamental isotropic PDE operators are known to have efficient representations in this form.

Discretizing anisotropic PDE operators on grids is regarded as a challenging task, because natural approaches involving the classical isotropic stencils (i.e. made of k-nearest grid neighbors), typically face issues of accuracy, performance, and stability. We intend to address this technological lock, by constructing new anisotropic stencils specifically tailored for the discretization of anisotropic PDE operators.
Our strategy for the stencil construction will be based on lattice basis reduction, a classical tool from discrete geometry which allows to efficiently construct twisted bases and neighborhoods in a lattice (here the discretization grid), well adapted to an ambient geometry defined through an anisotropic metric (here given with the anisotropic PDE operator).

For anisotropic static Hamilton-Jacobi PDEs, this program has already shown some success: a variant of the classical Fast Marching algorithm, using our anisotropic stencils, is studied mathematically and numerically in recent papers of the project coordinator.
Improvements of the accuracy vs complexity compromise, between one and four (!) orders of magnitude, were reported in classical test cases for this problem over earlier state of the art. This is the end of a technological lock for some image and volume processing applications, such as the segmentation problems studied by project members Cohen and Benmansour. A significant part of the project will be devoted to the valorization of this mathematical research, by its implementation in image processing free software, and the development of image and volume processing applications.

Anisotropic diffusion is another fundamental PDE, with applications ranging from image processing to hydraulic simulation. The project coordinator and Fehrenbach have developed for this purpose a small stencil, non-negative numerical scheme, which is currently under study. Both its mathematical guarantees - discrete maximum principle, spectral correctness - and numerical properties - solution accuracy, low complexity - are extremely promising. A significant part of this project will be devoted to finishing the study of this method, implementing it in free software, and developing applications.

Prospective studies of other PDEs are also under work. An important problem in economics is the solution of variational problems under global convexity constraints. Current numerical approaches face a numerical lock, since they either have a prohibitive computational cost, or lack convergence guarantees. Early theoretical studies strongly suggest that a grid discretization, using our adaptive anisotropic stencils, could bring strong improvements. The use of our stencils in transport equations will also be investigated, with the objective of reducing numerical diffusion.

This project is architectured around a fundamental innovation: the use of Lattice Basis Reduction in the discretization of anisotropic PDEs. It combines basic research (exploration of new PDEs), development of medical imaging applications (around anisotropic HJ and diffusion PDEs), and the distribution of code in high impact free software. These will be based on the Insight ToolKit, a C++ library known for its high quality and growing diffusion, which already incorporates contributions by project member Benmansour.

Project coordination

Jean-Marie MIREBEAU (Centre De Recherche en Mathématiques de la Décision, Université Paris-Dauphine)

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.

Partner

Ceremade Centre De Recherche en Mathématiques de la Décision, Université Paris-Dauphine

Help of the ANR 62,000 euros
Beginning and duration of the scientific project: June 2013 - 42 Months

Useful links

Explorez notre base de projets financés

 

 

ANR makes available its datasets on funded projects, click here to find more.

Sign up for the latest news:
Subscribe to our newsletter