Library Reference

LowerBoundAlgorithm

An algorithm for computing a lower bound to the treewidth of a graph. The options are

MMW{S} <: LowerBoundAlgorithm

MMW{S}()

The minor-min-width heuristic.

Parameters

• S: strategy
  • 1: min-d (fast)
  • 2: max-d (fast)
  • 3: least-c (slow)

References

• Gogate, Vibhav, and Rina Dechter. "A complete anytime algorithm for treewidth." Proceedings of the 20th conference on Uncertainty in artificial intelligence. 2004.
• Bodlaender, Hans, Thomas Wolle, and Arie Koster. "Contraction and treewidth lower bounds." Journal of Graph Algorithms and Applications 10.1 (2006): 5-49.

lowerbound([weights, ]graph;
    alg::WidthOrAlgorithm=DEFAULT_LOWER_BOUND_ALGORITHM)

Compute a lower bound to the treewidth of a graph.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> lowerbound(graph)
2

DEFAULT_LOWER_BOUND_ALGORITHM = MMW()

DissectionAlgorithm

A vertex separator algorithm.

METISND <: DissectionAlgorithm

METISND(; nseps=-1, seed=-1)

Compute a vertex separator using the graph partitioning library METIS.

Parameters

• nseps: number of different separators computed at each level of nested dissection
• seed: random seed

References

• Karypis, George, and Vipin Kumar. "A fast and high quality multilevel scheme for partitioning irregular graphs." SIAM Journal on Scientific Computing 20.1 (1998): 359-392.

KaHyParND{O} <: DissectionAlgorithm

KaHyParND(order; beta=1.0)

Compute a vertex separator using the hypergraph partitioning library KaHyPar. A β-quasi-clique cover is constructed using a greedy algorithm controlled by the parameters order and beta.

Parameters

• order: tie breaking strategy (Forward or Reverse).
• beta: quasi-clique parameter

References

• Çatalyürek, Ümit V., Cevdet Aykanat, and Enver Kayaaslan. "Hypergraph partitioning-based fill-reducing ordering for symmetric matrices." SIAM Journal on Scientific Computing 33.4 (2011): 1996-2023.
• Kaya, Oguz, et al. "Fill-in reduction in sparse matrix factorizations using hypergraphs".

DEFAULT_DISSECTION_ALGORITHM = METISND()

The default dissection algorithm.

EliminationAlgorithm

A graph elimination algorithm computes a total ordering of the vertices of a graph. The algorithms implemented in CliqueTrees.jl can be divided into five categories.

• triangulation recognition algorithms
• bandwidth minimization algorithms
• local algorithms
• global algorithms
• exact treewidth algorithms

Triangulation Recognition Algorithms

These algorithms will compute perfect orderings when applied to chordal graphs.

Bandwidth Minimization Algorithms

These algorithms try to minimize the bandwidth and envelope of the ordered graph.

Local Algorithms

These algorithms simulate the graph elimination process, greedily eliminating vertices that minimize a cost function. They are faster then the global algorithms, but have worse results.

Global Algorithms

These algorithms recursively partition a graph, then call a local algorithm on the leaves. These are slower than the local algorithms, but have better results.

Exact Treewidth Algorithms

The orderings computed by these algorithms induce minimum-width tree decompositions.

PermutationOrAlgorithm = Union{
    AbstractVector,
    Tuple{AbstractVector, AbstractVector},
    EliminationAlgorithm,
}

Either a permutation or an algorithm.

DEFAULT_ELIMINATION_ALGORITHM = AMF()

The default algorithm.

BFS <: EliminationAlgorithm

BFS()

The breadth-first search algorithm.

MCS <: EliminationAlgorithm

MCS()

The maximum cardinality search algorithm.

References

• Tarjan, Robert E., and Mihalis Yannakakis. "Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs." SIAM Journal on Computing 13.3 (1984): 566-579.

LexBFS <: EliminationAlgorithm

LexBFS()

The lexicographic breadth-first-search algorithm.

References

• Rose, Donald J., R. Endre Tarjan, and George S. Lueker. "Algorithmic aspects of vertex elimination on graphs." SIAM Journal on Computing 5.2 (1976): 266-283.

RCMMD{A} <: EliminationAlgorithm

RCMMD(alg::Algorithm)

RCMMD()

The reverse Cuthill-McKee algorithm. An initial vertex is selected using the minimum degree heuristic.

Parameters

• alg: sorting algorithm

References

• Cuthill, Elizabeth, and James McKee. "Reducing the bandwidth of sparse symmetric matrices." Proceedings of the 1969 24th National Conference. 1969.

RCMGL{A} <: EliminationAlgorithm

RCMGL(alg::Algorithm)

RCMGL()

The reverse Cuthill-McKee algorithm. An initial vertex is selected using George and Liu's variant of the GPS algorithm.

Parameters

• alg: sorting algorithm

References

• Cuthill, Elizabeth, and James McKee. "Reducing the bandwidth of sparse symmetric matrices." Proceedings of the 1969 24th National Conference. 1969.
• George, Alan, and Joseph WH Liu. "An implementation of a pseudoperipheral node finder." ACM Transactions on Mathematical Software (TOMS) 5.3 (1979): 284-295.

RCM = RCMGL

The default variant of the reverse Cuthill-Mckee algorithm.

LexM <: EliminationAlgorithm

LexM()

A minimal variant of the lexicographic breadth-first-search algorithm.

References

• Rose, Donald J., R. Endre Tarjan, and George S. Lueker. "Algorithmic aspects of vertex elimination on graphs." SIAM Journal on Computing 5.2 (1976): 266-283.

MCSM <: EliminationAlgorithm

MCSM()

A minimal variant of the maximal cardinality search algorithm.

References

• Berry, Anne, et al. "Maximum cardinality search for computing minimal triangulations of graphs." Algorithmica 39 (2004): 287-298.

AMD <: EliminationAlgorithm

AMD(; dense=10.0, aggressive=1.0)

The approximate minimum degree algorithm.

Parameters

• dense: dense row parameter
• aggressive: aggressive absorption

References

• Amestoy, Patrick R., Timothy A. Davis, and Iain S. Duff. "An approximate minimum degree ordering algorithm." SIAM Journal on Matrix Analysis and Applications 17.4 (1996): 886-905.

SymAMD <: EliminationAlgorithm

SymAMD(; dense_row=10.0, dense_col=10.0, aggressive=1.0)

The column approximate minimum degree algorithm.

Parameters

• dense_row: dense row parameter
• dense_column: dense column parameter
• aggressive: aggressive absorption

References

• Davis, Timothy A., et al. "A column approximate minimum degree ordering algorithm." ACM Transactions on Mathematical Software (TOMS) 30.3 (2004): 353-376.

AMF <: EliminationAlgorithm

AMF()

The approximate minimum fill algorithm.

References

• Rothberg, Edward, and Stanley C. Eisenstat. "Node selection strategies for bottom-up sparse matrix ordering." SIAM Journal on Matrix Analysis and Applications 19.3 (1998): 682-695.

MF <: EliminationAlgorithm

MF()

The greedy minimum fill algorithm.

References

• Ng, Esmond G., and Barry W. Peyton. "Fast implementation of the minimum local fill ordering heuristic." CSC14: The Sixth SIAM Workshop on Combinatorial Scientific Computing. 2014.

MMD <: EliminationAlgorithm

MMD(; delta=0)

The multiple minimum degree algorithm.

Parameters

• delta: tolerance for multiple elimination

References

• Liu, Joseph WH. "Modification of the minimum-degree algorithm by multiple elimination." ACM Transactions on Mathematical Software (TOMS) 11.2 (1985): 141-153.

METIS <: EliminationAlgorithm

METIS(; ctype=-1, rtype=-1, nseps=-1, niter=-1, seed=-1,
        compress=-1, ccorder=-1, pfactor=-1, ufactor=-1)

The multilevel nested dissection algorithm implemented in METIS.

Parameters

• ctype: matching scheme to be used during coarsening
• rtype: algorithm used for refinement
• nseps: number of different separators computed at each level of nested dissection
• niter: number of iterations for refinement algorithm at each stage of the uncoarsening process
• seed: random seed
• compress: whether to combine vertices with identical adjacency lists
• ccorder: whether to order connected components separately
• pfactor: minimum degree of vertices that will be ordered last
• ufactor: maximum allowed load imbalance partitions

References

• Karypis, George, and Vipin Kumar. "A fast and high quality multilevel scheme for partitioning irregular graphs." SIAM Journal on Scientific Computing 20.1 (1998): 359-392.

ND{S, A, D} <: EliminationAlgorithm

ND{S}(alg::EliminationAlgorithm, dis::DissectionAlgorithm;
    width = 120,
    level = 6,
    imbalance = 130,
)

The nested dissection algorithm. The algorithm dis is used to compute vertex separators, and the algorithm alg is called on the of the separator tree. The type parameter S controls the behavior of the algorithm: if S is equal to 1 or 2, then alg is additionally called on the branches of the separator tree. At each branch, the ordering computed by alg is compared to the ordering computed by the nested dissection algorithm, and the worse of the two is discarded.

• 1: minimize width (slow)
• 2: minimize fill (slow)
• 3: no strategy (fast)

CliqueTrees currently has two vertex separator algorithms, both of which require loading an external package.

The algorithm KaHyParND computes a vertex separator indirectly, by partitioning a quasi-clique-cover of the original graph. The parameters width and level control the recursion depth of the algorithm, and the parameter imbalance controls the maximum imbalance of the vertex separator.

Parameters

• S: strategy
  • 1: minimize width (slow)
  • 2: minimize fill (slow)
  • 3: no strategy (fast)
• alg: elimination algorithm
• dis: separation algorithm
• width: minimum width
• level: maximum level
• imbalance: separator imbalance

Spectral <: EliminationAlgorithm

Spectral(; tol=0.0)

The spectral ordering algorithm only works on connected graphs. In order to use it, import the package Laplacians.

Parameters

• tol: tolerance for convergence

References

• Barnard, Stephen T., Alex Pothen, and Horst D. Simon. "A spectral algorithm for envelope reduction of sparse matrices." Proceedings of the 1993 ACM/IEEE Conference on Supercomputing. 1993.

FlowCutter <: EliminationAlgorithm

FlowCutter(; time=5, seed=0)

The FlowCutter algorithm.

Parameters

• time: run time
• seed: random seed

References

• Strasser, Ben. "Computing tree decompositions with flowcutter: PACE 2017 submission." arXiv preprint arXiv:1709.08949 (2017).

BT <: EliminationAlgorithm

BT()

The Bouchitte-Todinca algorithm.

References

• Korhonen, Tuukka, Jeremias Berg, and Matti Järvisalo. "Solving Graph Problems via Potential Maximal Cliques: An Experimental Evaluation of the Bouchitté-Todinca Algorithm." Journal of Experimental Algorithmics (JEA) 24 (2019): 1-19.

MinimalChordal{A} <: EliminationAlgorithm

MinimalChordal(alg::PermutationOrAlgorithm)

MinimalChordal()

Evaluate an elimination algorithm, and them improve its output using the MinimalChordal algorithm. The result is guaranteed to be minimal.

Parameters

• alg: elimination algorithm

References

• Heggernes, Pinar, and Barry W. Peyton. "Fast computation of minimal fill inside a given elimination ordering." SIAM journal on matrix analysis and applications 30.4 (2009): 1424-1444.

CompositeRotations{C, A} <: EliminationAlgorithm

CompositeRotations(clique::AbstractVector, alg::EliminationAlgorithm)

CompositeRotations(clique::AbstractVector)

Evaluate an eliminaton algorithm, ensuring that the given clique is at the end of the ordering.

Parameters

• clique: clique
• alg: elimination algorithm

References

• Liu, Joseph WH. "Equivalent sparse matrix reordering by elimination tree rotations." Siam Journal on Scientific and Statistical Computing 9.3 (1988): 424-444.

Compression{A} <: EliminationAlgorithm

Compression(alg::EliminationAlgorithm; tao = 1.0)

Preprocess a graph by identifying indistinguishable vertices. The algorithm alg is run on the compressed graph.

Parameters

• alg: elimination algorithm
• tao: threshold parameter for graph compression

References

• Ashcraft, Cleve. "Compressed graphs and the minimum degree algorithm." SIAM Journal on Scientific Computing 16.6 (1995): 1404-1411.

SafeRules{A, L, U} <: EliminationAlgorithm

SafeRules(alg::EliminationAlgorithm, lb::WidthOrAlgorithm)

SafeRules()

Preprocess a graph using safe reduction rules. The algorithm lb is used to compute a lower bound to the treewidth; better lower bounds allow the algorithm to perform more reductions.

Parameters

• alg: elimination algorithm
• lb: lower bound algorithm (used to lower bound the treiwidth)
• ub: elimination algorithm (used to upper bound the treewidth)
• tao: threshold parameter for graph compression

References

• Bodlaender, Hans L., et al. "Pre-processing for triangulation of probabilistic networks." (2001).
• Bodlaender, Hans L., Arie M.C.A. Koster, and Frank van den Eijkhof. "Preprocessing rules for triangulation of probabilistic networks." Computational Intelligence 21.3 (2005): 286-305.
• van den Eijkhof, Frank, Hans L. Bodlaender, and Arie M.C.A. Koster. "Safe reduction rules for weighted treewidth." Algorithmica 47 (2007): 139-158.

