A note on perfect partial elimination

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

Research output: Book/ReportReportProfessional

112 Downloads (Pure)


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 languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages8
Publication statusPublished - Dec 2011

Publication series

NameMemorandum / Department of Applied Mathematics
PublisherUniversity of Twente, Department of Applied Mathematics
ISSN (Print)1874-4850
ISSN (Electronic)1874-4850


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

Cite this