Givens rotation-based 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_givens.h:
Go to the source code of this file.
Classes | |
| struct | matrix_algorithms::GivensQRResult< T, M, N > |
| Result of Givens QR decomposition. More... | |
Namespaces | |
| namespace | matrix_algorithms |
Functions | |
| template<typename T , my_size_t M, my_size_t N> | |
| GivensQRResult< T, M, N > | matrix_algorithms::qr_givens (const FusedMatrix< T, M, N > &A) |
| Compute the QR decomposition using Givens rotations. | |
Detailed Description
Givens rotation-based QR decomposition for rectangular matrices.
Decomposes A (M×N, M≥N) into Q·R using plane rotations that zero one sub-diagonal element at a time. Each rotation affects only two rows, making Givens QR ideal for:
- Sparse or banded matrices (minimal fill-in)
- Incremental/streaming updates (add one row at a time)
- Branch-free implementation (rotation parameters computed without branches)
ALGORITHM
For each column j = 0 … N−1: For each row i = M−1 down to j+1:
- Compute Givens rotation (c, s) to zero R(i, j) using R(i−1, j): r = sqrt(R(i−1,j)² + R(i,j)²) c = R(i−1,j) / r s = R(i,j) / r
- Apply rotation to rows i−1 and i of R (columns j … N−1)
- Accumulate rotation into Q (columns i−1 and i)
Complexity: O(3MN² − N³) for the factorization (roughly 50% more FLOPs than Householder for dense matrices, but better for sparse/banded).
NOTES
- Givens QR is infallible — every matrix has a valid QR decomposition.
- Q is built explicitly by accumulating rotations (unlike Householder's compact storage). This costs O(M²N) extra work but avoids the need for a separate Q extraction step.
- For purely triangularizing (R only, no Q needed), the Q accumulation can be skipped — a future
qr_givens_r_only()variant could exploit this.
