Newer
Older
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
126
127
128
129
130
// // This file is part of Eigen, a lightweight C++ template library
// for linear algebra.
//
// Copyright (C) 2012 Desire Nuentsa Wakam <desire.nuentsa_wakam@inria.fr>
//
// This Source Code Form is subject to the terms of the Mozilla
// Public License v. 2.0. If a copy of the MPL was not distributed
// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
// This file is modified from the colamd/symamd library. The copyright is below
// The authors of the code itself are Stefan I. Larimore and Timothy A.
// Davis (davis@cise.ufl.edu), University of Florida. The algorithm was
// developed in collaboration with John Gilbert, Xerox PARC, and Esmond
// Ng, Oak Ridge National Laboratory.
//
// Date:
//
// September 8, 2003. Version 2.3.
//
// Acknowledgements:
//
// This work was supported by the National Science Foundation, under
// grants DMS-9504974 and DMS-9803599.
//
// Notice:
//
// Copyright (c) 1998-2003 by the University of Florida.
// All Rights Reserved.
//
// THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY
// EXPRESSED OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
//
// Permission is hereby granted to use, copy, modify, and/or distribute
// this program, provided that the Copyright, this License, and the
// Availability of the original version is retained on all copies and made
// accessible to the end-user of any code or package that includes COLAMD
// or any modified version of COLAMD.
//
// Availability:
//
// The colamd/symamd library is available at
//
// http://www.suitesparse.com
#ifndef EIGEN_COLAMD_H
#define EIGEN_COLAMD_H
namespace internal {
/* Ensure that debugging is turned off: */
#ifndef COLAMD_NDEBUG
#define COLAMD_NDEBUG
#endif /* NDEBUG */
/* ========================================================================== */
/* === Knob and statistics definitions ====================================== */
/* ========================================================================== */
/* size of the knobs [ ] array. Only knobs [0..1] are currently used. */
#define COLAMD_KNOBS 20
/* number of output statistics. Only stats [0..6] are currently used. */
#define COLAMD_STATS 20
/* knobs [0] and stats [0]: dense row knob and output statistic. */
#define COLAMD_DENSE_ROW 0
/* knobs [1] and stats [1]: dense column knob and output statistic. */
#define COLAMD_DENSE_COL 1
/* stats [2]: memory defragmentation count output statistic */
#define COLAMD_DEFRAG_COUNT 2
/* stats [3]: colamd status: zero OK, > 0 warning or notice, < 0 error */
#define COLAMD_STATUS 3
/* stats [4..6]: error info, or info on jumbled columns */
#define COLAMD_INFO1 4
#define COLAMD_INFO2 5
#define COLAMD_INFO3 6
/* error codes returned in stats [3]: */
#define COLAMD_OK (0)
#define COLAMD_OK_BUT_JUMBLED (1)
#define COLAMD_ERROR_A_not_present (-1)
#define COLAMD_ERROR_p_not_present (-2)
#define COLAMD_ERROR_nrow_negative (-3)
#define COLAMD_ERROR_ncol_negative (-4)
#define COLAMD_ERROR_nnz_negative (-5)
#define COLAMD_ERROR_p0_nonzero (-6)
#define COLAMD_ERROR_A_too_small (-7)
#define COLAMD_ERROR_col_length_negative (-8)
#define COLAMD_ERROR_row_index_out_of_bounds (-9)
#define COLAMD_ERROR_out_of_memory (-10)
#define COLAMD_ERROR_internal_error (-999)
/* ========================================================================== */
/* === Definitions ========================================================== */
/* ========================================================================== */
#define ONES_COMPLEMENT(r) (-(r)-1)
/* -------------------------------------------------------------------------- */
#define COLAMD_EMPTY (-1)
/* Row and column status */
#define ALIVE (0)
#define DEAD (-1)
/* Column status */
#define DEAD_PRINCIPAL (-1)
#define DEAD_NON_PRINCIPAL (-2)
/* Macros for row and column status update and checking. */
#define ROW_IS_DEAD(r) ROW_IS_MARKED_DEAD (Row[r].shared2.mark)
#define ROW_IS_MARKED_DEAD(row_mark) (row_mark < ALIVE)
#define ROW_IS_ALIVE(r) (Row [r].shared2.mark >= ALIVE)
#define COL_IS_DEAD(c) (Col [c].start < ALIVE)
#define COL_IS_ALIVE(c) (Col [c].start >= ALIVE)
#define COL_IS_DEAD_PRINCIPAL(c) (Col [c].start == DEAD_PRINCIPAL)
#define KILL_ROW(r) { Row [r].shared2.mark = DEAD ; }
#define KILL_PRINCIPAL_COL(c) { Col [c].start = DEAD_PRINCIPAL ; }
#define KILL_NON_PRINCIPAL_COL(c) { Col [c].start = DEAD_NON_PRINCIPAL ; }
/* ========================================================================== */
/* === Colamd reporting mechanism =========================================== */
/* ========================================================================== */
// == Row and Column structures ==
IndexType start ; /* index for A of first row in this column, or DEAD */
IndexType thickness ; /* number of original columns represented by this */
IndexType parent ; /* parent in parent tree super-column structure, if */
IndexType score ; /* the score used to maintain heap, if col is alive */
IndexType order ; /* pivot ordering of this column, if col is dead */
IndexType headhash ; /* head of a hash bucket, if col is at the head of */
IndexType hash ; /* hash value, if col is not in a degree list */
IndexType prev ; /* previous column in degree list, if col is in a */
/* degree list (but not at the head of a degree list) */
} shared3 ;
union
{
IndexType degree_next ; /* next column, if col is in a degree list */
IndexType hash_next ; /* next column, if col is in a hash list */
IndexType start ; /* index for A of first col in this row */
IndexType length ; /* number of principal columns in this row */
IndexType degree ; /* number of principal & non-principal columns in row */
IndexType p ; /* used as a row pointer in init_rows_cols () */
IndexType mark ; /* for computing set differences and marking dead rows*/
IndexType first_column ;/* first column in row (used in garbage collection) */
} shared2 ;
};
/* ========================================================================== */
/* === Colamd recommended memory size ======================================= */
/* ========================================================================== */
/*
The recommended length Alen of the array A passed to colamd is given by
the COLAMD_RECOMMENDED (nnz, n_row, n_col) macro. It returns -1 if any
argument is negative. 2*nnz space is required for the row and column
indices of the matrix. colamd_c (n_col) + colamd_r (n_row) space is
required for the Col and Row arrays, respectively, which are internal to
colamd. An additional n_col space is the minimal amount of "elbow room",
and nnz/5 more space is recommended for run time efficiency.
This macro is not needed when using symamd.
Explicit typecast to IndexType added Sept. 23, 2002, COLAMD version 2.2, to avoid
Loading full blame...