Sparsification of rectangular matrices (Q1264423)

The central problem treated in this paper is to construct an invertible square matrix \(T\) such that \(TA\), where \(A \in R^{n,m}\), \(m>n\), contains as many zero entries as possible. Three important observations concerning the nature of the problem are presented. A combinatorial search method is proposed to find an optimal sparsification. The number of arithmetic operations is exponential in the worst case. The most important improvement to this method is the exploitation of block structure. The several new theoretical results about block decomposition, its recognizing and sparsification based on this block decomposition are achieved. An open problem is the question if sparsification is indeed NP-complete. The problem of sparsification is relevant in many areas of application. The two practical examples illustrate where sparsification can be useful.