amd_demo.m.out
5.86 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
amd_demo
AMD2 p = amd2 (A), the approximate minimum degree ordering of A
P = AMD2 (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. AMD tends to be faster
than SYMMMD and SYMAMD, and tends to return better orderings than SYMMMD.
S must be square. If S is full, amd(S) is equivalent to amd(sparse(S)).
Note that the built-in AMD routine in MATLAB is identical to AMD2,
except that AMD in MATLAB allows for a struct input to set the parameters.
Usage: P = amd2 (S) ; % finds the ordering
[P, Info] = amd2 (S, Control) ; % optional parameters & statistics
Control = amd2 ; % returns default parameters
amd2 ; % 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 AMD, in bytes
Info (9): the number of memory compactions performed by AMD
The following statistics are slight upper bounds because of the
approximate degree in AMD. 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 see the example below:
Example:
P = amd2 (S) ;
C = spones (S) + spones (S') ; % skip this if S already symmetric
[ignore, Q] = etree (C (P,P)) ;
P = P (Q) ;
See also AMD, COLMMD, COLAMD, COLPERM, SYMAMD, SYMMMD, SYMRCM.
If the next step fails, then you have
not yet compiled the AMD mexFunction.
AMD version 2.2.0, May 31, 2007: 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
size of AMD integer: 4
input matrix A is 24-by-24
input matrix A has 160 nonzero entries
AMD version 2.2.0, May 31, 2007, 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: 1516
# 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): 97
nonzeros in L (including diagonal): 121
# divide operations for LDL' or LU: 97
# multiply-subtract operations for LDL': 275
# multiply-subtract operations for LU: 453
max nz. in any column of L (incl. diagonal): 8
chol flop count for real A, sqrt counted as 1 flop: 671
LDL' flop count for real A: 647
LDL' flop count for complex A: 3073
LU flop count for real A (with no pivoting): 1003
LU flop count for complex A (with no pivoting): 4497
Permutation vector:
23 21 11 24 13 6 17 9 15 5 16 8 2 10 14 18 1 3 4 7 12 19 22 20
Analyze A(p,p) with MATLAB's symbfact routine:
number of nonzeros in L (including diagonal): 120
floating point operation count for chol (A (p,p)): 656
Results from AMD's approximate analysis:
number of nonzeros in L (including diagonal): 121
floating point operation count for chol (A (p,p)): 671
Note that the nonzero and flop counts from AMD are slight
upper bounds. This is due to the approximate minimum degree
method used, in conjunction with "mass elimination".
See the discussion about mass elimination in amd.h and
amd_2.c for more details.
diary off