Mercurial > octave-nkf

comparison liboctave/UMFPACK/UMFPACK/Source/umf_colamd.h @ 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 /* ========================================================================== */
2 /* === umf_colamd.h ========================================================= */
3 /* ========================================================================== */
4
5 /* -------------------------------------------------------------------------- */
6 /* UMFPACK Version 4.4, Copyright (c) 2005 by Timothy A. Davis. CISE Dept, */
7 /* Univ. of Florida. All Rights Reserved. See ../Doc/License for License. */
8 /* web: http://www.cise.ufl.edu/research/sparse/umfpack */
9 /* -------------------------------------------------------------------------- */
10
11 /*
12
13 Authors:
14
15 The authors of the COLAMD code itself are Stefan I. Larimore and Timothy A.
16 Davis, University of Florida. The algorithm was developed in collaboration
17 with John Gilbert, Xerox PARC, and Esmond Ng, Oak Ridge National Laboratory.
18
19 Date:
20
21 UMFPACK Version: see above.
22 COLAMD Version 2.0 was released on January 31, 2000.
23
24 Acknowledgements:
25
26 This work was supported by the National Science Foundation, under
27 grants DMS-9504974, DMS-9803599, and CCR-0203270.
28
29 UMFPACK: Copyright (c) 2003 by Timothy A. Davis. All Rights Reserved.
30
31 See the UMFPACK README file for the License for your use of this code.
32
33 Availability:
34
35 Both UMFPACK and the original unmodified colamd/symamd library are
36 available at http://www.cise.ufl.edu/research/sparse.
37
38 */
39
40 #ifndef COLAMD_H
41 #define COLAMD_H
42
43 /* ========================================================================== */
44 /* === Include files ======================================================== */
45 /* ========================================================================== */
46
47 #include <stdlib.h>
48
49 /* ========================================================================== */
50 /* === Knob and statistics definitions ====================================== */
51 /* ========================================================================== */
52
53 /* size of the knobs [ ] array. Only knobs [0..2] are currently used. */
54 #define COLAMD_KNOBS 20
55
56 /* number of output statistics. Only stats [0..8] are currently used. */
57 #define COLAMD_STATS 20
58
59 /* knobs [0] and stats [0]: dense row knob and output statistic. */
60 #define COLAMD_DENSE_ROW 0
61
62 /* knobs [1] and stats [1]: dense column knob and output statistic. */
63 #define COLAMD_DENSE_COL 1
64
65 /* knobs [2]: aggressive absorption option */
66 #define COLAMD_AGGRESSIVE 2
67
68 /* stats [2]: memory defragmentation count output statistic */
69 #define COLAMD_DEFRAG_COUNT 2
70
71 /* stats [3]: colamd status: zero OK, > 0 warning or notice, < 0 error */
72 #define COLAMD_STATUS 3
73
74 /* stats [4..6]: error info, or info on jumbled columns */
75 #define COLAMD_INFO1 4
76 #define COLAMD_INFO2 5
77 #define COLAMD_INFO3 6
78
79 /* ------------------ */
80 /* added for UMFPACK: */
81 /* stats [7]: number of originally empty rows */
82 #define COLAMD_EMPTY_ROW 7
83 /* stats [8]: number of originally empty cols */
84 #define COLAMD_EMPTY_COL 8
85 /* stats [9]: number of rows with entries only in dense cols */
86 #define COLAMD_NEWLY_EMPTY_ROW 9
87 /* stats [10]: number of cols with entries only in dense rows */
88 #define COLAMD_NEWLY_EMPTY_COL 10
89 /* ------------------ */
90
91 /* error codes returned in stats [3]: */
92 #define COLAMD_OK (0)
93 #define COLAMD_ERROR_jumbled_matrix (-11)
94 #define COLAMD_ERROR_A_not_present (-1)
95 #define COLAMD_ERROR_p_not_present (-2)
96 #define COLAMD_ERROR_nrow_negative (-3)
97 #define COLAMD_ERROR_ncol_negative (-4)
98 #define COLAMD_ERROR_nnz_negative (-5)
99 #define COLAMD_ERROR_p0_nonzero (-6)
100 #define COLAMD_ERROR_A_too_small (-7)
101 #define COLAMD_ERROR_col_length_negative (-8)
102 #define COLAMD_ERROR_row_index_out_of_bounds (-9)
103 #define COLAMD_ERROR_out_of_memory (-10)
104 #define COLAMD_ERROR_internal_error (-999)
105
106 /* ========================================================================== */
107 /* === Row and Column structures ============================================ */
108 /* ========================================================================== */
109
110 /* User code that makes use of the colamd/symamd routines need not directly */
111 /* reference these structures. They are used only for the COLAMD_RECOMMENDED */
112 /* macro. */
113
114 typedef struct Colamd_Col_struct
115 {
116 Int start ; /* index for A of first row in this column, or DEAD */
117 /* if column is dead */
118 Int length ; /* number of rows in this column */
119 union
120 {
121 Int thickness ; /* number of original columns represented by this */
122 /* col, if the column is alive */
123 Int parent ; /* parent in parent tree super-column structure, if */
124 /* the column is dead */
125 } shared1 ;
126 union
127 {
128 Int score ; /* the score used to maintain heap, if col is alive */
129 Int order ; /* pivot ordering of this column, if col is dead */
130 } shared2 ;
131 union
132 {
133 Int headhash ; /* head of a hash bucket, if col is at the head of */
134 /* a degree list */
135 Int hash ; /* hash value, if col is not in a degree list */
136 Int prev ; /* previous column in degree list, if col is in a */
137 /* degree list (but not at the head of a degree list) */
138 } shared3 ;
139 union
140 {
141 Int degree_next ; /* next column, if col is in a degree list */
142 Int hash_next ; /* next column, if col is in a hash list */
143 } shared4 ;
144
145 /* ------------------ */
146 /* added for UMFPACK: */
147 Int nextcol ; /* next column in this supercolumn */
148 Int lastcol ; /* last column in this supercolumn */
149 /* ------------------ */
150
151 } Colamd_Col ;
152
153 typedef struct Colamd_Row_struct
154 {
155 Int start ; /* index for A of first col in this row */
156 Int length ; /* number of principal columns in this row */
157 union
158 {
159 Int degree ; /* number of principal & non-principal columns in row */
160 Int p ; /* used as a row pointer in init_rows_cols () */
161 } shared1 ;
162 union
163 {
164 Int mark ; /* for computing set differences and marking dead rows*/
165 Int first_column ;/* first column in row (used in garbage collection) */
166 } shared2 ;
167
168 /* ------------------ */
169 /* added for UMFPACK: */
170 Int thickness ; /* number of original rows represented by this row */
171 /* that are not yet pivotal */
172 Int front ; /* -1 if an original row */
173 /* k if this row represents the kth frontal matrix */
174 /* where k goes from 0 to at most n_col-1 */
175 /* ------------------ */
176
177 } Colamd_Row ;
178
179
180
181 /* ========================================================================== */
182 /* === Colamd recommended memory size ======================================= */
183 /* ========================================================================== */
184
185 /*
186 The recommended length Alen of the array A passed to colamd is given by
187 the COLAMD_RECOMMENDED (nnz, n_row, n_col) macro. It returns -1 if any
188 argument is negative. 2*nnz space is required for the row and column
189 indices of the matrix. COLAMD_C (n_col) + COLAMD_R (n_row) space is
190 required for the Col and Row arrays, respectively, which are internal to
191 colamd. An additional n_col space is the minimal amount of "elbow room",
192 and nnz/5 more space is recommended for run time efficiency.
193
194 This macro is not needed when using symamd.
195 */
196
197 /* about 8*(n_col+1) integers: */
198 #define UMF_COLAMD_C(n_col) ((n_col + 1) * sizeof (Colamd_Col) / sizeof (Int))
199
200 /* about 6*(n_row+1) integers: */
201 #define UMF_COLAMD_R(n_row) ((n_row + 1) * sizeof (Colamd_Row) / sizeof (Int))
202
203 /* UMFPACK: make sure Alen is >= 5*n_col + size of Col and Row structures.
204 * Alen is typically about 2.2*nz + 9*n_col + 6*n_row, or 2.2nz+15n for
205 * square matrices. */
206 #define UMF_COLAMD_RECOMMENDED(nnz, n_row, n_col) \
207 ( \
208 ((nnz) < 0 || (n_row) < 0 || (n_col) < 0) \
209 ? \
210 (-1) \
211 : \
212 (MAX (2 * (nnz), 4 * (n_col)) + \
213 (Int) UMF_COLAMD_C (n_col) + \
214 (Int) UMF_COLAMD_R (n_row) + (n_col) + ((nnz) / 5)) \
215 )
216
217 /* ========================================================================== */
218 /* === Prototypes of user-callable routines ================================= */
219 /* ========================================================================== */
220
221 /* colamd_recommended removed for UMFPACK */
222
223 void UMF_colamd_set_defaults /* sets default parameters */
224 ( /* knobs argument is modified on output */
225 double knobs [COLAMD_KNOBS] /* parameter settings for colamd */
226 ) ;
227
228 Int UMF_colamd /* returns (1) if successful, (0) otherwise*/
229 ( /* A and p arguments are modified on output */
230 Int n_row, /* number of rows in A */
231 Int n_col, /* number of columns in A */
232 Int Alen, /* size of the array A */
233 Int A [], /* row indices of A, of size Alen */
234 Int p [], /* column pointers of A, of size n_col+1 */
235 double knobs [COLAMD_KNOBS],/* parameter settings for colamd */
236 Int stats [COLAMD_STATS] /* colamd output statistics and error codes */
237 /* ------------------ */
238 /* added for UMFPACK: */
239 , Int Front_npivcol [ ]
240 , Int Front_nrows [ ]
241 , Int Front_ncols [ ]
242 , Int Front_parent [ ]
243 , Int Front_cols [ ]
244 , Int *p_nfr
245 , Int InFront [ ]
246 /* ------------------ */
247 ) ;
248
249 /* symamd deleted for UMFPACK */
250
251 /* colamd_report deleted for UMFPACK */
252
253 /* symamd_report deleted for UMFPACK */
254
255 #endif /* COLAMD_H */