Documentation¶

Quick start¶

The core functionality of CHOMPACK is contained in two types of objects: the symbolic object and the cspmatrix (chordal sparse matrix) object. A symbolic object represents a symbolic factorization of a sparse symmetric matrix \(A\), and it can be created as follows:

from cvxopt import spmatrix, amd
import chompack as cp

# generate sparse matrix
I = [0, 1, 3, 1, 5, 2, 6, 3, 4, 5, 4, 5, 6, 5, 6]
J = [0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 6]
A = spmatrix(1.0, I, J, (7,7))

# compute symbolic factorization using AMD ordering
symb = cp.symbolic(A, p=amd.order)

The argument \(p\) is a so-called elimination order, and it can be either an ordering routine or a permutation vector. In the above example we used the “approximate minimum degree” (AMD) ordering routine. Note that \(A\) is a lower-triangular sparse matrix that represents a symmetric matrix; upper-triangular entries in \(A\) are ignored in the symbolic factorization.

Now let’s inspect the sparsity pattern of A and its chordal embedding (i.e., the filled pattern):

>>> print(A)

[ 1.00e+00     0         0         0         0         0         0    ]
[ 1.00e+00  1.00e+00     0         0         0         0         0    ]
[    0         0      1.00e+00     0         0         0         0    ]
[ 1.00e+00     0         0      1.00e+00     0         0         0    ]
[    0         0         0      1.00e+00  1.00e+00     0         0    ]
[    0      1.00e+00     0      1.00e+00  1.00e+00  1.00e+00     0    ]
[    0         0      1.00e+00     0      1.00e+00     0      1.00e+00]

>>> print(symb.sparsity_pattern(reordered=False, symmetric=False))

[ 1.00e+00     0         0         0         0         0         0    ]
[ 1.00e+00  1.00e+00     0         0         0         0         0    ]
[    0         0      1.00e+00     0         0         0         0    ]
[ 1.00e+00     0         0      1.00e+00     0         0         0    ]
[    0         0         0      1.00e+00  1.00e+00     0         0    ]
[ 1.00e+00  1.00e+00     0      1.00e+00  1.00e+00  1.00e+00     0    ]
[    0         0      1.00e+00     0      1.00e+00     0      1.00e+00]

The reordered pattern and its cliques can be inspected using the following commands:

>>> print(symb)

[X X          ]
[X X X        ]
[  X X   X X  ]
[      X   X X]
[    X   X X X]
[    X X X X X]
[      X X X X]

>>> print(symb.cliques())

[[0, 1], [1, 2], [2, 4, 5], [3, 5, 6], [4, 5, 6]]

Similarly, the clique tree, the supernodes, and the separator sets are:

>>> print(symb.parent())

[1, 2, 4, 4, 4]

>>> print(symb.supernodes())

[[0], [1], [2], [3], [4, 5, 6]]

>>> print(symb.separators())

[[1], [2], [4, 5], [5, 6], []]

The cspmatrix object represents a chordal sparse matrix, and it contains lower-triangular numerical values as well as a reference to a symbolic factorization that defines the sparsity pattern. Given a symbolic object symb and a sparse matrix \(A\), we can create a cspmatrix as follows:

from cvxopt import spmatrix, amd, printing
import chompack as cp
printing.options['dformat'] = '%3.1f'

# generate sparse matrix and compute symbolic factorization
I = [0, 1, 3, 1, 5, 2, 6, 3, 4, 5, 4, 5, 6, 5, 6]
J = [0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 6]
A = spmatrix([1.0*i for i in range(1,15+1)], I, J, (7,7))
symb = cp.symbolic(A, p=amd.order)

L = cp.cspmatrix(symb)
L += A

Now let us take a look at \(A\) and \(L\):

>>> print(A)

[ 1.0  0    0    0    0    0    0  ]
[ 2.0  4.0  0    0    0    0    0  ]
[ 0    0    6.0  0    0    0    0  ]
[ 3.0  0    0    8.0  0    0    0  ]
[ 0    0    0    9.0 11.0  0    0  ]
[ 0    5.0  0   10.0 12.0 14.0  0  ]
[ 0    0    7.0  0   13.0  0   15.0]

>>> print(L)

[ 6.0  0    0    0    0    0    0  ]
[ 7.0 15.0  0    0    0    0    0  ]
[ 0   13.0 11.0  0    0    0    0  ]
[ 0    0    0    4.0  0    0    0  ]
[ 0    0    9.0  0    8.0  0    0  ]
[ 0    0   12.0  5.0 10.0 14.0  0  ]
[ 0    0    0    2.0  3.0  0.0  1.0]

