Matthijs Bomhoff — Open Problems Related to Perfect Elimination Bipartite Graphs
| Time: | Thursday, November 11, 2010 |
| Location: | Room 101, Citadel |
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 in the process. It has been known for several decades that the recognition of this class of graphs or matrices takes polynomial time. Several related problems however appear to be still open. This talk will briefly discuss three such problems we are currently looking into:
- Given a square {0,1}-matrix M, what is the smallest number of zeroes we need to turn into ones before M admits perfect elimination? This problem is closely related to the "best" Gaussian elimination scheme for the matrix with respect to the space required to store intermediate results.
- Given a non-square {0,1}-matrix M with more columns than rows, is there a subset of the columns of M that together form a perfect elimination square matrix? This problem is related to efficiently solving under-specified systems of linear equations where some variables can be fixed before solving the remainder.
- Given a square {0,1}-matrix M, can we perform perfect elimination on M using "partial pivots"? (I.e., instead of clearing an entire row/column in one go, we pick a new pivot for every single element we turn to zero.)