Timeline for Why do we need orthonormal basis of Krylov subspaces for GMRES?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 5, 2017 at 13:14 | answer | added | Christian Clason | timeline score: 2 | |
| Jul 3, 2017 at 11:30 | comment | added | Christian Clason | Well, if you copy all the neat tricks of GMRES (column-wise update of Hessenberg form and QR factorization, delayed solution of triangular system), you end up with an algorithm with at best cosmetic differences, so what you're proposing is in the end not very different. The standard approach is likely more stable, though, since you orthogonalize each new Krylov basis vector as soon as you compute it instead of first forming $A^{m-1}r_0$ (which converges to the dominant eigenvector of $A$ for $m\to\infty$). Fundamentally, it's the difference between Gram-Schmidt and modified Gram-Schmidt. | |
| Jul 3, 2017 at 8:38 | comment | added | Hui Zhang | But note that $H_m$ was obtained by the Arnoldi process which costs about the same as the Householder for $AX_m$. | |
| Jul 3, 2017 at 8:11 | comment | added | Christian Clason | Another thing which I thought was obvious but is worth pointing out is that $H_{m}$ is an $(m+1)\times m$ matrix, while $AX_m$ is an $n\times m$ matrix. In practice, $m\ll n$ (think $m=10$ versus $n=10^4$). This also has bearing on your comment: Of course Householder can do it, but Givens is much more efficient in this case. | |
| Jul 3, 2017 at 7:35 | comment | added | Hui Zhang | "The first step in any practical QR decomposition is to transform the matrix to upper Hessenberg form". But Householder can directly do QR without the first step. "Also, the practical implementation of the GMRES algorithm ...". With my proposal, I think I can also postpone solving the least square problem-- just doing the Householder for the new column each time. | |
| Jul 3, 2017 at 6:50 | comment | added | Christian Clason | The first step in any practical QR decomposition is to transform the matrix to upper Hessenberg form, which the Arnoldi process gives you for free. Also, the practical implementation of the GMRES algorithm makes use of the QR decomposition of $H_m$ (actually, the extended matrix) to compute the decomposition of $H_{m+1}$ with a single Givens rotation and postpones actually solving the least squares system until the residual would be small enough. All this exploits the properties of the Arnoldi process. | |
| Jul 3, 2017 at 4:54 | history | edited | Hui Zhang | CC BY-SA 3.0 |
corrected subscript
|
| Jul 3, 2017 at 4:22 | history | asked | Hui Zhang | CC BY-SA 3.0 |