A note on perfect partial elimination

M.J. Bomhoff, Walter Kern, Georg J. Still

Research output: Contribution to journalArticleAcademicpeer-review

66 Downloads (Pure)

Abstract

In Gaussian elimination it is often desirable to preserve existing zeros (sparsity). This is closely related to perfect elimination schemes on graphs. Such schemes can be found in polynomial time. Gaussian elimination uses a pivot for each column, so opportunities for preserving sparsity can be missed. In this paper we consider a more flexible process that selects a pivot for each nonzero to be eliminated and show that recognizing matrices that allow such perfect partial elimination schemes is NP-hard.
Original languageEnglish
Pages (from-to)1558-1563
Number of pages6
JournalDiscrete mathematics
Volume313
Issue number14
DOIs
Publication statusPublished - 2013

Keywords

  • EWI-23990
  • Perfect elimination
  • Bipartite graph
  • IR-87884
  • Gaussian elimination
  • METIS-300169
  • Complexity

Fingerprint

Dive into the research topics of 'A note on perfect partial elimination'. Together they form a unique fingerprint.

Cite this