Duff, Iain S. ;
Ucar, Bora
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 fillin), 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 righthand 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.
BibTeX  Entry
@InProceedings{duff_et_al:DSP:2009:2077,
author = {Iain S. Duff and Bora Ucar},
title = {Combinatorial problems in solving linear systems},
booktitle = {Combinatorial Scientific Computing},
year = {2009},
editor = {Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
number = {09061},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2077},
annote = {Keywords: Combinatorial scientic computing, graph theory, combinatorial optimization, sparse matrices, linear system solution}
}
Keywords: 

Combinatorial scientific computing, graph theory, combinatorial optimization, sparse matrices, linear system solution 
Seminar: 

09061  Combinatorial Scientific Computing

Issue date: 

2009 
Date of publication: 

24.07.2009 