A note on perfect partial elimination

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

A note on perfect partial elimination

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

Discrete Mathematics and Mathematical Programming

Research output: Book/Report › Report › Professional

112 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 language	Undefined
Place of Publication	Enschede
Publisher	University of Twente, Department of Applied Mathematics
Number of pages	8
Publication status	Published - Dec 2011

Publication series

Name	Memorandum / Department of Applied Mathematics
Publisher	University of Twente, Department of Applied Mathematics
No.	1971
ISSN (Print)	1874-4850
ISSN (Electronic)	1874-4850

Keywords

IR-79127
Complexity
Perfect elimination
METIS-284946
Gaussian elimination
Bipartite graph
EWI-21127

Access to Document

http://www.math.utwente.nl/publications

Cite this

@book{c904c18f996643d892f1e437c53afb6b,

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 = "IR-79127, Complexity, Perfect elimination, METIS-284946, Gaussian elimination, Bipartite graph, EWI-21127",

author = "M.J. Bomhoff and Walter Kern and Still, {Georg J.}",

note = "eemcs-eprint-21127 ",

year = "2011",

month = dec,

language = "Undefined",

series = "Memorandum / Department of Applied Mathematics",

publisher = "University of Twente, Department of Applied Mathematics",

number = "1971",

}

TY - BOOK

T1 - A note on perfect partial elimination

AU - Bomhoff, M.J.

AU - Kern, Walter

AU - Still, Georg J.

N1 - eemcs-eprint-21127

PY - 2011/12

Y1 - 2011/12

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 - IR-79127

KW - Complexity

KW - Perfect elimination

KW - METIS-284946

KW - Gaussian elimination

KW - Bipartite graph

KW - EWI-21127

M3 - Report

T3 - Memorandum / Department of Applied Mathematics

BT - A note on perfect partial elimination

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -