gaelic-ghost/maxvol

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.

1. 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.

1. 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.

1. 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.

1. 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.

Package Metadata

Repository: gaelic-ghost/maxvol

Default branch: main

README: README.md