Notice that \(L\) is a reordered lower-triangular representation of \(A\). We can convert \(L\) to an spmatrix using the spmatrix() method:

>>> print(L.spmatrix(reordered = False))

[ 1.0  0    0    0    0    0    0  ]
[ 2.0  4.0  0    0    0    0    0  ]
[ 0    0    6.0  0    0    0    0  ]
[ 3.0  0    0    8.0  0    0    0  ]
[ 0    0    0    9.0 11.0  0    0  ]
[ 0.0  5.0  0   10.0 12.0 14.0  0  ]
[ 0    0    7.0  0   13.0  0   15.0]

This returns an spmatrix with the same ordering as \(A\), i.e., the inverse permutation is applied to \(L\).

The following example illustrates how to use the Cholesky routine:

from cvxopt import spmatrix, amd, normal
from chompack import symbolic, cspmatrix, cholesky

# generate sparse matrix and compute symbolic factorization
I = [0, 1, 3, 1, 5, 2, 6, 3, 4, 5, 4, 5, 6, 5, 6]
J = [0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 6]
A = spmatrix([0.1*(i+1) for i in range(15)], I, J, (7,7)) + spmatrix(10.0,range(7),range(7))
symb = symbolic(A, p=amd.order)

# create cspmatrix
L = cspmatrix(symb)
L += A

# compute numeric factorization
cholesky(L)

>>> print(L)

[ 3.3  0    0    0    0    0    0  ]
[ 0.2  3.4  0    0    0    0    0  ]
[ 0    0.4  3.3  0    0    0    0  ]
[ 0    0    0    3.2  0    0    0  ]
[ 0    0    0.3  0    3.3  0    0  ]
[ 0    0    0.4  0.2  0.3  3.3  0  ]
[ 0    0    0    0.1  0.1 -0.0  3.2]

Given a sparse matrix \(A\), we can check if it is chordal by checking whether the permutation \(p\) returned by maximum cardinality search is a perfect elimination ordering:

from cvxopt import spmatrix, printing
printing.options['width'] = -1
import chompack as cp

# Define chordal sparse matrix
I = range(17)+[2,2,3,3,4,14,4,14,8,14,15,8,15,7,8,14,8,14,14,\
    15,10,12,13,16,12,13,16,12,13,15,16,13,15,16,15,16,15,16,16]
J = range(17)+[0,1,1,2,2,2,3,3,4,4,4,5,5,6,6,6,7,7,8,\
    8,9,9,9,9,10,10,10,11,11,11,11,12,12,12,13,13,14,14,15]
A = spmatrix(1.0,I,J,(17,17))

# Compute maximum cardinality search
p = cp.maxcardsearch(A)

Is \(p\) a perfect elimination ordering?

>>> cp.peo(A,p)

True

Let’s verify that no fill is generated by the symbolic factorization:

>>> symb = cp.symbolic(A,p)
>>> print(symb.fill)

(0, 0)

Symbolic factorization¶

class chompack.symbolic(A, p=None, merge_function=None, **kwargs)¶

Symbolic factorization object.

Computes symbolic factorization of a square sparse matrix \(A\) and creates a symbolic factorization object.

Parameters:	A – `spmatrix` p – permutation vector or ordering routine (optional) merge_function – routine that implements a merge heuristic (optional)

The optional argument p can be either a permutation vector or an ordering rutine that takes an spmatrix and returns a permutation vector.

The optional argument merge_function allows the user to merge supernodes in the elimination tree in a greedy manner; the argument must be a routine that takes the following four arguments and returns either True or False:

Parameters:	cp – clique order of the parent of clique \(k\) ck – clique order of clique \(k\) np – supernode order of the parent of supernode \(k\) nk – supernode order of supernode \(k\)

The clique k is merged with its parent if the return value is True.

Nsn¶: Number of supernodes

blkptr¶: Pointer array for block storage of chordal sparse matrix.

chidx¶: Integer array with indices of child vertices in etree: chidx[chptr[k]:chptr[k+1]] are the indices of the children of supernode \(k\).

chptr¶: Pointer array associated with chidx: chidx[chptr[k]:chptr[k+1]] are the indices of the children of supernode k.

clique_number¶: The clique number (the order of the largest clique)

cliques(reordered=True)¶: Returns a list of cliques

