camd_demo CAMD p = camd (A), the approximate minimum degree ordering of A P = CAMD (S) returns the approximate minimum degree permutation vector for the sparse matrix C = S+S'. The Cholesky factorization of C (P,P), or S (P,P), tends to be sparser than that of C or S. CAMD tends to be faster than SYMMMD and SYMAMD, and tends to return better orderings than SYMMMD. S must be square. If S is full, camd(S) is equivalent to camd(sparse(S)). Usage: P = camd (S) ; % finds the ordering [P, Info] = camd (S,Control,C) ; % optional parameters & statistics Control = camd ; % returns default parameters camd ; % prints default parameters. Control (1); If S is n-by-n, then rows/columns with more than max (16, (Control (1))* sqrt(n)) entries in S+S' are considered "dense", and ignored during ordering. They are placed last in the output permutation. The default is 10.0 if Control is not present. Control (2): If nonzero, then aggressive absorption is performed. This is the default if Control is not present. Control (3): If nonzero, print statistics about the ordering. Info (1): status (0: ok, -1: out of memory, -2: matrix invalid) Info (2): n = size (A,1) Info (3): nnz (A) Info (4): the symmetry of the matrix S (0.0 means purely unsymmetric, 1.0 means purely symmetric). Computed as: B = tril (S, -1) + triu (S, 1) ; symmetry = nnz (B & B') / nnz (B); Info (5): nnz (diag (S)) Info (6): nnz in S+S', excluding the diagonal (= nnz (B+B')) Info (7): number "dense" rows/columns in S+S' Info (8): the amount of memory used by CAMD, in bytes Info (9): the number of memory compactions performed by CAMD The following statistics are slight upper bounds because of the approximate degree in CAMD. The bounds are looser if "dense" rows/columns are ignored during ordering (Info (7) > 0). The statistics are for a subsequent factorization of the matrix C (P,P). The LU factorization statistics assume no pivoting. Info (10): the number of nonzeros in L, excluding the diagonal Info (11): the number of divide operations for LL', LDL', or LU Info (12): the number of multiply-subtract pairs for LL' or LDL' Info (13): the number of multiply-subtract pairs for LU Info (14): the max # of nonzeros in any column of L (incl. diagonal) Info (15:20): unused, reserved for future use An assembly tree post-ordering is performed, which is typically the same as an elimination tree post-ordering. It is not always identical because of the approximate degree update used, and because "dense" rows/columns do not take part in the post-order. It well-suited for a subsequent "chol", however. If you require a precise elimination tree post-ordering, then do the following: Example: P = camd (S) ; C = spones (S) + spones (S') ; % skip this if S already symmetric [ignore, Q] = etree (C (P,P)) ; P = P (Q) ; CAMD has the ability to order the matrix with constraints. Each node i in the graph (row/column i in the matrix) has a constraint, C(i), which is in the range 1 to n. All nodes with C(i) = 1 are ordered first, followed by all nodes with constraint 2, and so on. That is, C(P) is monotonically non-decreasing. If C is not provided, no constraints are used (the ordering will be similar to AMD's ordering, except that the postordering is different). See also AMD, COLMMD, COLAMD, COLPERM, SYMAMD, SYMMMD, SYMRCM. If the next step fails, then you have not yet compiled the CAMD mexFunction. camd version 2.1, Dec 12, 2006: approximate minimum degree ordering: dense row parameter: 10 (rows with more than max (10 * sqrt (n), 16) entries are considered "dense", and placed last in output permutation) aggressive absorption: yes input matrix A is 24-by-24 input matrix A has 160 nonzero entries camd: approximate minimum degree ordering, results: status: OK n, dimension of A: 24 nz, number of nonzeros in A: 160 symmetry of A: 1.0000 number of nonzeros on diagonal: 24 nonzeros in pattern of A+A' (excl. diagonal): 136 # dense rows/columns of A+A': 0 memory used, in bytes: 1644 # of memory compactions: 0 The following approximate statistics are for a subsequent factorization of A(P,P) + A(P,P)'. They are slight upper bounds if there are no dense rows/columns in A+A', and become looser if dense rows/columns exist. nonzeros in L (excluding diagonal): 149 nonzeros in L (including diagonal): 173 # divide operations for LDL' or LU: 149 # multiply-subtract operations for LDL': 631 # multiply-subtract operations for LU: 1113 max nz. in any column of L (incl. diagonal): 12 chol flop count for real A, sqrt counted as 1 flop: 1435 LDL' flop count for real A: 1411 LDL' flop count for complex A: 6389 LU flop count for real A (with no pivoting): 2375 LU flop count for complex A (with no pivoting): 10245 Permutation vector: 24 21 8 2 15 10 16 4 19 22 7 3 11 6 9 23 12 14 20 1 5 13 18 17 Corresponding constraint sets: 1 1 1 2 2 3 3 3 3 3 3 4 4 5 5 5 5 5 6 6 6 6 6 6 analyze A(p,p) with MATLAB's symbfact routine: CHOLMOD version 1.1.0, May 5, 2006: : status: OK Architecture: Linux sizeof(int): 4 sizeof(UF_long): 4 sizeof(void *): 4 sizeof(double): 8 sizeof(Int): 4 (CHOLMOD's basic integer) sizeof(BLAS_INT): 4 (integer used in the BLAS) Results from most recent analysis: Cholesky flop count: 1435 Nonzeros in L: 173 memory blocks in use: 3 memory in use (MB): 0.0 peak memory usage (MB): 0.0 maxrank: update/downdate rank: 8 supernodal control: 1 40 (supernodal if flops/lnz >= 40) nmethods=0: default strategy: Try user permutation if given. Try AMD. Select best ordering tried. method 0: user permutation (if given) method 1: AMD (or COLAMD if factorizing AA') prune_dense: for pruning dense nodes: 10 a dense node has degree >= max(16,(10)*sqrt(n)) OK CHOLMOD version 1.1.0, May 5, 2006: : status: OK Architecture: Linux sizeof(int): 4 sizeof(UF_long): 4 sizeof(void *): 4 sizeof(double): 8 sizeof(Int): 4 (CHOLMOD's basic integer) sizeof(BLAS_INT): 4 (integer used in the BLAS) memory blocks in use: 0 memory in use (MB): 0.0 peak memory usage (MB): 0.0 maxrank: update/downdate rank: 8 supernodal control: 1 40 (supernodal if flops/lnz >= 40) nmethods=0: default strategy: Try user permutation if given. Try AMD. Select best ordering tried. method 0: user permutation (if given) method 1: AMD (or COLAMD if factorizing AA') prune_dense: for pruning dense nodes: 10 a dense node has degree >= max(16,(10)*sqrt(n)) OK number of nonzeros in L (including diagonal): 173 floating point operation count for chol (A (p,p)): 1435 Results from CAMD's approximate analysis: number of nonzeros in L (including diagonal): 173 floating point operation count for chol (A (p,p)): 1435 Note that the ordering quality is not as good as p=amd(A). This is only because the ordering constraints, C, have been randomly selected. diar off ??? Undefined function or method 'diar' for input arguments of type 'char'. diary 1 camd_demo CAMD p = camd (A), the approximate minimum degree ordering of A P = CAMD (S) returns the approximate minimum degree permutation vector for the sparse matrix C = S+S'. The Cholesky factorization of C (P,P), or S (P,P), tends to be sparser than that of C or S. CAMD tends to be faster than SYMMMD and SYMAMD, and tends to return better orderings than SYMMMD. S must be square. If S is full, camd(S) is equivalent to camd(sparse(S)). Usage: P = camd (S) ; % finds the ordering [P, Info] = camd (S,Control,C) ; % optional parameters & statistics Control = camd ; % returns default parameters camd ; % prints default parameters. Control (1); If S is n-by-n, then rows/columns with more than max (16, (Control (1))* sqrt(n)) entries in S+S' are considered "dense", and ignored during ordering. They are placed last in the output permutation. The default is 10.0 if Control is not present. Control (2): If nonzero, then aggressive absorption is performed. This is the default if Control is not present. Control (3): If nonzero, print statistics about the ordering. Info (1): status (0: ok, -1: out of memory, -2: matrix invalid) Info (2): n = size (A,1) Info (3): nnz (A) Info (4): the symmetry of the matrix S (0.0 means purely unsymmetric, 1.0 means purely symmetric). Computed as: B = tril (S, -1) + triu (S, 1) ; symmetry = nnz (B & B') / nnz (B); Info (5): nnz (diag (S)) Info (6): nnz in S+S', excluding the diagonal (= nnz (B+B')) Info (7): number "dense" rows/columns in S+S' Info (8): the amount of memory used by CAMD, in bytes Info (9): the number of memory compactions performed by CAMD The following statistics are slight upper bounds because of the approximate degree in CAMD. The bounds are looser if "dense" rows/columns are ignored during ordering (Info (7) > 0). The statistics are for a subsequent factorization of the matrix C (P,P). The LU factorization statistics assume no pivoting. Info (10): the number of nonzeros in L, excluding the diagonal Info (11): the number of divide operations for LL', LDL', or LU Info (12): the number of multiply-subtract pairs for LL' or LDL' Info (13): the number of multiply-subtract pairs for LU Info (14): the max # of nonzeros in any column of L (incl. diagonal) Info (15:20): unused, reserved for future use An assembly tree post-ordering is performed, which is typically the same as an elimination tree post-ordering. It is not always identical because of the approximate degree update used, and because "dense" rows/columns do not take part in the post-order. It well-suited for a subsequent "chol", however. If you require a precise elimination tree post-ordering, then do the following: Example: P = camd (S) ; C = spones (S) + spones (S') ; % skip this if S already symmetric [ignore, Q] = etree (C (P,P)) ; P = P (Q) ; CAMD has the ability to order the matrix with constraints. Each node i in the graph (row/column i in the matrix) has a constraint, C(i), which is in the range 1 to n. All nodes with C(i) = 1 are ordered first, followed by all nodes with constraint 2, and so on. That is, C(P) is monotonically non-decreasing. If C is not provided, no constraints are used (the ordering will be similar to AMD's ordering, except that the postordering is different). See also AMD, COLMMD, COLAMD, COLPERM, SYMAMD, SYMMMD, SYMRCM. If the next step fails, then you have not yet compiled the CAMD mexFunction. camd version 2.1, Dec 12, 2006: approximate minimum degree ordering: dense row parameter: 10 (rows with more than max (10 * sqrt (n), 16) entries are considered "dense", and placed last in output permutation) aggressive absorption: yes input matrix A is 24-by-24 input matrix A has 160 nonzero entries camd: approximate minimum degree ordering, results: status: OK n, dimension of A: 24 nz, number of nonzeros in A: 160 symmetry of A: 1.0000 number of nonzeros on diagonal: 24 nonzeros in pattern of A+A' (excl. diagonal): 136 # dense rows/columns of A+A': 0 memory used, in bytes: 1644 # of memory compactions: 0 The following approximate statistics are for a subsequent factorization of A(P,P) + A(P,P)'. They are slight upper bounds if there are no dense rows/columns in A+A', and become looser if dense rows/columns exist. nonzeros in L (excluding diagonal): 149 nonzeros in L (including diagonal): 173 # divide operations for LDL' or LU: 149 # multiply-subtract operations for LDL': 631 # multiply-subtract operations for LU: 1113 max nz. in any column of L (incl. diagonal): 12 chol flop count for real A, sqrt counted as 1 flop: 1435 LDL' flop count for real A: 1411 LDL' flop count for complex A: 6389 LU flop count for real A (with no pivoting): 2375 LU flop count for complex A (with no pivoting): 10245 Permutation vector: 24 21 8 2 15 10 16 4 19 22 7 3 11 6 9 23 12 14 20 1 5 13 18 17 Corresponding constraint sets: 1 1 1 2 2 3 3 3 3 3 3 4 4 5 5 5 5 5 6 6 6 6 6 6 analyze A(p,p) with MATLAB's symbfact routine: CHOLMOD version 1.1.0, May 5, 2006: : status: OK Architecture: Linux sizeof(int): 4 sizeof(UF_long): 4 sizeof(void *): 4 sizeof(double): 8 sizeof(Int): 4 (CHOLMOD's basic integer) sizeof(BLAS_INT): 4 (integer used in the BLAS) Results from most recent analysis: Cholesky flop count: 1435 Nonzeros in L: 173 memory blocks in use: 3 memory in use (MB): 0.0 peak memory usage (MB): 0.0 maxrank: update/downdate rank: 8 supernodal control: 1 40 (supernodal if flops/lnz >= 40) nmethods=0: default strategy: Try user permutation if given. Try AMD. Select best ordering tried. method 0: user permutation (if given) method 1: AMD (or COLAMD if factorizing AA') prune_dense: for pruning dense nodes: 10 a dense node has degree >= max(16,(10)*sqrt(n)) OK CHOLMOD version 1.1.0, May 5, 2006: : status: OK Architecture: Linux sizeof(int): 4 sizeof(UF_long): 4 sizeof(void *): 4 sizeof(double): 8 sizeof(Int): 4 (CHOLMOD's basic integer) sizeof(BLAS_INT): 4 (integer used in the BLAS) memory blocks in use: 0 memory in use (MB): 0.0 peak memory usage (MB): 0.0 maxrank: update/downdate rank: 8 supernodal control: 1 40 (supernodal if flops/lnz >= 40) nmethods=0: default strategy: Try user permutation if given. Try AMD. Select best ordering tried. method 0: user permutation (if given) method 1: AMD (or COLAMD if factorizing AA') prune_dense: for pruning dense nodes: 10 a dense node has degree >= max(16,(10)*sqrt(n)) OK number of nonzeros in L (including diagonal): 173 floating point operation count for chol (A (p,p)): 1435 Results from CAMD's approximate analysis: number of nonzeros in L (including diagonal): 173 floating point operation count for chol (A (p,p)): 1435 Note that the ordering quality is not as good as p=amd(A). This is only because the ordering constraints, C, have been randomly selected. diary off