Block computation and representation of a sparse nullspace basis of a rectangular matrix

✍ Scribed by Sabine Le Borne

• Publisher: Elsevier Science
• Year: 2008
• Tongue: English
• Weight: 179 KB
• Volume: 428
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/j.laa.2007.11.025

✦ Synopsis

In this paper, we propose a new method to efficiently compute a representation of an orthogonal basis of the nullspace of a sparse matrix operator B T with B ∈ R n×m , n > m. We assume that B has full rank, i.e., rank(B) = m. It is well known that the last nm columns of the orthogonal matrix Q in a QR factorization B = QR form such a desired null basis. The orthogonal matrix Q can be represented either explicitly as a matrix, or implicitly as a matrix H of Householder vectors. Typically, the matrix H represents the orthogonal factor much more compactly than Q. We will employ this observation to design an efficient block algorithm that computes a sparse representation of the nullspace basis in almost optimal complexity. This new algorithm may, e.g., be used to construct a null space basis of the discrete divergence operator in the finite element context, and we will provide numerical results for this particular application.