Search Results

Documents authored by Duff, Iain S.


Document
Combinatorial problems in solving linear systems

Authors: Iain S. Duff and Bora Ucar

Published in: Dagstuhl Seminar Proceedings, Volume 9061, Combinatorial Scientific Computing (2009)


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.

Cite as

Iain S. Duff and Bora Ucar. Combinatorial problems in solving linear systems. In Combinatorial Scientific Computing. Dagstuhl Seminar Proceedings, Volume 9061, pp. 1-37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@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/entities/document/10.4230/DagSemProc.09061.8},
  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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail