Recognizing sparse perfect elimination bipartite graphs

M.J. Bomhoff

Research output: Book/ReportReportProfessional

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

Publication series

NameMemorandum / Department of Applied Mathematics
PublisherDepartment of Applied Mathematics, University of Twente
No.1931
ISSN (Print)1874-4850
ISSN (Electronic)1874-4850

Keywords

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

Cite this