### 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

## Cite this

Bomhoff, M. J., Kern, W., & Still, G. J. (2011).

*A note on perfect partial elimination*. (Memorandum / Department of Applied Mathematics; No. 1971). Enschede: University of Twente, Department of Applied Mathematics.