License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09061.8
URN: urn:nbn:de:0030-drops-20779
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2077/
Go to the corresponding Portal

Duff, Iain S. ; Ucar, Bora

Combinatorial problems in solving linear systems

pdf-format:
09061.DuffIain.Paper.2077.pdf (0.3 MB)

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.

BibTeX - Entry

@InProceedings{duff_et_al:DagSemProc.09061.8,
  author =	{Duff, Iain S. and Ucar, Bora},
  title =	{{Combinatorial problems in solving linear systems}},
  booktitle =	{Combinatorial Scientific Computing},
  pages =	{1--37},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9061},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2009/2077},
  URN =		{urn:nbn:de:0030-drops-20779},
  doi =		{10.4230/DagSemProc.09061.8},
  annote =	{Keywords: Combinatorial scientific computing, graph theory, combinatorial optimization, sparse matrices, linear system solution}
}

Keywords: Combinatorial scientific computing, graph theory, combinatorial optimization, sparse matrices, linear system solution
Collection: 09061 - Combinatorial Scientific Computing
Issue Date: 2009
Date of publication: 24.07.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI