Options
Block computation and representation of a sparse nullspace basis of a rectangular matrix
Publikationstyp
Journal Article
Date Issued
2008-01-25
Sprache
English
Author(s)
Volume
428
Issue
11-12
Start Page
2455
End Page
2467
Citation
Linear Algebra and Its Applications 428 (11-12): 2455-2467 (2008-06-01)
Publisher DOI
Scopus ID
Publisher
American Elsevier Publ.
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 BT with B ∈ Rn × m, n > m. We assume that B has full rank, i.e., rank(B) = m. It is well-known that the last n - m 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.
Subjects
Block QR factorization
Hierarchical matrices
Orthogonal factorization
DDC Class
510: Mathematik