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 sparse linear system solutions, we
will cover combinatorial problems, notions, and algorithms relating to
those computations.

This talk is thus concerned with direct and iterative methods for sparse 
linear systems and their intercation with combinatorial optimization.
On the direct methods side, we discuss 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 factor preconditioners
(notion of level of fill-in), support graph preconditioners (graph
embedding concepts), and algebraic multigrids (independent sets in
undirected graphs).

In a separate part of the talk, we discuss methods that aim to exploit
sparsity during linear system solution. These methods include block
diagonalization of the matrix; efficient triangular system solutions
for right-hand side vectors of single nonzero entries. Towards the
end, we mention, quite briefly as they are topics of other invited
talks, some other areas whose interactions with combinatorial
optimization are of great benefit to numerical linear algebra.  These
include graph and hypergraph partitioning for load balancing problems,
and colouring problems in numerical optimization. On closing, we
compile and list a set of open problems.