|
5164
|
1 function [p, Info] = amd (A, Control) |
|
|
2 %AMD Approximate minimum degree permutation. |
|
|
3 % P = AMD (S) returns the approximate minimum degree permutation vector for |
|
|
4 % the sparse matrix C = S+S'. The Cholesky factorization of C (P,P), or |
|
|
5 % S (P,P), tends to be sparser than that of C or S. AMD tends to be faster |
|
|
6 % than SYMMMD and SYMAMD, and tends to return better orderings than SYMMMD. |
|
|
7 % S must be square. If S is full, amd (S) is equivalent to amd (sparse (S)). |
|
|
8 % |
|
|
9 % Usage: P = amd (S) ; % finds the ordering |
|
|
10 % [P, Info] = amd (S, Control) ; % optional parameters & statistics |
|
|
11 % Control = amd ; % returns default parameters |
|
|
12 % amd ; % prints default parameters. |
|
|
13 % |
|
|
14 % Control (1); If S is n-by-n, then rows/columns with more than |
|
|
15 % max (16, (Control (1))* sqrt(n)) entries in S+S' are considered |
|
|
16 % "dense", and ignored during ordering. They are placed last in the |
|
|
17 % output permutation. The default is 10.0 if Control is not present. |
|
|
18 % Control (2): If nonzero, then aggressive absorption is performed. |
|
|
19 % This is the default if Control is not present. |
|
|
20 % Control (3): If nonzero, print statistics about the ordering. |
|
|
21 % |
|
|
22 % Info (1): status (0: ok, -1: out of memory, -2: matrix invalid) |
|
|
23 % Info (2): n = size (A,1) |
|
|
24 % Info (3): nnz (A) |
|
|
25 % Info (4): the symmetry of the matrix S (0.0 means purely unsymmetric, |
|
|
26 % 1.0 means purely symmetric). Computed as: |
|
|
27 % B = tril (S, -1) + triu (S, 1) ; symmetry = nnz (B & B') / nnz (B); |
|
|
28 % Info (5): nnz (diag (S)) |
|
|
29 % Info (6): nnz in S+S', excluding the diagonal (= nnz (B+B')) |
|
|
30 % Info (7): number "dense" rows/columns in S+S' |
|
|
31 % Info (8): the amount of memory used by AMD, in bytes |
|
|
32 % Info (9): the number of memory compactions performed by AMD |
|
|
33 % |
|
|
34 % The following statistics are slight upper bounds because of the |
|
|
35 % approximate degree in AMD. The bounds are looser if "dense" rows/columns |
|
|
36 % are ignored during ordering (Info (7) > 0). The statistics are for a |
|
|
37 % subsequent factorization of the matrix C (P,P). The LU factorization |
|
|
38 % statistics assume no pivoting. |
|
|
39 % |
|
|
40 % Info (10): the number of nonzeros in L, excluding the diagonal |
|
|
41 % Info (11): the number of divide operations for LL', LDL', or LU |
|
|
42 % Info (12): the number of multiply-subtract pairs for LL' or LDL' |
|
|
43 % Info (13): the number of multiply-subtract pairs for LU |
|
|
44 % Info (14): the max # of nonzeros in any column of L (incl. diagonal) |
|
|
45 % Info (15:20): unused, reserved for future use |
|
|
46 % |
|
|
47 % An assembly tree post-ordering is performed, which is typically the same |
|
|
48 % as an elimination tree post-ordering. It is not always identical because |
|
|
49 % of the approximate degree update used, and because "dense" rows/columns |
|
|
50 % do not take part in the post-order. It well-suited for a subsequent |
|
|
51 % "chol", however. If you require a precise elimination tree post-ordering, |
|
|
52 % then do: |
|
|
53 % |
|
|
54 % P = amd (S) ; |
|
|
55 % C = spones (S) + spones (S') ; % skip this if S already symmetric |
|
|
56 % [ignore, Q] = sparsfun ('symetree', C (P,P)) ; |
|
|
57 % P = P (Q) ; |
|
|
58 % |
|
|
59 % -------------------------------------------------------------------------- |
|
|
60 % AMD Version 1.1 (Jan. 21, 2004), Copyright (c) 2004 by Timothy A. Davis, |
|
|
61 % Patrick R. Amestoy, and Iain S. Duff. See ../README for License. |
|
|
62 % email: davis@cise.ufl.edu CISE Department, Univ. of Florida. |
|
|
63 % web: http://www.cise.ufl.edu/research/sparse/amd |
|
|
64 % -------------------------------------------------------------------------- |
|
|
65 % |
|
|
66 % Acknowledgements: This work was supported by the National Science |
|
|
67 % Foundation, under grants ASC-9111263, DMS-9223088, and CCR-0203270. |
|
|
68 % |
|
|
69 % See also COLMMD, COLAMD, COLPERM, SYMAMD, SYMMMD, SYMRCM. |
|
|
70 |
|
|
71 more on |
|
|
72 help amd |
|
|
73 more off |
|
|
74 error ('amd mexFunction not found! Type "amd_make" in MATLAB to compile amd'); |