SafeSeparators{A, M} <: EliminationAlgorithm

SafeSeparators(alg::EliminationAlgorithm, min::PermutationOrAlgorithm)

Apple an elimination algorithm to the atoms of an almost-clique separator decomposition. The algorithm min is used to compute the decomposition.

Parameters

• alg: elimination algorithm
• min: minimal elimination algorithm

References

• Bodlaender, Hans L., and Arie MCA Koster. "Safe separators for treewidth." Discrete Mathematics 306.3 (2006): 337-350.
• Tamaki, Hisao. "A heuristic for listing almost-clique minimal separators of a graph." arXiv preprint arXiv:2108.07551 (2021).

ConnectedComponents{A} <: EliminationAlgorithm

ConnectedComponents(alg::PermutationOrAlgorithm)

ConnectedComponents()

Apply an elimination algorithm to each connected component of a graph.

Parameters

• alg: elimination algorithm

permutation([weights, ]graph;
    alg::PermutationOrAlgorithm=DEFAULT_ELIMINATION_ALGORITHM)

Construct a fill-reducing permutation of the vertices of a simple graph.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> order, index = permutation(graph);

julia> order
8-element Vector{Int64}:
 4
 1
 2
 8
 5
 3
 6
 7

julia> index == invperm(order)
true

SupernodeType

A type of supernode partition. The options are

DEFAULT_SUPERNODE_TYPE = Maximal()

The default supernode partition.

Nodal <: SupernodeType

A nodal supernode partition.

Maximal <: SupernodeType

A maximal supernode partition.

Fundamental <: SupernodeType

A fundamental supernode partition.

AbstractTree{V} = Union{Tree{V}, SupernodeTree{V}, CliqueTree{V}}

A rooted forest. This type implements the indexed tree interface.

rootindices(tree::AbstractTree)

Get the roots of a rooted forest.

ancestorindices(tree::AbstractTree, i::Integer)

Get the proper ancestors of node i.

Tree{I, Prnt, Ptr, Tgt} <: AbstractUnitRange{I}

A rooted forest T = (V, E) with edges oriented from leaf to root. This type implements the indexed tree interface.

eliminationtree([weights, ]graph;
    alg::PermutationOrAlgorithm=DEFAULT_ELIMINATION_ALGORITHM)

Construct a tree-depth decomposition of a simple graph.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> label, tree = eliminationtree(graph);

julia> tree
8-element Tree{Int64, Vector{Int64}, Array{Int64, 0}, Vector{Int64}, Vector{Int64}}:
 8
 └─ 7
    ├─ 5
    └─ 6
       ├─ 1
       ├─ 3
       │  └─ 2
       └─ 4

SupernodeTree{V} <: AbstractVector{UnitRange{V}}

A rooted forest T = (V, E) and a function snd: U → V. This type implements the indexed tree interface.

supernodetree(graph;
    alg::PermutationOrAlgorithm=DEFAULT_ELIMINATION_ALGORITHM,
    snd::SupernodeType=DEFAULT_SUPERNODE_TYPE)

Construct a supernodal elimination tree.

Clique{V, E} <: AbstractVector{V}

A clique of a clique tree.

CliqueTree{V, E} <: AbstractVector{Clique{V, E}}

A rooted forest T = (V, E) and functions

   clique: V → 2ᵁ
separator: V → 2ᵁ

This type implements the indexed tree interface.

cliquetree([weights, ]graph;
    alg::PermutationOrAlgorithm=DEFAULT_ELIMINATION_ALGORITHM,
    snd::SupernodeType=DEFAULT_SUPERNODE_TYPE)

Construct a tree decomposition of a simple graph. The vertices of the graph are first ordered by a fill-reducing permutation computed by the algorithm alg. The size of the resulting decomposition is determined by the supernode partition snd.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> label, tree = cliquetree(graph);

julia> tree
6-element CliqueTree{Int64, Int64}:
 [6, 7, 8]
 └─ [5, 7, 8]
    ├─ [1, 5]
    ├─ [3, 5, 7]
    │  └─ [2, 3]
    └─ [4, 5, 8]

treewidth([weights, ]tree::CliqueTree)

Compute the width of a clique tree.

julia> using CliqueTrees

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> label, tree = cliquetree(graph);

julia> treewidth(tree)
2

