Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing

Ioannis Koutis, Gary L. Miller, David Tolliver

Research output: Contribution to journalArticlepeer-review

81 Scopus citations


Several algorithms for problems including image segmentation, gradient inpainting and total variation are based on solving symmetric diagonally dominant (SDD) linear systems. These algorithms generally produce results of high quality. However, existing solvers are not always efficient, and in many cases they operate only on restricted topologies. The unavailability of reliably efficient solvers has arguably hindered the adoptability of approaches and algorithms based on SDD systems, especially in applications involving very large systems. A central claim of this paper is that SDD-based approaches can now be considered practical and reliable. To support our claim we present Combinatorial Multigrid (CMG), the first reliably efficient SDD solver that tackles problems in general and arbitrary weighted topologies. The solver borrows the structure and operators of multigrid algorithms, but embeds into them powerful and algebraically sound combinatorial preconditioners, based on novel tools from support graph theory. In order to present the derivation of CMG, we review and exemplify key notions of support graph theory that can also guide the future development of specialized solvers. We validate our claims on very large systems derived from imaging applications. Finally, we outline two new reductions of non-linear filtering problems to SDD systems and review the integration of SDD systems into selected algorithms.

Original languageEnglish (US)
Pages (from-to)1638-1646
Number of pages9
JournalComputer Vision and Image Understanding
Issue number12
StatePublished - Dec 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition


  • Eigensolvers
  • Linear system solvers
  • Multigrid
  • Multilevel methods
  • Preconditioning


Dive into the research topics of 'Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing'. Together they form a unique fingerprint.

Cite this