Householder QR decomposition for rectangular matrices. More...
#include "config.h"#include "fused/fused_matrix.h"#include "fused/fused_vector.h"#include "math/math_utils.h"
Include dependency graph for qr.h:
This graph shows which files directly or indirectly include this file:
Go to the source code of this file.
Classes | |
| struct | matrix_algorithms::QRResult< T, M, N > |
| Result of Householder QR decomposition. More... | |
Namespaces | |
| namespace | matrix_algorithms |
Functions | |
| template<typename T , my_size_t M, my_size_t N> | |
| QRResult< T, M, N > | matrix_algorithms::qr_householder (const FusedMatrix< T, M, N > &A) |
| Compute the Householder QR decomposition of a rectangular matrix. | |
Detailed Description
Householder QR decomposition for rectangular matrices.
Decomposes A (M×N, M≥N) into Q·R where:
- Q is M×M orthogonal (Qᵀ·Q = I)
- R is M×N upper triangular
Compact storage stores R in the upper triangle and Householder vectors below the diagonal (with implicit leading 1), plus a tau vector of scaling factors. Q() and R() extract the full matrices when needed.
ALGORITHM
For each column j = 0 … N−1:
- Compute the norm of the sub-column A(j:M−1, j)
- Choose α = −sign(A(j,j))·‖sub-column‖ (avoids cancellation)
- Form Householder vector v: v(0) = A(j,j)−α, v(i) = A(i,j) for i>j
- Normalize: store v(i)/v(0) below diagonal, adjust τ = 2·v(0)²/(vᵀv)
- Apply reflection H = I − τ·v·vᵀ to remaining columns j+1…N−1
- Store R(j,j) = α on the diagonal
Q is recovered by accumulating the Householder reflections in reverse order.
Complexity: O(2MN² − 2N³/3) for the factorization. O(2M²N − 2MN²/3) additionally to form Q.
NOTES
- QR is infallible — every matrix has a valid QR decomposition.
- The sign convention ensures numerical stability (no catastrophic cancellation in v(0)).
- For least squares, Q is not needed explicitly — apply Qᵀb via the stored Householder vectors, then back-substitute with R.
