A note on perfect partial elimination

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

Research output: Contribution to journalArticleAcademicpeer-review

35 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

Fingerprint

Elimination
Gaussian elimination
Pivot
Polynomials
Sparsity
Partial
Polynomial time
NP-complete problem
Zero
Graph in graph theory

Keywords

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

Cite this

Bomhoff, M.J. ; Kern, Walter ; Still, Georg J. / A note on perfect partial elimination. In: Discrete mathematics. 2013 ; Vol. 313, No. 14. pp. 1558-1563.
@article{beb2f7a5c2394b53b64fb8ea21f8fd31,
title = "A note on perfect partial elimination",
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.",
keywords = "EWI-23990, Perfect elimination, Bipartite graph, IR-87884, Gaussian elimination, METIS-300169, Complexity",
author = "M.J. Bomhoff and Walter Kern and Still, {Georg J.}",
note = "eemcs-eprint-23990",
year = "2013",
doi = "10.1016/j.disc.2013.04.001",
language = "English",
volume = "313",
pages = "1558--1563",
journal = "Discrete mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "14",

}

A note on perfect partial elimination. / Bomhoff, M.J.; Kern, Walter; Still, Georg J.

In: Discrete mathematics, Vol. 313, No. 14, 2013, p. 1558-1563.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - A note on perfect partial elimination

AU - Bomhoff, M.J.

AU - Kern, Walter

AU - Still, Georg J.

N1 - eemcs-eprint-23990

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - EWI-23990

KW - Perfect elimination

KW - Bipartite graph

KW - IR-87884

KW - Gaussian elimination

KW - METIS-300169

KW - Complexity

U2 - 10.1016/j.disc.2013.04.001

DO - 10.1016/j.disc.2013.04.001

M3 - Article

VL - 313

SP - 1558

EP - 1563

JO - Discrete mathematics

JF - Discrete mathematics

SN - 0012-365X

IS - 14

ER -