stan-dev / stan-dev/math

Update Cholesky factors

Open
#2,855 0 comments 2 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
C++
Stars
839
Forks
220
Avg merge
2d 4h
Merged PRs (30d)
14

Description

Description

Calculation of the cholesky factor is very expensive, which is why updating a given Cholesky factor can save substantial amount of effort. It would this be great to be able to update the Cholesky factor L of a matrix A such that you get tilde{L} for tilde{A} whenever a row and column r is removed from A.

See:
https://normalsplines.blogspot.com/2019/02/algorithms-for-updating-cholesky.html

Another common update to Cholesky factors are rank-1 updates, which would also be great to have.

Also refer to:
https://en.wikipedia.org/wiki/Cholesky_decomposition#Updating_the_decomposition

Looks like Eigen supports this out of the box:
https://eigen.tuxfamily.org/dox/classEigen_1_1LLT.html#a56b1b914d7bd101a474c325327e17049

Example

An example application is for multi-variate normal covariance matrices. When I want to subset these to a sub-space, I simply need to get rid of the r th row and column of the covariance matrix, for example. In case I already have the Cholesky factor of that covariance matrix, then it would be a lot faster to update the respective Cholesky factor rather than recomputing the full thing.

Expected Output

Current Version:

v4.5.0

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

The issue names no Stan Math files, tests, or entry points. Start by locating the existing Cholesky implementation and reviewing the linked Eigen LLT documentation and Cholesky update references. Done should include support for removing a row and column, plus rank-1 updates, with coverage for the requested behavior.

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
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.