MaxVol

Swift implementations of MaxVol and RectMaxVol row-selection algorithms backed by Accelerate.

Goal

This package should provide small, explicit Swift APIs for selecting high-volume row submatrices from tall dense matrices. The first implementation target is a real-valued Double and Float path using Accelerate BLAS/LAPACK without deprecated compatibility shims.

Implementation Plan

1. Define a narrow matrix storage type.

   • Store dense matrices in column-major order to match LAPACK.
   • Keep dimensions explicit and validate shape before calling Accelerate.
   • Return descriptive errors for non-tall, rank-deficient, or malformed input.

2. Implement square MaxVol for Double and Float.

   • Accept an N x r matrix where N >= r.
   • Initialize pivots with dgetrf / sgetrf.
   • Solve for expansion coefficients with triangular solves.
   • Iterate row swaps using the standard rank-one update with dger / sger.
   • Return selected row indices, coefficient matrix, iteration count, and whether the coefficient tolerance was reached.

3. Add RectMaxVol on top of square MaxVol.

   • Start from square MaxVol pivots.
   • Greedily append rows while coefficient row norms exceed tolerance.
   • Update coefficients with BLAS rank-one operations.
   • Support fixed minRows / maxRows bounds.

4. Add correctness tests before optimizing.

   • Verify reconstruction A ~= C * A[pivots, :].
   • Check pivot count, uniqueness, and bounds.
   • Cover identity, tall random, rank-deficient, tolerance, and max-iteration cases.
   • Compare small deterministic fixtures against reference Python, Julia, or R results.

5. Add performance-focused refinements only after the behavior is stable.

   • Avoid repeated temporary allocations in the swap loop.
   • Reuse workspace buffers.
   • Keep Double and Float paths mapped to the matching Accelerate entry points.
   • Consider complex support only after real-valued APIs are stable.

Benchmarking

MaxVolBenchmark runs deterministic fixtures through the Swift implementation and prints one JSON object per result:

swift run -c release MaxVolBenchmark --iterations 20

The Python comparison harness reads the same checked-in fixture values and runs the official maxvolpy implementation from the PyPI source distribution:

uv run --python 3.11 scripts/compare_maxvolpy.py --iterations 20

To compare correctness-oriented fields, write both outputs as JSONL and run the parity checker:

swift run -c release MaxVolBenchmark --iterations 20 > /tmp/maxvol-swift.jsonl
uv run --python 3.11 scripts/compare_maxvolpy.py --iterations 20 > /tmp/maxvol-python.jsonl
python3 scripts/check_benchmark_parity.py /tmp/maxvol-swift.jsonl /tmp/maxvol-python.jsonl

For allocation profiling, build the executable once and record the workload with Instruments from the command line:

swift build -c release --product MaxVolBenchmark
xcrun xctrace record --template 'Allocations' --output /tmp/MaxVolBenchmark.trace --launch -- .build/release/MaxVolBenchmark --iterations 100

Non-Goals For The First Pass

• Exact exhaustive maximum-volume search.
• Sparse matrices.
• GPU kernels.
• Core ML model execution.
• Public API compatibility promises before the first tagged release.