Skip to main content

RowOps

Trait RowOps 

Source
pub trait RowOps: MatrixView {
    // Required methods
    fn swap_rows(&mut self, a: usize, b: usize) -> Result<(), LinearError>;
    fn scale_row(
        &mut self,
        row: usize,
        factor: &Self::Scalar,
        from_col: usize,
    ) -> Result<(), LinearError>;
    fn axpy_rows(
        &mut self,
        dst: usize,
        src: usize,
        factor: &Self::Scalar,
        from_col: usize,
    ) -> Result<(), LinearError>;

    // Provided method
    fn pivot_in_column(&self, col: usize, from_row: usize) -> Option<usize>
       where Self::Scalar: Field { ... }
}
Expand description

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.

Required Methods§

Source

fn swap_rows(&mut self, a: usize, b: usize) -> Result<(), LinearError>

Exchanges two rows.

§Errors

LinearError::IndexOutOfBounds if either row is outside the shape. Swapping a row with itself is a no-op rather than an error.

Source

fn scale_row( &mut self, row: usize, factor: &Self::Scalar, from_col: usize, ) -> Result<(), LinearError>

Multiplies row by factor, from column from_col onward.

§Errors

LinearError::IndexOutOfBounds if the row is outside the shape.

Source

fn axpy_rows( &mut self, dst: usize, src: usize, factor: &Self::Scalar, from_col: usize, ) -> Result<(), LinearError>

dst := dst + factor * src, from column from_col onward.

The one operation that makes elimination possible and sparse elimination a separate problem.

§Errors

LinearError::IndexOutOfBounds if either row is outside the shape.

Provided Methods§

Source

fn pivot_in_column(&self, col: usize, from_row: usize) -> Option<usize>
where Self::Scalar: Field,

Chooses a pivot row in col, searching at or below from_row.

Returns None when the column is entirely zero from from_row down, which is what tells elimination that the column contributes no rank.

§The search is not optional

The default searches. An implementation may override this to search differently — the bit-packed matrix scans a word at a time rather than a bit at a time — but it may not override it to take self.get(from_row, col) and stop.

This is load-bearing rather than a quality nicety. Both Laplace determinants in deep_causality_topology are fed Cayley-Menger matrices, whose (0,0) entry is zero by construction. Elimination that assumes the diagonal returns zero for every simplex volume: measured on a regular unit tetrahedron, the pivoted result is det = 4.0 and vol = √2⁄12, and the unpivoted one is det = 0.0 and a NaN volume.

§This default is exact, and that is a numerical choice

Taking the first non-zero is correct over any field and needs no ordering and no epsilon, which is what lets 𝔽₂ and ℚ through — neither has an order, and neither needs one. Over the floats it is correct but ill-conditioned: a pivot near zero amplifies rounding. The magnitude-pivoting path is a separate entry point on the algorithms rather than an override here, because DenseMatrix<T> has one impl slot and needs two opposite answers depending on whether T is normed — the same mechanic that made the algebra tower’s law markers parameterised by their operator.

Dyn Compatibility§

This trait is dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementors§

Source§

impl<T> RowOps for DenseMatrix<T>
where T: Field + Clone,

The dense layout is what makes the row operations cheap: each row’s entries are contiguous, so axpy_rows walks one slice and swap_rows exchanges two.

Source§

impl<W: NaturalNumber> RowOps for PackedGf2<W>