Constrained Approximate Minimum Degree (CAMD) Ordering (sksparse.camd)

The sksparse.camd module provides an interface to the Approximate Minimum Degree (AMD) ordering algorithm for sparse, square matrices.

It exposes the main function of the CAMD package, which computes a symmetric ordering of a sparse matrix that minimizes the fill-in of the Cholesky decomposition. The CAMD function accepts both real and complex matrices, in any format supported by scipy.sparse (CSC format is most efficient).

This function is identical to that of the AMD package (sksparse.amd), except that it allows the user to specify a set of constraints on the ordering of the matrix.

Quickstart

If \(A\) is a sparse, square matrix, then the following code computes the CAMD ordering of \(A\):

from sksparse.camd import camd
A = ...  # some sparse matrix
# Set some constraints, e.g., to fix the first K rows and columns
N = A.shape[0]
K = N // 2                    # number of constrained variables
C = np.full(N, K)             # none are constrained (all == K)
C[:K] = np.arange(K)          # first K variables are constrained
p = camd(A, constraints=C)
PAPT = A[p][:, p]

to give the permuted matrix \(PAP^T\), where \(P\) is the permutation matrix corresponding to the ordering \(p\). If \(A\) is not symmetric, then this is the same as CAMD computes the ordering of the symbolically symmetric matrix \(A + A^T\).

We can then continue from above to compute the Cholesky decompositions of the original and permuted matrix using cholesky(), and compare the number of non-zeros in each:

from sksparse.cholmod import cholesky
A_factor = cholesky(A)
PAPT_factor = cholesky(PAPT)
L = A_factor.L()
Lp = PAPT_factor.L()
print("Number of non-zeros in L: ", L.nnz)
print("Number of non-zeros in Lp:", Lp.nnz)

The number of non-zeros in the Cholesky factorization of the permuted matrix should be less than or equal to the number of non-zeros in the Cholesky factorization of the original matrix, but this is not guaranteed.

Example

To see the effects of CAMD ordering, we can load a sparse matrix from the SuiteSparse Matrix Collection and compute its CAMD ordering.

#!/usr/bin/env python3
# Part of the scikit-sparse project.
# Copyright (C) 2025 Bernard Roesler. All rights reserved.
# See pyproject.toml for full author list and LICENSE.txt for license details.
# SPDX-License-Identifier: BSD-2-Clause
#
# =============================================================================
#     File: camd_example.py
#  Created: 2025-09-30 10:16
# =============================================================================

"""An example of using the AMD (Approximate Minimum Degree) algorithm to find
a fill-reducing ordering of a sparse matrix.
"""

from pathlib import Path

import matplotlib.pyplot as plt
import numpy as np
from scipy.io import mmread

from sksparse.camd import camd
from sksparse.cholmod import cholesky

# Load the bcsstk06 matrix (downloaded from the SuiteSparse Matrix Collection:
# <https://sparse.tamu.edu/HB/bcsstk06>)
filepath = Path("data") / "bcsstk06.mtx"
A = mmread(filepath, spmatrix=False).tocsc()  # read the matrix

N = A.shape[0]
K = N // 2                    # number of constrained variables
C = np.full(N, K)             # fully constrained
C[:K] = np.arange(K)          # first K variables are constrained
Nc = np.count_nonzero(C < K)  # number of constrained variables

p = camd(A, constraints=C)  # compute the AMD ordering
PAPT = A[p][:, p]           # apply the ordering to the matrix

# Compute the Cholesky factorization of each matrix
L = cholesky(A, lower=True)
Lp = cholesky(PAPT, lower=True)

# Plot the original and permuted matrices
plt.rcParams.update({"font.size": 10})

fig, axs = plt.subplots(num=1, nrows=2, ncols=2, clear=True)
fig.set_size_inches((6, 6), forward=True)
fig.set_constrained_layout(True)
fig.suptitle(
    f"CAMD Example: Fill-Reducing Ordering of bcsstk06\n{Nc} constrained variables"
)

ax = axs[0, 0]
ax.spy(A, markersize=1)
ax.set_title(r"Original Matrix $A$")

ax = axs[0, 1]
ax.spy(PAPT, markersize=1)
ax.set_title(r"Permuted Matrix $PAP^T$")

ax = axs[1, 0]
ax.spy(L, markersize=1)
ax.set_title(r"Original Cholesky Factor $L$")
ax.set_xlabel(f"{L.nnz:,} non-zeros")

ax = axs[1, 1]
ax.spy(Lp, markersize=1)
ax.set_title(r"Permuted Cholesky Factor $L_p$")
ax.set_xlabel(f"{Lp.nnz:,} non-zeros")

for ax in axs.flat:
    ax.set_aspect("equal")
    ax.set_xticks([])
    ax.set_yticks([])

plt.show()
fig.savefig("camd_example.svg")

The figure shows the effect of CAMD ordering that reduces the fill-in of the Cholesky factorization of a sparse matrix, while constraining some of the rows.

CAMD Example

The number of non-zeros in the Cholesky factorization of the original matrix (left) and the permuted matrix (right) using CAMD ordering.

CAMDInfo Objects

An CAMDInfo object is a dataclass returned by the camd() function when the return_info parameter is set to True. It contains information about the CAMD ordering, including the return status, the number of non-zeros in the Cholesky factorization, and others.

We can use CAMDInfo objects to compare the number of non-zeros in the Cholesky factorization of the original matrix, without computing it directly:

from sksparse.camd import camd
from sksparse.cholmod import cholesky
A = ...  # some sparse matrix
N = A.shape[0]
p, info = camd(A, return_info=True)
PAPT_factor = cholesky(A[p][:, p])
print("nnz in L of A:   ", info.Lnz + N)
print("nnz in L of PAPT:", PAPT_factor.L().nnz)

Typically, the CAMDInfo object is unnecessary, and you can just use the permutation vector returned by camd().

Convenience Methods

The CAMD package also provides a convenience function, camd_default_control() to get the default control parameters from the CAMD package. Most users will not need to use this function, as the default control parameters are used automatically by camd().

Error Handling

Errors raised by the CAMD package are converted into Python exceptions. See the Exceptions and Warnings for details.

References