borglab / borglab/gtsam

Compile a rank-independent QCQP representation for BM staircases

Open
#2,683 8 comments 0 reactions 0 assignees View on GitHub
enhancement performance
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.