API Reference

build_A(y::Vector{JuMP.VariableRef}, F::AbstractVector{SparseMatrixCSC{T, S}}, G::SparseMatrixCSC{T, S}) where {T <: Number, S <: Integer}

Builds a JuMP.GenericAffExpr A = F_1 y_1 + F_2 y_2 + ... + F_n y_n + G.

build_constraints_lmi!(m::JuMP.Model, A::SparseMatrixCSC{JuMP.AffExpr, Int}; verbose=false)

Adds the constraint A + S ∈ PSDCone(), where S ⪰ 0 to JuMP model m

build_constraints_lmi!(m::JuMP.Model, A::SparseMatrixCSC{JuMP.AffExpr, Int}; verbose=false)

Adds the constraint F_1 y_1 + F_2 y_2 + ... + F_n y_n + G ∈ PSDCone() to JuMP model m

build_perm_matrix(p)

Builds a sparse permutation matrix form permutation p such that P*x == x[p]

edm_completion(A::SparseMatrixCSC{Tv, Ti}) where {Tv <: AbstractFloat, Ti <: Integer}

Returns a Euclidean distance matrix completion of A if it is EDM-completable using Algorithm 11.1 in [VA15].

Reference

[VA15] Chordal Graphs and Semidefinite Optimization by Lieven Vandenberghe and Martin Andersen

generate_clique_graph(cliques, n::Integer)

Generates CliqueGraph datastructure for an undirected graph from cliques and the number of nodes n.

Reference

• A clique graph based merging strategy for decomposable SDPs by Michael Garstka, Mark Cannon, Paul Goulart

generate_clique_tree(A::SparseMatrixCSC{Tv, Ti}) where {Tv <: AbstractFloat, Ti <: Integer}

Generates a CliqueTree from chordally sparse matrix A.

Reference

[VA15] Chordal Graphs and Semidefinite Optimization by Lieven Vandenberghe and Martin Andersen

generate_random_sdp(n; rand_seed=0)

Generates a random dual form SDP with side dimension n: min c'*x s.t. sum(F[i]*x[i]) + G ⪰ 0

Returns c, F, G, xstar, D, where xstar and D are optimal primal and dual variables respectively

get_children_from_par(par)

Compute the children of each vertex v in a tree specified by par

get_chordal_extension(sp_pattern::SparseMatrixCSC; perm="amd", verbose=false)

Returns p, ip, L, where L is a lower-triangular matrix representing the chordal extension of the undirected graph sp_pattern after fill-reducing permutation p (with inverse permutation ip).

Options for perm include - "nothing" (no permutation) - amd (approximate minimum degree) - metis (uses METIS) - cuthill-mckee (Cuthill-McKee bandwidth reducing algorithm)

get_cliques(cg::CliqueGraph)

Returns a list of the cliques in CliqueGraph cg.

get_cliques(ct::CliqueTree)

Returns the cliques in the graph represented by CliqueTree ct.

get_cliques(L::SparseMatrixCSC)

Returns the (maximal) cliques of the undirected graph represented by lower triangular matrix L.

get_etree(A)

Compute the parent function of the elimination tree of a symmetric sparse matrix A

get_higher_deg(L::SparseMatrixCSC)

Returns the higher degrees of each node in the graph represented by lower triangular matrix L.

NOTE: the algorithm assums that L has order σ = 1:n and zeros on the diagonal.

get_postordering(par, child)

Gets a postordering of the tree represented by vector of parents par and vector of children child.

get_selectors(input_mat::SparseMatrixCSC; verbose=true, ret_cliques=true)

Returns the (merged) cliques of the graph corresponding to the sparsity pattern of input_mat (after a permutation to reduce fill-in) and optionally the cliques. Also returns the fill-reducing permutation and and inverse permutation used.

get_sparsity_pattern_from_cliques(cliques)

Returns a sparse matrix sp corresponding to the graph with maximal cliques cliques

is_chordal(A)

Tests if the graph represented by symmetric sparse matrix A is chordal. This function can also be used with AbstractGraph objects from LightGraphs.jl.

References

• Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs by Robert Tarjan and Mihalis Yannakakis

is_edm(M::AbstractMatrix)

Checks if M is a Euclidean Distance Matrix. Note: a matrix is a EDM iff it is negative semidefinite on the subspace on the subspace orthogonal to the all ones vector.

is_edm_completable(A::SparseMatrixCSC, ct::CliqueTree)

Checks if A is EDM completable. Requires the associated CliqueTree ct.

is_separable(sp::SparseMatrixCSC)

Returns true if the sparsity pattern is separable (i.e., block diagonal).

make_selectors_from_clique_graph(cg::CliqueGraph, n)

Builds selector matrices Tℓ from cg, a CliqueGraph with n vertices.

Tℓ*X*Tℓ' is the submatrix of X corresponding to clique ℓ.

make_selectors_from_cliques(cliques, n)

Builds selector matrices Tℓ from cliques, a list of the cliques in a graph with n vertices.

Tℓ*X*Tℓ' is the submatrix of X corresponding to clique ℓ.

max_supernode_etree(L::SparseMatrixCSC, etree_par::Vector{Int})

Constructs the supernodal elimination tree of the chordal graph represented by lower triangular matrix L and with elimination tree etree_par. Returns the reprsentation vertices, the supernodal elimination tree, and a supernode memership indicator.

Implemented using [VA15, Algorithm 4.1], which was originally formulated by [PS89].

References

• [PS89] Compact clique tree data structures in sparse matrix factorizations by Alex Pothen and Chunguang Sun

• [VA15] Chordal Graphs and Semidefinite Optimization by Lieven Vandenberghe and Martin Andersen

maxdet_completion(A::SparseMatrixCSC{Tv, Ti}) where {Tv <: AbstractFloat, Ti <: Integer}

Returns the maximum determinant completion of chordal sparse matrix A using Algorithm 10.2 in [VA15].

Reference

[VA15] Chordal Graphs and Semidefinite Optimization by Lieven Vandenberghe and Martin Andersen

maxdet_completion_etree(A::SparseMatrixCSC{Tv, Ti}) where {Tv <: AbstractFloat, Ti <: Integer}

Returns the cholesky factors of the inverse of the maximum determinant completion of chordal sparse matrix A using Algorithm 4.2 in [ADV14]. This algorithm uses the elimination tree of A and, therefore, BLAS level 2 operations.

Reference

[ADV12] Logarithmic barriers for sparse matrix cones by Martin S. Andersen, Joachim Dahl, Lieven Vandenberghe

maxdet_completion_etree(A::SparseMatrixCSC{Tv, Ti}) where {Tv <: AbstractFloat, Ti <: Integer}

Returns the cholesky factors of the inverse of the maximum determinant completion of chordal sparse matrix A using Algorithm 7.3 in [ADV14]. This algorithm uses the supernodal elimination tree of A and, therefore, BLAS level 3 operations.

Reference

[ADV12] Logarithmic barriers for sparse matrix cones by Martin S. Andersen, Joachim Dahl, Lieven Vandenberghe

maximum_cardinality_search(A)

Compute the perfect elimination ordering for a chordal graph represented by a symmetric sparse matrix A. This function can also be used with AbstractGraph objects from LightGraphs.jl.

merge_cliques!(cg::CliqueGraph; verbose=false)

Merges cliques in cg in a greedy fashion starting with the pair with the largest weight_function. Stops when all pairs of cliques have a non-positive weight.

Reference

• A clique graph based merging strategy for decomposable SDPs by Michael Garstka, Mark Cannon, Paul Goulart

minrank_completion(A::SparseMatrixCSC{Tv, Ti}) where {Tv <: AbstractFloat, Ti <: Integer}

Returns the cholesky factor of the minimum rank completion (A_complete = Y*Yᵀ) of chordal sparse matrix A using Algorithm 2 in [Sun15]. This algorithm uses the supernodal elimination tree of A and, therefore, BLAS level 3 operations.

Reference

[Sun15] Decomposition Methods for Semidefinite Optimization (PhD Thesis) by Yifan Sun

order_snds!(ct::CliqueTree)

Orders supernodes such that elements of each supernode are numbered consecutively and the order is a topological ordering of the reprsentative vertices in the supernodal elimination tree. (See [VA15, 4.6])

Reference

[VA15] Chordal Graphs and Semidefinite Optimization by Lieven Vandenberghe and Martin Andersen

preprocess!(mat::SparseMatrixCSC{T, <:Integer}) where {T}

Checks that mat is symmetric and drops numerical zeros.

reconstruct_from_sparse_varref(Zref, n)

Gets the value of JuMP.Containers.SparseAxisArray Zref and returns the result as a SparseMatrixCSC

sparsity_pattern(mats::AbstractVector{SparseMatrixCSC{T,S}}) where {T, S <: Integer}

Returns the 0/1 aggregate sparsity pattern of the matrices in mats as a sparse matrix.

unzip(a)

Unzips a list of tuples a.

Example

julia> unzip([(1,2), (3,4), (5,6)])
([1, 3, 5], [2, 4, 6])

weight_function(ci, cj)

Defines the weight function used to determine if cliques ci and cj should be merged. Cliques are merged if this is positive.

Reference

• A clique graph based merging strategy for decomposable SDPs by Michael Garstka, Mark Cannon, Paul Goulart