treewidth([weights, ]graph;
    alg::PermutationOrAlgorithm=DEFAULT_ELIMINATION_ALGORITHM)

Compute the width induced by an elimination algorithm.

julia> using CliqueTrees, TreeWidthSolver

julia> graph = [
           0 1 0 0 0 0 0 0
           1 0 1 0 0 1 0 0
           0 1 0 1 0 1 1 1
           0 0 1 0 0 0 0 0
           0 0 0 0 0 1 1 0
           0 1 1 0 1 0 0 0
           0 0 1 0 1 0 0 1
           0 0 1 0 0 0 1 0
       ];

julia> treewidth(graph; alg=MCS())
3

julia> treewidth(graph; alg=BT()) # exact treewidth
2

separator(clique::Clique)

Get the separator of a clique.

separator(tree::CliqueTree, i::Integer)

Get the separator at node i.

residual(clique::Clique)

Get the residual of a clique.

residual(tree::CliqueTree, i::Integer)

Get the residual at node i.

FilledGraph{V, E} <: AbstractGraph{V}

A filled graph.

ischordal(graph)

Determine whether a simple graph is chordal.

isperfect(graph, order::AbstractVector[, index::AbstractVector])

Determine whether an fill-reducing permutation is perfect.

ChordalSymbolic{I}

A symbolic factorization of a sparse symmetric matrix. It can be used to construct a ChordalCholesky or ChordalLDLt matrix factorization, determining the sparsity pattern of its lower and upper triangular factors.

Fields

• S.L: lower triangular factor (Boolean)
• S.U: upper triangular factor (Boolean)

ChordalCholesky{UPLO, T, I, Val} <: Factorization{T}

A Cholesky decomposition of a sparse positive-definite matrix $A$:

\[ P A P^\mathsf{T} = L L^\mathsf{T}.\]

where $P$ is a permutation matrix and $L$ is lower triangular. The type parameter UPLO specifies which triangular factor is stored.

• UPLO: :L or :U (lower / upper triangular)

Fields

• F.P: permutation matrix
• F.L: lower triangular factor
• F.U: upper triangular factor
• F.S: symbolic factorization

ChordalLDLt{UPLO, T, I, Val} <: Factorization{T}

An LDLᵀ decomposition of a sparse symmetric matrix $A$:

\[ P A P^\mathsf{T} = L D L^\mathsf{T}.\]

where $P$ is a permutation matrix, $L$ is unit lower triangular, and $D$ is diagonal. The type parameter UPLO specifies which triangular factor is stored.

• UPLO: :L or :U (lower / upper triangular)

Fields

• F.P: permutation matrix
• F.L: unit lower triangular factor
• F.U: unit upper triangular factor
• F.D: diagonal factor
• F.S: symbolic factorization

ChordalTriangular{UPLO, DIAG, T, I, Val} <: AbstractMatrix{T}

A triangular matrix with chordal sparsity pattern. The type parameters UPLO and DIAG specify its precise structure:

• UPLO: :L or :U (lower / upper triangular)
• DIAG: :N or :U (non-unit / unit triangular)

Basic Usage

Fields

• A.S: symbolic factorization

DynamicRegularization

Permutation{I} <: AbstractMatrix{Bool}

A permutation matrix.

Fields

• P.perm: permutation vector

symbolic(A::AbstractMatrix; kw...)

Construct a symbolic factorization. The keyword arguments kw are passed to the function cliquetree.

Basic Usage

julia> using CliqueTrees.Multifrontal, LinearAlgebra

julia> A = [
           4  2  0  0  2
           2  5  0  0  3
           0  0  4  2  0
           0  0  2  5  2
           2  3  0  2  7
       ]

julia> perm, S = symbolic(A);

julia> S
5×5 ChordalSymbolic{Int64} with 10 stored entries:
  true    ⋅      ⋅      ⋅      ⋅  
 false   true    ⋅      ⋅      ⋅  
 false   true   true    ⋅      ⋅  
  true  false  false   true    ⋅  
 false   true   true   true   true

julia> F = cholesky!(ChordalCholesky(A, perm, S))
5×5 FChordalCholesky{:L, Float64, Int64} with 10 stored entries:
 2.0   ⋅    ⋅    ⋅    ⋅ 
 0.0  2.0   ⋅    ⋅    ⋅ 
 0.0  1.0  2.0   ⋅    ⋅ 
 1.0  0.0  0.0  2.0   ⋅ 
 0.0  1.0  1.0  1.0  2.0