fill¶: Tuple with number of lower-triangular fill edges: fill[0] is the fill due to symbolic factorization, and fill[1] is the fill due to supernodal amalgamation

ip¶: Inverse permutation vector

n¶: Number of nodes (matrix order)

nnz¶: Returns the number of lower-triangular nonzeros.

p¶: Permutation vector

parent()¶: Returns a supernodal parent list: the i’th element is equal to -1 if supernode i is a root node in the clique forest, and otherwise the i’th element is the index of the parent of supernode i.

relidx¶: The relative index array facilitates fast “extend-add” and “extract” operations in the supernodal-multifrontal algorithms. The relative indices associated with supernode \(k\) is a list of indices \(I\) such that the frontal matrix \(F\) associated with the parent of node \(k\) can be updated as F[I,I] += Uj. The relative indices are stored in an integer array relidx with an associated pointer array relptr.

relptr¶: Pointer array assoicated with relidx.

separators(reordered=True)¶: Returns a list of separator sets

sncolptr¶: Pointer array associated with snrowidx.

snode¶: Supernode array: supernode \(k\) consists of nodes snode[snptr[k]:snptr[k+1]] where snptr is the supernode pointer array

snpar¶: Supernode parent array: supernode \(k\) is a root of the supernodal elimination tree if snpar[k] is equal to k, and otherwise snpar[k] is the index of the parent of supernode \(k\) in the supernodal elimination tree

snpost¶: Supernode post-ordering

snptr¶: Supernode pointer array: supernode \(k\) is of order snpptr[k+1]-snptr[k] and supernode \(k\) consists of nodes snode[snptr[k]:snptr[k+1]]

snrowidx¶: Row indices associated with representative vertices: snrowidx[sncolptr[k]:sncolptr[k+1]] are the row indices in the column corresponding the the representative vertex of supernode \(k\), or equivalently, snrowidx[sncolptr[k]:sncolptr[k+1]] is the \(k\)‘th clique.

sparsity_pattern(reordered=True, symmetric=True)¶

Returns a sparse matrix with the filled pattern. By default, the routine uses the reordered pattern, and the inverse permutation is applied if reordered is False.

Parameters:	reordered – boolean (default: True) symmetric – boolean (default: True)

supernodes(reordered=True)¶: Returns a list of supernode sets

Chordal sparse matrices¶

class chompack.cspmatrix(symb, blkval=None, factor=False)¶

Chordal sparse matrix object.

Parameters:	symb – `symbolic` object blkval – `matrix` with numerical values (optional) factor – boolean (default is False)

A cspmatrix object contains a reference to a symbolic factorization as well as an array with numerical values which are stored in a compressed block storage format which is a block variant of the compressed column storage format.

A = cspmatrix(symb) creates a new chordal sparse matrix object with a sparsity pattern defined by the symbolic factorization object symb. If the optional argument blkval specified, the cspmatrix object will use the blkval array for numerical values (and not a copy!), and otherwise the cspmatrix object is initialized with an all-zero array. The optional input factor determines whether or not the cspmatrix stores a factored matrix.

add_projection(A, alpha=1.0, beta=1.0, reordered=False)¶: Add projection of a dense matrix \(A\) to cspmatrix.

X := alpha*proj(A) + beta*X

copy()¶: Returns a new cspmatrix object with a reference to the same symbolic factorization, but with a copy of the array that stores the numerical values.

diag(reordered=True)¶: Returns a vector with the diagonal elements of the matrix.

is_factor¶: This property is equal to True if the cspmatrix represents a Cholesky factor, and otherwise it is equal to False.

spmatrix(reordered=True, symmetric=False)¶

Converts the cspmatrix \(A\) to a sparse matrix. A reordered matrix is returned if the optional argument reordered is True (default), and otherwise the inverse permutation is applied. Only the default options are allowed if the cspmatrix \(A\) represents a Cholesky factor.

Parameters:	reordered – boolean (default: True) symmetric – boolean (default: False)

Numerical computations¶

chompack.cholesky(X)¶

Supernodal multifrontal Cholesky factorization:

\[X = LL^T\]

where \(L\) is lower-triangular. On exit, the argument \(X\) contains the Cholesky factor \(L\).

Parameters:	X – `cspmatrix`

chompack.llt(L)¶

Supernodal multifrontal Cholesky product:

\[X = LL^T\]

where \(L\) is lower-triangular. On exit, the argument L contains the product \(X\).

Parameters:	L – `cspmatrix` (factor)

chompack.projected_inverse(L)¶

