Householder Vector Generator
Computes reflection vector v_k = x_k + sign(x_{1k})‖x_k‖₂ e₁ to avoid subtractive cancellation.
Mathematics / Householder QR Factorization
FREE TO EXPLORELABORATORY 18 · MATHEMATICS
Orthogonal QR Factorization via Householder Elementary Reflections
Factorize dense m×n rectangular matrices A into orthogonal Q and upper-triangular R (A = QR) using Householder elementary reflectors H = I − 2vvᵀ/(vᵀv), eliminate numerical loss of orthogonality inherent in classical Gram-Schmidt, and extract the operational scaling constant C = 4/3 ≈ 1.333 FLOPs/n³ via ordinary least-squares regression. Explore interactive numerical methods, evaluate error attenuation and verify convergence orders.
COMPUTE · CONVERGE · ANALYSE
Your virtual mathematics laboratory.
HOUSEHOLDER QR OPERATIONS—
COMPUTATION STATUS
Ready to execute n = 20.0.
Adjust n, then execute computation.
Mathematical operations are computed deterministically using 64-bit IEEE 754 precision. Residuals reflect ordinary least-squares regression across successive observations.
Numerical assumptions and limits
Requires (4/3)n³ operations—twice as expensive as Gaussian elimination ((2/3)n³). The numerical simulation model executes Householder QR factorization across dense matrices from n = [10, 20, 30, 40, 50, 60]. Normalized cubic coordinate: x = n³/1000 = [1.00, 8.00, 27.00, 64.00, 125.00, 216.00]. Theoretical Householder factorization operations: FLOPs(n) = (4/3)n³ = [1.333, 10.667, 36.000, 85.333, 166.667, 288.000] kFLOPs. Ordinary least-squares linear regression on these coordinates produces an empirical slope C = 1.33333 and Y-intercept b = 0.000 with coefficient of determination R² = 1.000000. The empirical scaling constant C = 1.333 matches the theoretical benchmark C = 4/3 = 1.33333 within 0.0000% deviation.
Computational tools & numerical modules.
Rank-1 Elementary Reflector Applicator
Applies H_k A = A − (2/vᵀv)v(vᵀA) in 4(m−k)(n−k) operations without forming matrix H explicitly.
Frobenius Orthogonality Loss Monitor
Measures ‖QᵀQ − I‖_F and confirms stability down to machine precision ~10⁻¹⁶.
Operational Scaling FLOP Counter
Tracks the (4/3)n³ operations required to reduce matrix A to upper-triangular form R.
Interactive Reflection Plane Canvas
Visualizes vector x, reflecting hyperplane H, and the projected vector αe₁ on the coordinate axis.
Least-Squares Residual Solver
Solves overdetermined least-squares systems min ‖Ax − b‖₂ via Rx = Qᵀb.
FOLLOW THE METHOD
A reason behind every step.
Factorize dense m×n rectangular matrices A into orthogonal Q and upper-triangular R (A = QR) using Householder elementary reflectors H = I − 2vvᵀ/(vᵀv), eliminate numerical loss of orthogonality inherent in classical Gram-Schmidt, and extract the operational scaling constant C = 4/3 ≈ 1.333 FLOPs/n³ via ordinary least-squares regression. Standardized input settings: 10.0, 20.0, 30.0, 40.0, 50.0, 60.0 rows.
01
Matrix Initialization
Initialize dense n×n matrix A across dimensions n ∈ {10, 20, 30, 40, 50, 60}.
02
First Householder Vector Generation (k = 1)
Extract column vector x₁ = A[:, 1]. Compute its norm: μ₁ = ‖x₁‖₂. Set v₁ = x₁ + sign(x_{1,1})·μ₁·e₁ to prevent catastrophic cancellation.
03
Application of Reflection H₁
Compute scalar β₁ = 2 / (v₁ᵀ v₁). Update remaining columns: A ← A − β₁ · v₁ · (v₁ᵀ A). The first column is transformed to [−sign(x_{1,1})·μ₁, 0, ..., 0]ᵀ.
04
Iterate Across All Columns k = 2 to n − 1
Repeat steps 2 and 3 on the active submatrix A[k:n, k:n] until all elements below the diagonal are annihilated, leaving upper-triangular matrix R.
05
Orthogonal Matrix Q Accumulation
If explicit Q is required, accumulate Q = H₁ H₂ ... H_{n-1} by backward accumulation in (4/3)n³ additional operations.
06
Operational Scaling Linear Regression
Plot factorization operations against normalized cubic dimension n³/1000. Perform ordinary least-squares regression to extract empirical slope C = 1.333, verifying (4/3)n³ complexity.
YOUR NOTEBOOK · 0 OBSERVATIONS
Turn measurements into mathematical insight.
Points are your recorded observations. The solid regression line validates Householder QR Factorization mathematical scaling.
LINEAR ASYMPTOTIC FIT · y = mx + b
\text{FLOPs}(n) = C \cdot \frac{n^3}{1000} \implies C = \frac{4}{3} \approx 1.333
| # | Matrix Dimension n (rows) | Householder QR Operations (kFLOPs) | Normalized Dimension Cubic n³/1000 | Householder QR Operations (kFLOPs) | Remove |
|---|
No readings yet. Execute a computation and record it.
Calculate it yourself.
CHECK YOUR UNDERSTANDING