CholeskyWorkspace

org.appliedtopology.tda4j.alpha.CholeskyWorkspace
final class CholeskyWorkspace(capacity: Int)

Maintains a Cholesky factor of B_W for the current working set W.

The working set is kept linearly independent, so B_W stays positive definite and a plain Cholesky suffices; DAQP uses LDL^T so that it can represent the singular step, we instead detect it via the Schur complement and restructure the working set immediately (see DualQP).

Appending is the standard bordered update; deleting removes a row of L and rotates the resulting extra superdiagonal away with Givens rotations, which is O(|W|²) rather than a refactorisation.

Attributes

Experimental
true
Graph
Supertypes
class Object
trait Matchable
class Any

Members list

Value members

Concrete methods

def clear(): Unit
def commit(lOut: Array[Double], s: Double): Unit

Commit the column computed by schurComplement.

Commit the column computed by schurComplement.

Attributes

def delete(k: Int): Unit

Remove index k from the working set.

Remove index k from the working set.

Deleting row k of L (keeping every column) leaves an (nw-1) x nw matrix R with R R^t equal to B_W with row/column k struck out. R is lower triangular except for one extra superdiagonal below row k, which a sweep of Givens rotations on adjacent column pairs removes.

Attributes

def isFull: Boolean
def schurComplement(bcol: Array[Double], beta: Double, lOut: Array[Double]): Double

Given bcol = B[W, j] and beta = B[j,j], write lOut = L^{-1} bcol and return the Schur complement s = beta - lOut·lOut.

Given bcol = B[W, j] and beta = B[j,j], write lOut = L^{-1} bcol and return the Schur complement s = beta - lOut·lOut.

s is exactly the squared norm of the component of A_j orthogonal to the rows already in W, so s <= 0 means linear dependence. Nothing is mutated -- call commit to actually extend the factor.

Attributes

def size: Int
def solve(rhs: Array[Double], out: Array[Double]): Unit

Solve B_W v = rhs.

Solve B_W v = rhs.

Attributes

def solveLower(rhs: Array[Double], out: Array[Double]): Unit

Solve L z = rhs. Aliasing rhs eq out is allowed.

Solve L z = rhs. Aliasing rhs eq out is allowed.

Attributes

def solveUpper(rhs: Array[Double], out: Array[Double]): Unit

Solve L^t w = rhs. Aliasing rhs eq out is allowed.

Solve L^t w = rhs. Aliasing rhs eq out is allowed.

Attributes