Skip to content

Optional QR-based reordering for Cholesky.identify #81

Description

@thomaspinder

Context

Audit reports/audit-2026-05-18.md finding #11, deferred from the
4-PR audit-cleanup stack per plans/2026-05-18-audit-cleanup-plan.md.

When Cholesky.ordering != var_names, Cholesky.identify reconstructs
Σ from L (np.einsum("cdij,cdkj->cdik", L, L)), permutes both axes,
then runs np.linalg.cholesky(sigma_ordered) per draw. The
einsum + decomposition pair is O((C·D)·n³) on every call, even though
the algebra of a permutation-of-rows-of-L admits a cheaper path via
QR on L @ P (where P is the permutation matrix).

Why we're parking it

The audit flagged this as P2 — clean and worth doing, but the constant
in front of n³ is small, and there is no current workload where this
shows up in a profile. PR #69's Cholesky caching already removed the
larger redundancy. Without a measured regression to anchor the change
to, optimising further risks adding cleverness without benefit.

Resolution sketch

When self.ordering != var_names:

  1. Build the permutation matrix P from [var_names.index(v) for v in ordering].
  2. Compute the QR decomposition of L @ P. The R factor is the
    reordered Cholesky factor (up to sign), avoiding the round-trip
    through Σ.
  3. Verify numerical agreement with the existing einsum + cholesky path
    on a representative posterior (the gate test from PR3 would naturally
    extend).

When to revisit

  • A user / notebook reports Cholesky.identify as a hotspot in a
    profile.
  • We add a workload where it's exercised at large C·D (e.g. the
    500-draw monetary-policy SV notebook with non-trivial ordering).

Not blocking. No action until measured.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions