Combinatorial problems in solving linear systems

Abstract : Numerical linear algebra and combinatorial optimization are vast subjects; as is their interaction. In virtually all cases there should be a notion of sparsity for a combinatorial problem to arise. Sparse matrices therefore form the basis of the interaction of these two seemingly disparate subjects. As the core of many of today's numerical linear algebra computations consists of the solution of sparse linear system by direct or iterative methods, we survey some combinatorial problems, ideas, and algorithms relating to these computations. On the direct methods side, we discuss issues such as matrix ordering; bipartite matching and matrix scaling for better pivoting; task assignment and scheduling for parallel multifrontal solvers. On the iterative method side, we discuss preconditioning techniques including incomplete factorization preconditioners, support graph preconditioners, and algebraic multigrid. In a separate part, we discuss the block triangular form of sparse matrices.
Type de document :
Pré-publication, Document de travail
42 pages, available as LIP research report RR-2009-15. 2011
Liste complète des métadonnées

Littérature citée [159 références]  Voir  Masquer  Télécharger
Contributeur : Bora Uçar <>
Soumis le : mardi 12 avril 2011 - 18:09:36
Dernière modification le : samedi 21 avril 2018 - 01:27:24


Fichiers produits par l'(les) auteur(s)


  • HAL Id : ensl-00411638, version 3



Iain Duff, Bora Uçar. Combinatorial problems in solving linear systems. 42 pages, available as LIP research report RR-2009-15. 2011. 〈ensl-00411638v3〉



Consultations de la notice


Téléchargements de fichiers