TY - BOOK

T1 - Recognizing sparse perfect elimination bipartite graphs

AU - Bomhoff, M.J.

PY - 2010/12

Y1 - 2010/12

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

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

KW - IR-75140

KW - METIS-276210

KW - EWI-19049

M3 - Report

T3 - Memorandum / Department of Applied Mathematics

BT - Recognizing sparse perfect elimination bipartite graphs

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -