Algorithms

Rank-one Cholesky modification

Let R be an upper triangular Cholesky factor of a symmetric positive definite matrix A:

\[A = R^T R.\]

A rank-one update or downdate modifies the matrix as

\[A_{\mathrm{new}} = A + \alpha z z^T, \qquad \alpha \in \{+1, -1\}.\]

The package computes a triangular factor D such that

\[D^T D = R^T R + \alpha z z^T\]

for the upper convention. For the lower convention, the analogous relation is

\[D D^T = L L^T + \alpha z z^T.\]

Downdates require the modified matrix to remain positive definite. If the condition fails, cholrot raises NonPositiveDefiniteError.

Hyperbolic rotations

For downdates, the algorithms use hyperbolic rotations to remove the rank-one term while preserving triangular structure. cholrot exposes three related recurrences:

method="hy"

A direct hyperbolic-rotation recurrence.

method="hc"

A Chambers-style hyperbolic-cosine recurrence.

method="algorithm_a"

An Algorithm-A recurrence using scalar lambda updates.

These methods are mathematically equivalent for valid inputs but have different rounding behavior and implementation structure.

Direct factor-vector product

A common workflow is not to inspect the modified factor itself, but to compute

\[w = D v.\]

Calling downdate(R, z) @ v first materializes the full triangular factor D. cholrot.matvec(R, z, v) fuses the recurrence with the product and returns the same result without storing D.

Rank-one modified solve

cholrot.cholsolve solves

\[(A + \alpha z z^T) x = b\]

using triangular solves with the original Cholesky factor and the rank-one inverse identity. It does not form the modified matrix or the modified Cholesky factor.

Identity-structured product

For

\[D D^T = I + \alpha z z^T,\]

cholrot.identity_matvec computes D @ v without scanning a dense base factor. This is the structured case where the largest benchmark gains are expected, because the original Cholesky factor is the identity.