Recent advances on the Augmented Block Cimmino method

(Conférencier invité)International audienceThe classical block Cimmino method belongs to the class of block rowprojection methods, and is designed to solve non symmetric large sparse systems of linear equations. Its appealing features are that it presents very natural parallelism, and can be accelerated with conjugate gradient techniques. Its convergence speed depends strongly on the principal angles between the subspaces spanned by the blocks of rows from the initial partitioning of the system, and can be slow in many cases. The "Augmented Block Cimmino" method is a way to bypass this inherent limitation by embedding the original partitionned system of equations into a larger one, so as to enforce numerical orthogonality between the corresponding blocks of rows in the enlarged system of equations. Doing so, we can ensure a convergence in one iteration only, but at the expense of the increase in size and extra work induced by operating on the resulting enlarged system. In this presentation, we recall the major principles of this approach, and we also extend this to nding the least-squares solution of overdetermined systems of equations. We also consider novel ways for partitionning the system that takes into account the numerical values and replicate some of the equations to improve the convergence. Finally, we also present variations on the above augmentation process, which is indeed purely algebraic, and can be expensive or even prohibitive depending on the application. In the case of discretized PDE problems, we investigate alternatives for this augmentation, which will target explicitly geometric information from the problem, exploiting multigrid ideas to construct the enlarged system. The idea is not to enforce strict orthogonality but open suciently the angles between sub-spaces. The convergence of the classical iterative method could then be improved greatly while keeping a more scalable approach altogether(in terms of computations and memory needs)