Recognizing sparse perfect elimination bipartite graphs
Bomhoff, Matthijs (2010) Recognizing sparse perfect elimination bipartite graphs. [Report]

PDF
142kB 
Abstract:  When applying Gaussian elimination to a sparse matrix, it is desirable to avoid turning zeros into nonzeros 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 nonzero. Existing literature on the recognition of this class and finding suitable pivots mainly focusses on time complexity. For matrices with m nonzero elements, the currently best known algorithm has a time complexity of . 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 space. We present two new algorithms for the recognition of sparse instances: one with a time complexity in space and one with a time complexity in space. Furthermore, if we allow only pivots on the diagonal, our second algorithm can easily be adapted to run in time . 
Item Type:  Report 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/75140 
Publisher URL:  http://www.math.utwente.nl/publications 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page