  This is the first of two papers to describe a matrix sparsification algorithm
that takes a general real or complex matrix as input and produces a sparse
output matrix of the same size. The non-zero entries in the output are chosen
to minimize changes to the singular values and singular vectors corresponding
to the near null-space of the input. The output matrix is constrained to
preserve left and right null-spaces exactly. The sparsity pattern of the output
matrix is automatically determined or can be given as input.
  If the input matrix belongs to a common matrix subspace, we prove that the
computed sparse matrix belongs to the same subspace. This works without
imposing explicit constraints pertaining to the subspace. This property holds
for the subspaces of Hermitian, complex-symmetric, Hamiltonian, circulant,
centrosymmetric, and persymmetric matrices, and for each of the skew
counterparts.
  Applications of our method include computation of reusable sparse
preconditioning matrices for reliable and efficient solution of high-order
finite element systems. The second paper in this series describes our
open-source implementation, and presents further technical details.
