Mercurial > octave-nkf

comparison liboctave/UMFPACK/AMD/MATLAB/amd_demo.m.out @ 5164:57077d0ddc8e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[project @ 2005-02-25 19:55:24 by jwe]
author jwe
date Fri, 25 Feb 2005 19:55:28 +0000
parents
children
comparison
equal deleted inserted replaced
5163:9f3299378193 5164:57077d0ddc8e
1 >> amd_demo
2
3 AMD Approximate minimum degree permutation.
4 P = AMD (S) returns the approximate minimum degree permutation vector for
5 the sparse matrix C = S+S'. The Cholesky factorization of C (P,P), or
6 S (P,P), tends to be sparser than that of C or S. AMD tends to be faster
7 than SYMMMD and SYMAMD, and tends to return better orderings than SYMMMD.
8 S must be square. If S is full, amd (S) is equivalent to amd (sparse (S)).
9
10 Usage: P = amd (S) ; % finds the ordering
11 [P, Info] = amd (S, Control) ; % optional parameters & statistics
12 Control = amd ; % returns default parameters
13 amd ; % prints default parameters.
14
15 Control (1); If S is n-by-n, then rows/columns with more than
16 max (16, (Control (1))* sqrt(n)) entries in S+S' are considered
17 "dense", and ignored during ordering. They are placed last in the
18 output permutation. The default is 10.0 if Control is not present.
19 Control (2): If nonzero, then aggressive absorption is performed.
20 This is the default if Control is not present.
21 Control (3): If nonzero, print statistics about the ordering.
22
23 Info (1): status (0: ok, -1: out of memory, -2: matrix invalid)
24 Info (2): n = size (A,1)
25 Info (3): nnz (A)
26 Info (4): the symmetry of the matrix S (0.0 means purely unsymmetric,
27 1.0 means purely symmetric). Computed as:
28 B = tril (S, -1) + triu (S, 1) ; symmetry = nnz (B & B') / nnz (B);
29 Info (5): nnz (diag (S))
30 Info (6): nnz in S+S', excluding the diagonal (= nnz (B+B'))
31 Info (7): number "dense" rows/columns in S+S'
32 Info (8): the amount of memory used by AMD, in bytes
33 Info (9): the number of memory compactions performed by AMD
34
35 The following statistics are slight upper bounds because of the
36 approximate degree in AMD. The bounds are looser if "dense" rows/columns
37 are ignored during ordering (Info (7) > 0). The statistics are for a
38 subsequent factorization of the matrix C (P,P). The LU factorization
39 statistics assume no pivoting.
40
41 Info (10): the number of nonzeros in L, excluding the diagonal
42 Info (11): the number of divide operations for LL', LDL', or LU
43 Info (12): the number of multiply-subtract pairs for LL' or LDL'
44 Info (13): the number of multiply-subtract pairs for LU
45 Info (14): the max # of nonzeros in any column of L (incl. diagonal)
46 Info (15:20): unused, reserved for future use
47
48 An assembly tree post-ordering is performed, which is typically the same
49 as an elimination tree post-ordering. It is not always identical because
50 of the approximate degree update used, and because "dense" rows/columns
51 do not take part in the post-order. It well-suited for a subsequent
52 "chol", however. If you require a precise elimination tree post-ordering,
53 then do:
54
55 P = amd (S) ;
56 C = spones (S) + spones (S') ; % skip this if S already symmetric
57 [ignore, Q] = sparsfun ('symetree', C (P,P)) ;
58 P = P (Q) ;
59
60 --------------------------------------------------------------------------
61 AMD Version 1.1 (Jan. 21, 2004), Copyright (c) 2004 by Timothy A. Davis,
62 Patrick R. Amestoy, and Iain S. Duff. See ../README for License.
63 email: davis@cise.ufl.edu CISE Department, Univ. of Florida.
64 web: http://www.cise.ufl.edu/research/sparse/amd
65 --------------------------------------------------------------------------
66
67 Acknowledgements: This work was supported by the National Science
68 Foundation, under grants ASC-9111263, DMS-9223088, and CCR-0203270.
69
70 See also COLMMD, COLAMD, COLPERM, SYMAMD, SYMMMD, SYMRCM.
71
72 Matrix name: HB/can_24
73 Matrix title: 1SYMMETRIC PATTERN FROM CANNES,LUCIEN MARRO,JUNE 1981.
74
75 If the next step fails, then you have
76 not yet compiled the AMD mexFunction.
77
78 amd: approximate minimum degree ordering, parameters:
79 dense row parameter: 10
80 (rows with more than max (10 * sqrt (n), 16) entries are
81 considered "dense", and placed last in output permutation)
82 aggressive absorption: yes
83
84 input matrix A is 24-by-24
85 input matrix A has 160 nonzero entries
86
87 amd: approximate minimum degree ordering, results:
88 status: OK
89 n, dimension of A: 24
90 nz, number of nonzeros in A: 160
91 symmetry of A: 1.0000
92 number of nonzeros on diagonal: 24
93 nonzeros in pattern of A+A' (excl. diagonal): 136
94 # dense rows/columns of A+A': 0
95 memory used, in bytes: 1516
96 # of memory compactions: 0
97
98 The following approximate statistics are for a subsequent
99 factorization of A(P,P) + A(P,P)'. They are slight upper
100 bounds if there are no dense rows/columns in A+A', and become
101 looser if dense rows/columns exist.
102
103 nonzeros in L (excluding diagonal): 97
104 nonzeros in L (including diagonal): 121
105 # divide operations for LDL' or LU: 97
106 # multiply-subtract operations for LDL': 275
107 # multiply-subtract operations for LU: 453
108 max nz. in any column of L (incl. diagonal): 8
109
110 chol flop count for real A, sqrt counted as 1 flop: 671
111 LDL' flop count for real A: 647
112 LDL' flop count for complex A: 3073
113 LU flop count for real A (with no pivoting): 1003
114 LU flop count for complex A (with no pivoting): 4497
115
116 Permutation vector:
117 23 21 11 24 13 6 17 9 15 5 16 8 2 10 14 18 1 3 4 7 12 19 22 20
118
119 Analyze A(p,p) with MATLAB's symbfact routine:
120 predicted nonzeros: 120
121 predicted flops: 656
122 predicted height: 16
123 predicted front size: 7
124 number of nonzeros in L (including diagonal): 120
125 floating point operation count for chol (A (p,p)): 656
126
127 Results from AMD's approximate analysis:
128 number of nonzeros in L (including diagonal): 121
129 floating point operation count for chol (A (p,p)): 671
130
131 Note that the nonzero and flop counts from AMD are slight
132 upper bounds. This is due to the approximate minimum degree
133 method used, in conjunction with "mass elimination".
134 See the discussion about mass elimination in amd.h and
135 amd_2.c for more details.
136 >> diary off