## Combinatorial problems in solving linear systems

### Iain S. Duff and Bora Uçar

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.

Key words.
Combinatorial scientific computing, graph theory, combinatorial optimization, sparse matrices, linear system solution.