MBDyn-1.7.3
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups
colamd.h
Go to the documentation of this file.
1 /* $Header: /var/cvs/mbdyn/mbdyn/mbdyn-1.0/libraries/libcolamd/colamd.h,v 1.15 2017/01/12 14:43:33 masarati Exp $ */
2 /*
3  * MBDyn (C) is a multibody analysis code.
4  * http://www.mbdyn.org
5  *
6  * Copyright (C) 1996-2017
7  *
8  * Pierangelo Masarati <masarati@aero.polimi.it>
9  * Paolo Mantegazza <mantegazza@aero.polimi.it>
10  *
11  * Dipartimento di Ingegneria Aerospaziale - Politecnico di Milano
12  * via La Masa, 34 - 20156 Milano, Italy
13  * http://www.aero.polimi.it
14  *
15  * Changing this copyright notice is forbidden.
16  *
17  * This program is free software; you can redistribute it and/or modify
18  * it under the terms of the GNU General Public License as published by
19  * the Free Software Foundation (version 2 of the License).
20  *
21  *
22  * This program is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
25  * GNU General Public License for more details.
26  *
27  * You should have received a copy of the GNU General Public License
28  * along with this program; if not, write to the Free Software
29  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
30  */
31 
32 /*
33  * Colamd is distributed with MBDyn because its license seems to allow it.
34  * The original Copyright is preserved and reported below; credit of course
35  * goes to the original Authors.
36  *
37  * Colamd is used by the naive solver. The functions have been renamed
38  * in the mbdyn_* namespace for compatibility with other solvers that may
39  * require linking the original colamd functions with incompatible types.
40  */
41 
42 /* ========================================================================== */
43 /* === colamd/symamd prototypes and definitions ============================= */
44 /* ========================================================================== */
45 
46 /*
47  You must include this file (colamd.h) in any routine that uses colamd,
48  symamd, or the related macros and definitions.
49 
50  Authors:
51 
52  The authors of the code itself are Stefan I. Larimore and Timothy A.
53  Davis (davis@cise.ufl.edu), University of Florida. The algorithm was
54  developed in collaboration with John Gilbert, Xerox PARC, and Esmond
55  Ng, Oak Ridge National Laboratory.
56 
57  Date:
58 
59  May 4, 2001. Version 2.1.
60 
61  Acknowledgements:
62 
63  This work was supported by the National Science Foundation, under
64  grants DMS-9504974 and DMS-9803599.
65 
66  Notice:
67 
68  Copyright (c) 1998-2001 by the University of Florida.
69  All Rights Reserved.
70 
71  THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY
72  EXPRESSED OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
73 
74  Permission is hereby granted to use or copy this program for any
75  purpose, provided the above notices are retained on all copies.
76  User documentation of any code that uses this code must cite the
77  Authors, the Copyright, and "Used by permission." If this code is
78  accessible from within Matlab, then typing "help colamd" and "help
79  symamd" must cite the Authors. Permission to modify the code and to
80  distribute modified code is granted, provided the above notices are
81  retained, and a notice that the code was modified is included with the
82  above copyright notice. You must also retain the Availability
83  information below, of the original version.
84 
85  This software is provided free of charge.
86 
87  Availability:
88 
89  The colamd/symamd library is available at
90 
91  http://www.cise.ufl.edu/research/sparse/colamd
92 
93  This is the http://www.cise.ufl.edu/research/sparse/colamd/colamd.h
94  file. It is required by the colamd.c, colamdmex.c, and symamdmex.c
95  files, and by any C code that calls the routines whose prototypes are
96  listed below, or that uses the colamd/symamd definitions listed below.
97 
98 */
99 
100 #ifndef COLAMD_H
101 #define COLAMD_H
102 
103 /* ========================================================================== */
104 /* === Include files ======================================================== */
105 /* ========================================================================== */
106 
107 #include <stdlib.h>
108 
109 /* ========================================================================== */
110 /* === Knob and statistics definitions ====================================== */
111 /* ========================================================================== */
112 
113 /* size of the knobs [ ] array. Only knobs [0..1] are currently used. */
114 #define COLAMD_KNOBS 20
115 
116 /* number of output statistics. Only stats [0..6] are currently used. */
117 #define COLAMD_STATS 20
118 
119 /* knobs [0] and stats [0]: dense row knob and output statistic. */
120 #define COLAMD_DENSE_ROW 0
121 
122 /* knobs [1] and stats [1]: dense column knob and output statistic. */
123 #define COLAMD_DENSE_COL 1
124 
125 /* stats [2]: memory defragmentation count output statistic */
126 #define COLAMD_DEFRAG_COUNT 2
127 
128 /* stats [3]: colamd status: zero OK, > 0 warning or notice, < 0 error */
129 #define COLAMD_STATUS 3
130 
131 /* stats [4..6]: error info, or info on jumbled columns */
132 #define COLAMD_INFO1 4
133 #define COLAMD_INFO2 5
134 #define COLAMD_INFO3 6
135 
136 /* error codes returned in stats [3]: */
137 #define COLAMD_OK (0)
138 #define COLAMD_OK_BUT_JUMBLED (1)
139 #define COLAMD_ERROR_A_not_present (-1)
140 #define COLAMD_ERROR_p_not_present (-2)
141 #define COLAMD_ERROR_nrow_negative (-3)
142 #define COLAMD_ERROR_ncol_negative (-4)
143 #define COLAMD_ERROR_nnz_negative (-5)
144 #define COLAMD_ERROR_p0_nonzero (-6)
145 #define COLAMD_ERROR_A_too_small (-7)
146 #define COLAMD_ERROR_col_length_negative (-8)
147 #define COLAMD_ERROR_row_index_out_of_bounds (-9)
148 #define COLAMD_ERROR_out_of_memory (-10)
149 #define COLAMD_ERROR_internal_error (-999)
150 
151 /* ========================================================================== */
152 /* === Row and Column structures ============================================ */
153 /* ========================================================================== */
154 
155 /* User code that makes use of the colamd/symamd routines need not directly */
156 /* reference these structures. They are used only for the COLAMD_RECOMMENDED */
157 /* macro. */
158 
159 typedef struct mbdyn_Colamd_Col
160 {
161  integer start ; /* index for A of first row in this column, or DEAD */
162  /* if column is dead */
163  integer length ; /* number of rows in this column */
164  union
165  {
166  integer thickness ; /* number of original columns represented by this */
167  /* col, if the column is alive */
168  integer parent ; /* parent in parent tree super-column structure, if */
169  /* the column is dead */
170  } shared1 ;
171  union
172  {
173  integer score ; /* the score used to maintain heap, if col is alive */
174  integer order ; /* pivot ordering of this column, if col is dead */
175  } shared2 ;
176  union
177  {
178  integer headhash ; /* head of a hash bucket, if col is at the head of */
179  /* a degree list */
180  integer hash ; /* hash value, if col is not in a degree list */
181  integer prev ; /* previous column in degree list, if col is in a */
182  /* degree list (but not at the head of a degree list) */
183  } shared3 ;
184  union
185  {
186  integer degree_next ; /* next column, if col is in a degree list */
187  integer hash_next ; /* next column, if col is in a hash list */
188  } shared4 ;
189 
191 
192 typedef struct mbdyn_Colamd_Row
193 {
194  integer start ; /* index for A of first col in this row */
195  integer length ; /* number of principal columns in this row */
196  union
197  {
198  integer degree ; /* number of principal & non-principal columns in row */
199  integer p ; /* used as a row pointer in init_rows_cols () */
200  } shared1 ;
201  union
202  {
203  integer mark ; /* for computing set differences and marking dead rows*/
204  integer first_column ;/* first column in row (used in garbage collection) */
205  } shared2 ;
206 
208 
209 /* ========================================================================== */
210 /* === Colamd recommended memory size ======================================= */
211 /* ========================================================================== */
212 
213 /*
214  The recommended length Alen of the array A passed to colamd is given by
215  the COLAMD_RECOMMENDED (nnz, n_row, n_col) macro. It returns -1 if any
216  argument is negative. 2*nnz space is required for the row and column
217  indices of the matrix. COLAMD_C (n_col) + COLAMD_R (n_row) space is
218  required for the Col and Row arrays, respectively, which are internal to
219  colamd. An additional n_col space is the minimal amount of "elbow room",
220  and nnz/5 more space is recommended for run time efficiency.
221 
222  This macro is not needed when using symamd.
223 */
224 
225 #define COLAMD_C(n_col) (((n_col) + 1) * sizeof (mbdyn_Colamd_Col) / sizeof (int))
226 #define COLAMD_R(n_row) (((n_row) + 1) * sizeof (mbdyn_Colamd_Row) / sizeof (int))
227 
228 #define COLAMD_RECOMMENDED(nnz, n_row, n_col) \
229 ( \
230 ((nnz) < 0 || (n_row) < 0 || (n_col) < 0) \
231 ? \
232  (-1) \
233 : \
234  (2 * (nnz) + COLAMD_C (n_col) + COLAMD_R (n_row) + (n_col) + ((nnz) / 5)) \
235 )
236 
237 /* ========================================================================== */
238 /* === Prototypes of user-callable routines ================================= */
239 /* ========================================================================== */
240 
241 integer mbdyn_colamd_recommended /* returns recommended value of Alen, */
242  /* or (-1) if input arguments are erroneous */
243 (
244  integer nnz, /* nonzeros in A */
245  integer n_row, /* number of rows in A */
246  integer n_col /* number of columns in A */
247 ) ;
248 
249 void mbdyn_colamd_set_defaults /* sets default parameters */
250 ( /* knobs argument is modified on output */
251  double knobs [COLAMD_KNOBS] /* parameter settings for colamd */
252 ) ;
253 
254 integer mbdyn_colamd /* returns (1) if successful, (0) otherwise*/
255 ( /* A and p arguments are modified on output */
256  integer n_row, /* number of rows in A */
257  integer n_col, /* number of columns in A */
258  integer Alen, /* size of the array A */
259  integer A [], /* row indices of A, of size Alen */
260  integer p [], /* column pointers of A, of size n_col+1 */
261  double knobs [COLAMD_KNOBS],/* parameter settings for colamd */
262  integer stats [COLAMD_STATS] /* colamd output statistics and error codes */
263 ) ;
264 
265 integer mbdyn_symamd /* return (1) if OK, (0) otherwise */
266 (
267  integer n, /* number of rows and columns of A */
268  integer A [], /* row indices of A */
269  integer p [], /* column pointers of A */
270  integer perm [], /* output permutation, size n_col+1 */
271  double knobs [COLAMD_KNOBS], /* parameters (uses defaults if NULL) */
272  integer stats [COLAMD_STATS], /* output statistics and error codes */
273  void * (*allocate) (size_t, size_t),
274  /* pointer to calloc (ANSI C) or */
275  /* mxCalloc (for Matlab mexFunction) */
276  void (*release) (void *)
277  /* pointer to free (ANSI C) or */
278  /* mxFree (for Matlab mexFunction) */
279 ) ;
280 
282 (
283  integer stats [COLAMD_STATS]
284 ) ;
285 
287 (
288  integer stats [COLAMD_STATS]
289 ) ;
290 
291 #endif /* COLAMD_H */
integer first_column
Definition: colamd.h:204
integer parent
Definition: colamd.h:168
integer hash
Definition: colamd.h:180
integer p
Definition: colamd.h:199
void mbdyn_symamd_report(integer stats[20])
Definition: colamd.c:1583
union mbdyn_Colamd_Col::@1 shared2
#define COLAMD_STATS
Definition: colamd.h:117
integer degree
Definition: colamd.h:198
integer start
Definition: colamd.h:194
struct mbdyn_Colamd_Col mbdyn_Colamd_Col
integer mbdyn_symamd(integer n, integer A[], integer p[], integer perm[], double knobs[20], integer stats[20], void *(*allocate)(size_t, size_t), void(*release)(void *))
Definition: colamd.c:1066
integer headhash
Definition: colamd.h:178
integer score
Definition: colamd.h:173
#define COLAMD_KNOBS
Definition: colamd.h:114
union mbdyn_Colamd_Row::@4 shared1
union mbdyn_Colamd_Col::@0 shared1
integer thickness
Definition: colamd.h:166
union mbdyn_Colamd_Row::@5 shared2
integer mbdyn_colamd_recommended(integer nnz, integer n_row, integer n_col)
Definition: colamd.c:1004
integer mark
Definition: colamd.h:203
void mbdyn_colamd_report(integer stats[20])
Definition: colamd.c:1570
integer length
Definition: colamd.h:195
integer prev
Definition: colamd.h:181
integer hash_next
Definition: colamd.h:187
union mbdyn_Colamd_Col::@3 shared4
struct mbdyn_Colamd_Row mbdyn_Colamd_Row
integer length
Definition: colamd.h:163
integer start
Definition: colamd.h:161
integer mbdyn_colamd(integer n_row, integer n_col, integer Alen, integer A[], integer p[], double knobs[20], integer stats[20])
Definition: colamd.c:1411
void mbdyn_colamd_set_defaults(double knobs[20])
Definition: colamd.c:1038
integer order
Definition: colamd.h:174
integer degree_next
Definition: colamd.h:186
union mbdyn_Colamd_Col::@2 shared3
long int integer
Definition: colamd.c:51