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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
//! The plane rotations of the sweep: the scale-safe Givens rotation and its
//! contiguous application to a transposed factor.
use crateKernelWindow;
use crateRealScalar;
/// Givens rotation `(c, s, r)` with `c·a + s·b = r`, `−s·a + c·b = 0`.
///
/// Returns the rotated lead component `r = c·a + s·b` (the 2-norm `√(a²+b²)`
/// when `b ≠ 0`, else `a`) so the caller uses it directly instead of recomputing
/// `c·a + s·b` — `givens` already formed `√(a²+b²)` to normalize, so re-deriving
/// it at the call site is pure redundant arithmetic (the leto `cancel_y`
/// pattern, which returns the norm alongside the rotation).
///
/// Scale-safe as LAPACK `dlartg` (3.10, Anderson 2017): `a² + b² ≤ 2m²`,
/// `m = max(|a|, |b|)`, is formed unscaled while `m` lies in
/// `[√safmin, √(Ω/2)]` — `dlartg`'s `rtmin`/`rtmax` — and otherwise from
/// `a, b` divided by the power of two bringing `m` into `[1, 2)`. `c`, `s`
/// are scale-invariant and `r` is multiplied back, all exactly, so inside the
/// window the result is bit-for-bit the unscaled formula. `window` is
/// [`SweepWindows::rotation`](super::sweep::SweepWindows::rotation).
pub
/// Apply the Givens `first' = c·first + s·second`, `second' = c·second − s·first`
/// to the two rows `(first, second)` of length `len` in a row-major matrix.
///
/// The pair need not be adjacent and need not be ordered (`first > second` is a
/// rotation with the roles swapped, which the zero-diagonal chase below needs);
/// each row is a contiguous `len`-slice either way.
///
/// # Theorem (transposed accumulation is bitwise-identical, and contiguous)
/// Accumulating `U` (or `V`) as its transpose `Uᵀ` while rotating two **rows** of
/// `Uᵀ` produces exactly the same factor `U` as rotating two **columns** of `U`,
/// bit for bit, and turns the strided column update into a contiguous one.
///
/// *Proof.* A plane rotation applied to columns `(k, k+1)` of `U` is the
/// right-multiplication `U ← U G` with `G` the embedded `2×2` Givens. Transposing,
/// `(U G)ᵀ = Gᵀ Uᵀ`, i.e. `Uᵀ ← Gᵀ Uᵀ`, which is a left-multiplication mixing
/// **rows** `(k, k+1)` of `Uᵀ` with the same scalar coefficients `(c, s)`. The two
/// updated entries in each position are the identical floating-point expression
/// `c·a + s·b` / `c·b − s·a` of the identical operands `a, b`, evaluated in the
/// identical order — so no rounding differs: the stored `Uᵀ` is the exact transpose
/// of the column-accumulated `U`. In row-major storage a row of `Uᵀ` is a
/// contiguous length-`len` slice, so the rotation is two contiguous disjoint
/// slices (cache-friendly, auto-vectorizable) instead of a stride-`len` column walk
/// (a cache line per element). The factors are recovered by reading rows of
/// `Uᵀ`/`Vᵀ` as columns of `U`/`V` at the `O(n²)` thin-extraction step — no
/// separate transpose pass — negligible against the `O(n³)` sweep. ∎
///
/// `U`/`V` are accumulated as `Uᵀ`/`Vᵀ` so every rotation hits this path.
/// The factors a sweep accumulates its rotations into, held transposed
/// ([`rotate_row_pair`]): `Uᵀ` (`m × m`) takes the left rotations of `B`'s
/// rows, `Vᵀ` (`n × n`) the right rotations of its columns. Empty on the
/// values-only path (`VEC = false`), where no rotation reaches them.
pub