Options
Block computation and representation of a sparse nullspace basis of a rectangular matrix
Publikationstyp
Journal Article
Publikationsdatum
2008-01-25
Sprache
English
Author
Enthalten in
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. © 2007 Elsevier Inc. All rights reserved.
Schlagworte
Block QR factorization
Hierarchical matrices
Orthogonal factorization
DDC Class
510: Mathematik