North-Holland A hierarchical algorithm for making sparse matrices sparser

If A is the (sparse) coefficient matrix of linear equality constraints, for what nonsingular T is fil ~- TA as sparse as possible, and how can it be efficiently computed? An efficient algorithm for this Sparsity Problem (SP) would be a valuable pre-processor for linearly constrained optimization problems. In this paper we develop a two-pass approach to solve SP. Pass 1 builds a combinatorial structure on the rows of A which hierarchically decomposes them into blocks. This determines the structure of the optimal transformation matrix T. In Pass 2, we use the information about T as a road map to do block-wise partial Gauss-Jordan elimination on A. Two block-aggregation strategies are also suggested that could further reduce the time spend in Pass 2. Computational results indicate that this approach to increasing sparsity produces ignificant net reductions in simplex solution time. O