Timeline for sparsity of QR decomposition
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 17, 2012 at 13:36 | comment | added | Brian Borchers | If you want to use this sparse QR "factorization" to solve $\min \| Ax-b \|$, the procedure is to first apply the Givens rotations to reduce $A$ to $R$, possibly reordering the columns of $A$ to minimize fill-in in the $R$ matrix. As you do these Givens rotations you also apply them to $b$ to obtain $Q^{T}b$. Then you solve the triangular system $Rx=Q^{T}b$ to obtain the least squares solution. There is lots of available software for performing these computations. | |
| Apr 17, 2012 at 13:32 | comment | added | Brian Borchers | The typical case in which sparse QR factorization is used is where $A$ is of size $m$ by $n$, $m \gg n$, and $A$ has full column rank. In this situation, $Q$ would be $m$ by $m$ and typically dense with nonzeros, but the effect of multiplication by $Q$ can be achieved by using sequences of Givens rotations. So $Q$ isn't stored explicitly. It is also possible to order the columns of $A$ to reduce the nonzero fill-in in the $R$ matrix. | |
| Apr 17, 2012 at 3:16 | history | edited | Brian Borchers | CC BY-SA 3.0 |
Removed "or all" before "columns of the orthogonal matrix"
|
| Apr 16, 2012 at 13:33 | history | answered | Brian Borchers | CC BY-SA 3.0 |