Xavier Vasseur : June 13, 2006

On the computation of the null space of a sparse matrix.

Abstract

Computing the null space basis of a rectangular matrix is a specific task needed in some applications e.g. in constrained optimization. The knowledge of a null space basis is also sometimes required in modern advanced iterative methods for the solution of large linear systems. In this talk we will first briefly review the main strategies when the matrix is dense. We then focus on methods for sparse matrices and present two approaches. Their main computational kernel will be a sparse LU factorization with partial pivoting. Finally we will analyse experimentally their behaviour on a set of rank deficient sparse matrices.