cholesky!(F::ChordalCholesky; check=true)

Perform a Cholesky factorization of a sparse positive-definite matrix.

Basic Usage

Use ChordalCholesky to construct a factorization object, and use cholesky! to perform the factorization.

julia> using CliqueTrees.Multifrontal, LinearAlgebra

julia> A = [
           4  2  0  0  2
           2  5  0  0  3
           0  0  4  2  0
           0  0  2  5  2
           2  3  0  2  7
       ];

julia> F = cholesky!(ChordalCholesky(A))
5×5 FChordalCholesky{:L, Float64, Int64} with 10 stored entries:
 2.0   ⋅    ⋅    ⋅    ⋅ 
 0.0  2.0   ⋅    ⋅    ⋅ 
 0.0  1.0  2.0   ⋅    ⋅ 
 1.0  0.0  0.0  2.0   ⋅ 
 0.0  1.0  1.0  1.0  2.0

Parameters

• F: positive-definite matrix
• check: if check = true, then the function errors if F is not positive definite

ldlt!(F::ChordalLDLt; check=true, reg=nothing)

Perform an LDLᵀ factorization of a sparse quasi-definite matrix.

Basic Usage

Use ChordalLDLt to construct a factorization object. Use ldlt! to perform the factorization.

julia> using CliqueTrees.Multifrontal, LinearAlgebra

julia> A = [
           4  2  0  0  2
           2  5  0  0  3
           0  0  4  2  0
           0  0  2  5  2
           2  3  0  2  7
       ];

julia> F = ldlt!(ChordalLDLt(A))
5×5 FChordalLDLt{:L, Float64, Int64} with 10 stored entries:
 1.0   ⋅    ⋅    ⋅    ⋅ 
 0.0  1.0   ⋅    ⋅    ⋅ 
 0.0  0.5  1.0   ⋅    ⋅ 
 0.5  0.0  0.0  1.0   ⋅ 
 0.0  0.5  0.5  0.5  1.0

 4.0   ⋅    ⋅    ⋅    ⋅ 
  ⋅   4.0   ⋅    ⋅    ⋅ 
  ⋅    ⋅   4.0   ⋅    ⋅ 
  ⋅    ⋅    ⋅   4.0   ⋅ 
  ⋅    ⋅    ⋅    ⋅   4.0

Parameters

• F: quasi-definite matrix
• check: if check = true, then the function errors if the matrix is singular
• reg: triggers dynamic regularization

selinv!(F::ChordalCholesky)

Compute the selected inverse of a sparse positive-definite matrix. This computes the inverse of the matrix only in the structural nonzeros of the sparsity pattern of the Cholesky factor F.L.

Use ChordalCholesky to construct a factorization object, use cholesky! to perform the factorization, and use `selinv! to compute the selected inverse.

julia> using CliqueTrees.Multifrontal, LinearAlgebra

julia> A = [
           4  2  0  0  2
           2  5  0  0  3
           0  0  4  2  0
           0  0  2  5  2
           2  3  0  2  7
       ];

julia> F = selinv!(cholesky!(ChordalCholesky(A)))
5×5 FChordalCholesky{:L, Float64, Int64} with 10 stored entries:
  0.328125    ⋅         ⋅        ⋅       ⋅
  0.0        0.328125   ⋅        ⋅       ⋅
  0.0       -0.09375   0.3125    ⋅       ⋅
 -0.15625    0.0       0.0      0.3125   ⋅
  0.0       -0.0625   -0.125   -0.125   0.25

Parameters

• F factorized positive definite matrix

complete!(F::ChordalCholesky)

Compute the Cholesky factorization of the inverse of the maximum-determinant positive-definite completion of a symmetric matrix.

Basic Usage

Use ChordalCholesky to construct a factorization object, and use complete! to perform the factorization.

julia> using CliqueTrees.Multifrontal, LinearAlgebra

julia> A = [
           4  2  0  0  2
           2  5  0  0  3
           0  0  4  2  0
           0  0  2  5  2
           2  3  0  2  7
       ];

julia> F = complete!(ChordalCholesky(A))
5×5 FChordalCholesky{:L, Float64, Int64} with 10 stored entries:
  0.5590169943749475     ⋅                   …   ⋅ 
  0.0                   0.5700877125495689       ⋅ 
  0.0                  -0.17541160386140583      ⋅ 
 -0.22360679774997896   0.0                      ⋅ 
  0.0  

Parameters

• F: symmetric matrix
• check: if check = true, then the function errors if F is not positive definite