Preconditioning Techniques Based on the Birkhoff–von Neumann Decomposition

Michele Benzi (1) , Bora Uçar (2, 3)

1 Department of Mathematics and Computer Science [Emory University]
2 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
3 LIP - Laboratoire de l'Informatique du Parallélisme

We introduce a class of preconditioners for general sparse matrices based on the Birkhoff-von Neumann decomposition of doubly stochastic matrices. These precondi- tioners are aimed primarily at solving challenging linear systems with highly unstructured and indefinite coefficient matrices. We present some theoretical results and numerical experiments on linear systems from a variety of applications.

Nous introduisons une classe de préconditionnement pour matrices creuses générales fondées sur la décomposition de Birkhoff–von Neumann des matrices bistochastiques. Ces préconditionnements visent principalement à résoudre des systèmes linéaires difficiles dont les matrices sont non-structurées et non-définies. Nous présentons quelques résultats théoriques et des expériences numériques pour des systèmes linéaires issus de tout un ensemble d’applications.

Mots clés: Birkhoff–von Neumann decomcoposition; doubly stochastic matrix; preconditioning

Mots clés: décomposition de Birkhoff-von Neumann; préconditionnement; matrices bistochastiques

Domaines: Mathématique discrète [cs.DM]; Algorithme et structure de données [cs.DS]; Analyse numérique [math.NA]; Combinatoire [math.CO]

Michele Benzi, Bora Uçar. Preconditioning Techniques Based on the Birkhoff–von Neumann Decomposition. Computational Methods in Applied Mathematics, 2016, ⟨10.1515/cmam-2016-0040⟩. ⟨hal-01318486v4⟩