Justin Buhendwa Nyenyezi (UNamur)

Title: Polynomial preconditioners versus matrix-splitting preconditioners for linear systems arising in 3D medical image registration

Abstract: Many methods exist to solve large sparse linear systems. However, a given method may perform well for a particular problem while it may not work as well for another [2]. For designing ecient system solvers, one may analyze structures of general operators or matrices used by the algorithms. In non-rigid medical image registration, matrices are derived from physical principles, modelled as Partial Dierential Equations (PDEs). Although these systems are often sparse and structured, they are very large and ill-conditioned. Thus, their solvers are time consuming and their complexity in operation counts is polynomial. As a consequence, fast and superfast direct methods reveal numerical instabilities and thus lead to breakdowns or inaccurate solutions. The most used alternative are iterative system solvers that enable a reduction of the number of expensive operations such as matrix-vector products and thus a speed up of the registration process. Although iterative solvers provide only an approximation of the solution, they are well suited for very large systems when cheap and well suited preconditioners are available. Preconditioners may be stationary (Jacobi, Gauss-Seidel or SOR) and non-stationary (e.g, polynonmial or low-rank inverse approximation).
In this study, we are especially interested in benchmarking [3, 4] iterative system solvers on a large set of 3D medical images. These system solvers are based on the Conjugate Gradient method but dierent from the preconditioning techniques [6, 5] . The ongoing results conrm [4] that there is no single system solver that is the best for all the problems. However, the results indicate which solver has the highest probability of being the best within a factor f ∈ [1, ∞[ and considering a limited computional budget in terms of time and storage require-
ments.
References
[1] Oseledets, Ivan and Tyrtyshnikov, Eugene and Zamarashkin, Nickolai. Evaluation of optimization methods for nonrigid medical image registration using mutual information and B-splines. Image Processing, IEEE Transactions on, 16:12,28792890, 2007.
[2] Barrett, Richard and & all. Templates for the solution of linear systems: building blocks for iterative methods. SIAM , 1994.
[3] Moré, Jorge J and Wild, Stefan M. Benchmarking derivative-free optimization algorithms. SIAM Journal on Optimization , 20:1,172191, 2009.
[4] Gould, Nicholas and Scott, Jennifer. The State-of-the-Art of Preconditioners for Sparse Linear Least-Squares Problems. ACM Transactions on Mathematical Software (TOMS) , 43:4,36, 2017.
[5] Nocedal, Jorge and Wright, Stephen J. Numerical optimization. Springer New York , 2, 2006.
[6] SAAD,Yousef Iterative methods for sparse linear systems. Society for Industrial and Applied Mathematics , 2003.