Supernodal multifrontal projected inverse. The routine computes the projected inverse

\[Y = P(L^{-T}L^{-1}) \]

where \(L\) is a Cholesky factor. On exit, the argument \(L\) contains the projected inverse \(Y\).

Parameters:	L – `cspmatrix` (factor)

chompack.completion(X, factored_updates=True)¶

Supernodal multifrontal maximum determinant positive definite matrix completion. The routine computes the Cholesky factor \(L\) of the inverse of the maximum determinant positive definite matrix completion of \(X\):, i.e.,

\[P( S^{-1} ) = X\]

where \(S = LL^T\). On exit, the argument X contains the lower-triangular Cholesky factor \(L\).

The optional argument factored_updates can be used to enable (if True) or disable (if False) updating of intermediate factorizations.

Parameters:	X – `cspmatrix` factored_updates – boolean

chompack.psdcompletion(A, reordered=True, **kwargs)¶

Maximum determinant positive semidefinite matrix completion. The routine takes a cspmatrix \(A\) and returns the maximum determinant positive semidefinite matrix completion \(X\) as a dense matrix, i.e.,

\[P( X ) = A\]

Parameters:	A – `cspmatrix` reordered – boolean

chompack.mrcompletion(A, reordered=True)¶

Minimum rank positive semidefinite completion. The routine takes a positive semidefinite cspmatrix \(A\) and returns a dense matrix \(Y\) with \(r\) columns that satisfies

\[P( YY^T ) = A\]

where

\[r = \max_{i} |\gamma_i|\]

is the clique number (the size of the largest clique).

Parameters:	A – `cspmatrix` reordered – boolean

chompack.edmcompletion(A, reordered=True, **kwargs)¶

Euclidean distance matrix completion. The routine takes an EDM-completable cspmatrix \(A\) and returns a dense EDM \(X\) that satisfies

\[P( X ) = A\]

Parameters:	A – `cspmatrix` reordered – boolean

chompack.hessian(L, Y, U, adj=False, inv=False, factored_updates=False)¶

Supernodal multifrontal Hessian mapping.

The mapping

\[\mathcal H_X(U) = P(X^{-1}UX^{-1})\]

is the Hessian of the log-det barrier at a positive definite chordal matrix \(X\), applied to a symmetric chordal matrix \(U\). The Hessian operator can be factored as

\[\mathcal H_X(U) = \mathcal G_X^{\mathrm adj}( \mathcal G_X(U) )\]

where the mappings on the right-hand side are adjoint mappings that map chordal symmetric matrices to chordal symmetric matrices.

This routine evaluates the mapping \(G_X\) and its adjoint \(G_X^{\mathrm adj}\) as well as the corresponding inverse mappings. The inputs adj and inv control the action as follows:

Action	adj	inv
\(U = \mathcal G_X(U)\)	False	False
\(U = \mathcal G_X^{\mathrm adj}(U)\)	True	False
\(U = \mathcal G_X^{-1}(U)\)	False	True
\(U = \mathcal (G_X^{\mathrm adj})^{-1}(U)\)	True	True

The input argument \(L\) is the Cholesky factor of \(X\). The input argument \(Y\) is the projected inverse of \(X\). The input argument \(U\) is either a chordal matrix (a cspmatrix) of a list of chordal matrices with the same sparsity pattern as \(L\) and \(Y\).

The optional argument factored_updates can be used to enable (if True) or disable (if False) updating of intermediate factorizations.

Parameters:	L – `cspmatrix` (factor) Y – `cspmatrix` U – `cspmatrix` or list of `cspmatrix` objects adj – boolean inv – boolean factored_updates – boolean

chompack.dot(X, Y)¶: Computes trace product of X and Y.

chompack.trmm(L, B, alpha=1.0, trans='N', nrhs=None, offsetB=0, ldB=None)¶

Multiplication with sparse triangular matrix. Computes

\[\begin{split}B &:= \alpha L B \text{ if trans is 'N'} \\ B &:= \alpha L^T B \text{ if trans is 'T'}\end{split}\]

where \(L\) is a cspmatrix factor.

Parameters:	L – `cspmatrix` factor B – matrix alpha – float (default: 1.0) trans – ‘N’ or ‘T’ (default: ‘N’) nrhs – number of right-hand sides (default: number of columns in \(B\)) offsetB – integer (default: 0) ldB – leading dimension of \(B\) (default: number of rows in \(B\))

chompack.trsm(L, B, alpha=1.0, trans='N', nrhs=None, offsetB=0, ldB=None)¶

