Some Results on Structure Prediction in Sparse $QR$ Factorization
| Autor: | Barry W. Peyton, Esmond G. Ng |
|---|---|
| Rok vydání: | 1996 |
| Předmět: | |
| Zdroj: | SIAM Journal on Matrix Analysis and Applications. 17:443-459 |
| ISSN: | 1095-7162 0895-4798 |
| DOI: | 10.1137/s0895479892230973 |
| Popis: | In $QR$ factorization of an $m \times n$ matrix $A$ ($m \geq n$), the orthogonal factor $Q$ is often stored implicitly as an $m \times n$ lower trapezoidal matrix $W$, known as the Householder matrix. When the sparsity of $A$ is to be exploited, the factorization is often preceded by a symbolic factorization step, which computes a data structure in which the nonzero entries of $W$ and $R$ are computed and stored. This is achieved by computing an upper bound on the nonzero structure of these factors, based solely on the nonzero structure of $A$. In this paper we use a well-known upper bound on the nonzero structure of $W$ to obtain an upper bound on the nonzero structure of $Q$. Let $U$ be the matrix consisting of the first $n$ columns of $Q$. One interesting feature of the new bound is that the bound on $W$'s structure is identical to the lower trapezoidal part of the bound on $U$'s structure. We show that if $A$ is strong Hall and has no zero entry on its main diagonal, then the bounds on the nonzero structures of $W$ and $U$ are the smallest possible based solely on the nonzero structure of $A$. We then use this result to obtain corresponding smallest upper bounds in the case where $A$ is weak Hall, is in block upper triangular form, and has no zero entry on its main diagonal. Finally, we show that one can always reorder a weak Hall matrix into block upper triangular form so that there is no increase in the fill incurred by the $QR$ factorization. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|