1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
//! Upper Hessenberg reduction `A = Q H Qᵀ` by Householder reflectors.
//!
//! An upper Hessenberg matrix is zero below the first subdiagonal
//! (`hᵢⱼ = 0` for `i > j + 1`). Reducing to Hessenberg form is the standard
//! first phase of the non-symmetric eigenvalue problem: the subsequent Francis
//! QR iteration costs `O(n²)` per step on a Hessenberg matrix instead of `O(n³)`
//! on a full one, and the form is preserved by the iteration.
//!
//! # Theorem (Hessenberg reduction)
//! Every `A ∈ ℝⁿˣⁿ` admits `A = Q H Qᵀ` with `Q` orthogonal and `H` upper
//! Hessenberg. *Proof (constructive):* a Householder reflector
//! `Pₖ = I − βₖ vₖ vₖᵀ` is symmetric and orthogonal; choosing `vₖ` from the
//! sub-column `A[k+1.., k]` maps it onto `e₁`, zeroing `A[k+2.., k]`. Applying
//! `Pₖ` on *both* sides, `A ← Pₖ A Pₖ`, is an orthogonal **similarity**, so it
//! leaves the spectrum unchanged; crucially the right multiplication only mixes
//! columns `k+1..n`, which does not refill the zeros just created in column `k`.
//! After `k = 0 … n−3` the result is upper Hessenberg, with
//! `Q = P₀ P₁ … P_{n−3}` orthogonal (a product of orthogonal matrices). ∎
//!
//! # Corollary (spectrum preservation)
//! `H = Qᵀ A Q` is similar to `A`, so `H` and `A` have the same eigenvalues; in
//! particular `tr(H) = tr(A)` and `‖H‖_F = ‖A‖_F` (orthogonal invariance).
//!
//! Uses the shared `householder` reflector primitive
//! (SSOT); `reduce` is the reduction loop. Generic over [`crate::RealScalar`], native
//! precision throughout.
use crateRealScalar;
use ;
/// Upper Hessenberg decomposition `A = Q H Qᵀ`.
/// Validate square shape, returning the dimension `n`. Finiteness is checked in
/// the reduction's single bulk input copy (SSOT), not by a second pre-scan here.
/// Reduce a square matrix to upper Hessenberg form `A = Q H Qᵀ`, accumulating `Q`.
///
/// # Errors
/// [`LetoError::ShapeMismatch`] for non-square input;
/// [`LetoError::StorageError`] for a non-finite entry.
/// Reduce a square matrix to upper Hessenberg form, returning only the row-major
/// `H` factor and dimension `n` — the `Q` accumulation is elided at compile time.
///
/// For the eigenvalue problem `H = Qᵀ A Q` is similar to `A` (spectrum
/// preserved), so the Schur/Francis stage that follows never reads `Q`. Skipping
/// its accumulation removes an `O(n³)` cost (one `apply_right` per reflector plus
/// the `n²` allocation) — about half the reduction work. SSOT: shares the single
/// [`reduce::reduce_to_hessenberg`] kernel via its `ACCUMULATE_Q = false`
/// instantiation.
///
/// # Errors
/// [`LetoError::ShapeMismatch`] for non-square input;
/// [`LetoError::StorageError`] for a non-finite entry.
pub