Solves a triangular system of equations with multiple right-hand sides. Computes

\[\begin{split}B &:= \alpha L^{-1} B \text{ if trans is 'N'} \\ B &:= \alpha L^{-T} B \text{ if trans is 'T'} \end{split}\]

where \(L\) is a cspmatrix factor.

Parameters:	L – `cspmatrix` factor B – matrix alpha – float (default: 1.0) trans – ‘N’ or ‘T’ (default: ‘N’) nrhs – number of right-hand sides (default: number of columns in \(B\)) offsetB – integer (default: 0) ldB – leading dimension of \(B\) (default: number of rows in \(B\))

class chompack.pfcholesky(X, V, a=None, p=None)¶

Supernodal multifrontal product-form Cholesky factorization:

\[X + V \mathrm{diag}(a) V^T = L_m \cdots L_1L_0 L_0^TL_1^T \cdots L_m^T\]

where \(X = L_0L_0^T\) is of order n and \(V\) is n-by-m.

Parameters:	X – `cspmatrix` or `spmatrix` V – n-by-m matrix a – m-by-1 matrix (optional, default is vector of ones) p – n-by-1 matrix (optional, default is natural ordering)

trmm(B, trans='N')¶: Multiplication with product-form Cholesky factor. Computes

\[ \begin{align}\begin{aligned}B &:= L B \text{ if trans is 'N'}\\B &:= L^T B \text{ if trans is 'T'}\end{aligned}\end{align} \]

trsm(B, trans='N')¶: Solves a triangular system of equations with multiple righthand sides. Computes

\[ \begin{align}\begin{aligned} B &:= L^{-1} B \text{ if trans is 'N'}\\B &:= L^{-T} B \text{ if trans is 'T'} \end{aligned}\end{align} \]

Chordal conversion¶

The following example illustrates how to apply the chordal conversion technique to a sparse SDP.

# Given: tuple with cone LP problem data
# prob = (c,G,h,dims,A,b)

# Solve cone LP with CVXOPT's conelp() routine
sol = cvxopt.conelp(*prob)

# Apply chordal conversion to cone LP
probc, blk2sparse, symbs = chompack.convert_conelp(*prob)

# Solve converted problem with CVXOPT's conelp() routine
solc = cvxopt.solvers.conelp(*probc)

chompack.convert_conelp(c, G, h, dims, A=None, b=None, **kwargs)¶

Applies the clique conversion method of Fukuda et al. to the positive semidefinite blocks of a cone LP.

Parameters:	c – `matrix` G – `spmatrix` h – `matrix` dims – dictionary A – `spmatrix` or `matrix` b – `matrix`

The following example illustrates how to convert a cone LP:

prob = (c,G,h,dims,A,b)
probc, blk2sparse, symbs = convert_conelp(*prob)

The return value blk2sparse is a list of 4-tuples (blki,I,J,n) that each defines a mapping between the sparse matrix representation and the converted block-diagonal representation, and symbs is a list of symbolic factorizations corresponding to each of the semidefinite blocks in the original cone LP.

Auxiliary routines¶

chompack.maxcardsearch(A, ve=None)¶

Maximum cardinality search ordering of a sparse chordal matrix.

Returns the maximum cardinality search ordering of a symmetric chordal matrix \(A\). Only the lower triangular part of \(A\) is accessed. The maximum cardinality search ordering is a perfect elimination ordering in the factorization \(PAP^T = LL^T\). The optional argument ve is the index of the last vertex to be eliminated (the default value is n-1).

Parameters:	A – `spmatrix` ve – integer between 0 and A.size[0]-1 (optional)

chompack.peo(A, p)¶

Checks whether an ordering is a perfect elmimination order.

Returns True if the permutation \(p\) is a perfect elimination order for a Cholesky factorization \(PAP^T = LL^T\). Only the lower triangular part of \(A\) is accessed.

Parameters:	A – `spmatrix` p – `matrix` or `list` of length A.size[0]

chompack.maxchord(A, ve=None)¶

Maximal chordal subgraph of sparsity graph.

Returns a lower triangular sparse matrix which is the projection of \(A\) on a maximal chordal subgraph and a perfect elimination order \(p\). Only the lower triangular part of \(A\) is accessed. The optional argument ve is the index of the last vertex to be eliminated (the default value is n-1). If \(A\) is chordal, then the matrix returned is equal to \(A\).

Parameters:	A – `spmatrix` ve – integer between 0 and A.size[0]-1 (optional)