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
/*
* SPDX-License-Identifier: MIT
* Copyright (c) 2023 - 2026. The DeepCausality Authors and Contributors. All Rights Reserved.
*/
use crateLinearError;
use crateMatrixView;
use Field;
/// The three row operations every elimination is built from.
///
/// The inner loop of RREF, of rank, of a kernel basis, of an LU factorisation is a row update.
/// Putting that behind a trait method lets a representation that can update a whole row at once do
/// so, while the algorithm driving it never sees an individual entry in the hot path. The prototype
/// measured the cost of that seam at 0.92–0.95× a hand-written non-generic loop over the same packed
/// words — it is slightly *faster*, for the reason `from_col` exists.
///
/// # Implemented by dense layouts only
///
/// `deep_causality_linear` implements this for the dense matrix and the bit-packed 𝔽₂ matrix, and
/// **not** for the compressed-sparse-row matrix.
///
/// `swap_rows` on CSR is fine. `axpy_rows` is not: adding a multiple of one sparse row to another
/// changes that row's non-zero pattern, which in CSR means reallocating every row after it. Sparse
/// elimination needs a fill-reducing ordering and a symbolic factorisation — a different algorithm,
/// not a different implementation of this one. A caller who wants to eliminate on a sparse matrix
/// converts to a dense layout, and that conversion is written at the call site so its cost is
/// visible.
///
/// # `from_col` is not an optimisation hint
///
/// Every operation takes the column to start from. By the time elimination reaches column `k`, the
/// entries to its left are already zero in every row it will touch, so re-reading them is wasted
/// work — and it is the work a hand-written loop over `&mut [u64]` does, which is why the generic
/// version through this trait outruns it. An implementation may ignore `from_col` and still be
/// correct.
/// Whether a scalar is the additive identity.
///
/// A free function rather than a method call so that the default `pivot_in_column` above reads as
/// one expression. `Zero::is_zero` takes `&self`, and the entry arrives by value from `get`.
pub