Compile a rank-independent QCQP representation for BM staircases
- Dominant language
- Jupyter Notebook
- Stars
- 3.7k
- Forks
- 989
- Avg merge
- 20h 41m
- Merged PRs (30d)
- 86
Description
## Motivation
The Riemannian staircase currently constructs a new `QcqpProblem(graph, p)` at every visited rank. PR #2675 makes each construction linear and reuses the constructor-built `pMin` problem, but advancing the staircase still calls every source factor's `qcqpFactors(..., p)` again and rebuilds equivalent rank-independent coefficients and constraints.
For matrix-valued BM problems, most of the mathematical representation is independent of the staircase rank `p`:
- variable keys and row dimensions;
- quadratic cost block coefficients;
- quadratic constraint `(A, b, sense, sigma)` data;
- constraint identity/order and source-factor diagnostics.
Only the runtime matrix values and their column dimension change with `p`.
## Proposal
Introduce a compiled, rank-independent QCQP representation between the source `NonlinearFactorGraph` and rank-specific optimizer adapters.
Conceptually:
```text
NonlinearFactorGraph
-> compile once
CompiledQcqp
-> instantiate/view at p
QcqpProblem(p)
```
The compiled form should own or reference the row-space quadratic data once. Creating the rank-`p` problem should be cheap and should not call the original source factors again or copy rank-independent dense coefficient matrices.
This should remain a general QCQP/BM facility. It must not encode rotation-averaging or Shonan behavior.
## Design questions
- Should this be a new `CompiledQcqp` type, or rank-independent storage directly owned by `QcqpProblem`?
- Should source factors expose a new rank-independent lowering API while `qcqpFactors(..., columnDimension)` remains as a compatibility path?
- Can `QpCost` and quadratic constraint factors operate as rank-parameterized views over shared row-space data?
- How should genuinely rank-dependent or nonquadratic constraints declare themselves and fall back without weakening fail-fast diagnostics?
- Which metadata should be retained to report the source factor responsible for an unsupported lowering?
## Acceptance criteria
- Lower every compatible source factor exactly once for an entire staircase run.
- Instantiate every visited rank without rescanning the source graph or duplicating rank-independent coefficient storage.
- Preserve cost and constraint order, exact quadratic deduplication semantics, objective values, violations, certificates, and existing unsupported-factor diagnostics.
- Demonstrate numerical equivalence across multiple ranks and at least two QCQP-lifted problem types.
- Add counting/storage tests proving compilation occurs once and rank instantiation does not relower source factors.
- Extend the phase benchmark from #2675 to quantify compilation versus per-rank instantiation.
## Out of scope
- changing ALM;
- rotation-specific optimization paths;
- matrix-free local optimization (related, but separable follow-up work).
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by tracing QcqpProblem construction, source-factor qcqpFactors calls, and QpCost or quadratic-constraint lowering across the Riemannian staircase. Review the phase benchmark from #2675 and the existing unsupported-factor diagnostics before choosing the compiled representation. Done means one lowering per staircase run, cheap rank instantiation without duplicated rank-independent storage, preserved numerical and diagnostic behavior, and counting, storage, equivalence, and benchmark tests.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- backend
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100