A geometric framework for sparse matrix problems

In this paper, we set up a geometric framework for solving sparse matrix problems. We introduce geometric sparseness, a notion which applies to several well-known families of sparse matrix. Two algorithms are presented for solving geometrically-sparse matrix problems. These algorithms are inspired by techniques in classical algebraic topology, and involve the construction of a simplicial complex from certain data on the matrix. In both cases, large parts of the computation can be parallelised. [Copyright &y& Elsevier]