IPM factorization: cached assembly and lower-triangle updates

This comparison measures the native Rust IPM before and after the assembly-map, workspace, and dense-kernel changes. The baseline already includes the tree/node parallel controls. These are BALDES-to-BALDES measurements, not a comparison against HiGHS timings.

Changes

• Compute CSC-to-front scatter positions and child-to-parent row maps during symbolic analysis. Share immutable maps across solver clones.
• Retain dense scratch, pivot permutations, multiplier vectors, and output column capacity across Newton steps. Reset scratch when the symbolic plan changes; solver clones start with independent empty scratch.
• Update the contiguous lower triangle and read symmetric pivot candidates from that triangle. Avoid mirroring the trailing matrix after every pivot. The previous full-matrix kernel remains an independent test oracle.
• Batch tree work over retained scratch buffers. Nested node work uses the same bounded Rayon pool; no workspace lock is held during nested execution.
• Recycle consumed Schur buffers through a size-binned pool, capped at 8 MiB per solver. The limit covers spare buffers, not live contributions or factors. Releasing consumed contributions avoids retaining every clique on deep trees.
• Preserve the serial up-looking fast path and release its old compressed factor before allocating the next output.

The dense update is still a rank-1/rank-2 kernel. Blocked panel factorization, relaxed supernodes, and dependency-driven subtree scheduling remain future work.

Method

Measured on an AMD Ryzen 9 9950X (16 cores, 32 logical CPUs), Linux x86_64, with rustc 1.97.1 / LLVM 22.1.6. Both binaries use the repository's release profile (opt-level 3, thin LTO), the same expanded benchmark, and the same input and diagonal sequences. No compiler or other validation job ran during timing.

Each process performs one warmup and 30 measured refactorizations. Diagonals vary as 1 + iteration / repeats. Tables give the median of three independent process medians, with the range of those medians where shown. Baseline/candidate execution order alternates between repetitions. Setup, factorization, and solve timings are collected separately. One worker is used for off, four for both and choose; there is no CPU affinity pinning.

The dense-front fixture has 512 identity columns and one column touching all 512 rows. The forest has four independent 128-row components of that form; the unbalanced forest has components of sizes 32, 64, 128, and 256. The routing case is the captured r201_master.txt fixture. Every solve is checked against a known KKT witness, with maximum absolute solution error below 1e-8.

cargo build --release --example ipm_sparse_bench
# Arguments: repetitions, threads, mode, optional exact case name.
target/release/examples/ipm_sparse_bench 30 4 both
target/release/examples/ipm_sparse_bench 30 1 off
target/release/examples/ipm_sparse_bench 30 4 choose
# Example: isolate a large front.
target/release/examples/ipm_sparse_bench 30 4 both dense-front

Warm factorization

All times are microseconds. Speedup is baseline divided by candidate; values below one indicate a slowdown. Ranges show variation across process medians, not per-iteration confidence intervals.

both

off

choose

Setup and solve costs with four workers (both)

Setup times are milliseconds; solve times are microseconds. Setup includes ordering candidates and the new immutable assembly maps. Warmup allocations are excluded from the measured refactorization loop.

Peak resident memory

These are medians of whole-process maximum RSS from wait4, in MiB. A process runs all cases and both backends, so this includes ordering, live fronts, retained allocator storage, thread stacks, and cached buffers; it is not a per-front or per-backend allocation count. The raw measurements retain each process peak.

The largest absolute solution error across all runs was 3.598e-13.

Interpretation and limits

Compare before/after within the same mode. A faster forced-parallel path can still be slower than the serial up-looking algorithm on a small sparse matrix. Choose retains that fast path when the structural heuristic finds insufficient work. Setup and solve costs should be included when judging end-to-end impact.

The synthetic fronts demonstrate dense-kernel and assembly behavior, not speedups for arbitrary routing instances. These measurements do not cover NUMA scaling, very deep elimination trees, or multiple simultaneous solver instances.

Provenance

The implementation was informed by inspection of HiPO's precomputed assembly indices and frontal storage reuse. The Rust kernel preserves this project's pivot policy and regularization rules.

Baseline source fingerprints (the worktree snapshot immediately before these optimizations, including the preceding parallel-control changes):

• factor.rs: SHA-256 ca014762d3fe2b3a94f900196bad8c73226ebdb96312c67da9ee62196623c014
• sparse_solver.rs: SHA-256 4a493de1b8c823445075c31f4170f42ba1e54ce9af248516d1bc25cd03685ca7

Raw results: ipm-factorization.json.

Validation

• cargo test -p baldes --lib --test ipm: 381 tests passed.
• cargo test -p baldes --doc: four doctests passed.
• cargo fmt -p baldes --check: passed.
• cargo clippy -p baldes --lib --tests: passed with existing repository warnings.

Regression coverage includes exact comparison against the previous dense kernel, partial fronts, 1×1/2×2 pivots, an unused upper triangle containing NaNs, changed numeric values, changed symbolic plans of the same size, appended-column symbolic reuse, thread modes, workspace reuse, failure recovery, and the Schur cache limit.