Documentation
¶
Overview ¶
Package order computes sparse-matrix orderings and measures their quality.
- RCM: reverse Cuthill-McKee with a George-Liu pseudo-peripheral start (bandwidth and profile reduction; MATLAB symrcm, scipy csgraph.reverse_cuthill_mckee).
- AMD: approximate minimum degree on the pattern of A+Aᵀ, written from Amestoy, Davis and Duff, SIAM J. Matrix Anal. Appl. 17(4), 1996, doi:10.1137/S0895479894278952 (MATLAB amd, symamd).
- COLAMD: approximate minimum degree on the column intersection graph of A, never forming AᵀA, written from Davis, Gilbert, Larimore and Ng, ACM TOMS 30(3), 2004, doi:10.1145/1024074.1024079 (MATLAB colamd).
Provenance: the implementations are written from the papers. SuiteSparse AMD and COLAMD are BSD-3-Clause and are credited as the reference algorithms; CHOLMOD, UMFPACK and CSparse (GPL/LGPL) were not consulted. Tie-breaking differs from SuiteSparse, so permutations are not expected to be identical; quality is compared through Bandwidth, Profile and CholeskyNNZ.
A permutation p lists, for each new position i, the original index p[i], so the reordered matrix is B[i][j] = A[p[i]][p[j]] (CSR.Permute(p, p)).
Index ¶
- Variables
- func AMD[T sparse.Scalar](a *sparse.CSR[T]) ([]int, error)
- func Bandwidth[T sparse.Scalar](a *sparse.CSR[T]) int
- func COLAMD[T sparse.Scalar](a *sparse.CSR[T]) ([]int, error)
- func CholeskyNNZ[T sparse.Scalar](a *sparse.CSR[T], perm []int) (int, error)
- func Inverse(p []int) []int
- func IsPermutation(p []int) bool
- func Profile[T sparse.Scalar](a *sparse.CSR[T]) int
- func QRFillNNZ[T sparse.Scalar](a *sparse.CSR[T], perm []int) (int, error)
- func RCM[T sparse.Scalar](a *sparse.CSR[T]) ([]int, error)
Constants ¶
This section is empty.
Variables ¶
var ErrNotSquare = errors.New("order: matrix is not square")
ErrNotSquare is returned for orderings that need a square matrix.
Functions ¶
func AMD ¶
AMD returns an approximate minimum degree ordering of the pattern of A + Aᵀ for a square matrix. Rows denser than max(16, 10 sqrt(n)) are ordered last, as in SuiteSparse AMD.
func COLAMD ¶
COLAMD returns a column ordering of the m x n matrix A for sparse LU or QR (an approximate minimum degree ordering of AᵀA computed from A alone). Rows with more than max(16, 10 sqrt(n)) entries are ignored and columns with more than max(16, 10 sqrt(m)) entries are ordered last, the default thresholds of SuiteSparse COLAMD.
func CholeskyNNZ ¶
CholeskyNNZ returns the number of nonzeros (diagonal included) of the Cholesky factor L of P A Pᵀ for the pattern of A + Aᵀ, computed symbolically from the elimination tree (Liu 1990). perm nil is the natural order.
func IsPermutation ¶
IsPermutation reports whether p is a permutation of 0..len(p)-1.
func Profile ¶
Profile returns the (lower) envelope size: the sum over rows of i - (smallest column index in row i), for entries on or below the diagonal.
Types ¶
This section is empty.
Source Files