# Recognizing sparse perfect elimination bipartite graphs

M.J. Bomhoff

Research output: Book/ReportReportProfessional

67 Downloads (Pure)

## Abstract

When applying Gaussian elimination to a sparse matrix, it is desirable to avoid turning zeros into non-zeros to preserve the sparsity. The class of perfect elimination bipartite graphs is closely related to square matrices that Gaussian elimination can be applied to without turning any zero into a non-zero. Existing literature on the recognition of this class and finding suitable pivots mainly focusses on time complexity. For $n \times n$ matrices with m non-zero elements, the currently best known algorithm has a time complexity of $O(n^3/\log n)$. However, when viewed from a practical perspective, the space complexity also deserves attention: it may not be worthwhile to look for a suitable set of pivots for a sparse matrix if this requires $\Omega(n^2)$ space. We present two new algorithms for the recognition of sparse instances: one with a $O(n m)$ time complexity in $\Theta(n^2)$ space and one with a $O(m^2)$ time complexity in $\Theta(m)$ space. Furthermore, if we allow only pivots on the diagonal, our second algorithm can easily be adapted to run in time $O(n m)$.
Original language Undefined Enschede University of Twente, Department of Applied Mathematics 12 Published - Dec 2010

### Publication series

Name Memorandum / Department of Applied Mathematics Department of Applied Mathematics, University of Twente 1931 1874-4850 1874-4850

• IR-75140
• METIS-276210
• EWI-19049