1 /* ========================================================================== */
2 /* === Partition/cholmod_ccolamd ============================================ */
3 /* ========================================================================== */
4
5 /* -----------------------------------------------------------------------------
6 * CHOLMOD/Partition Module.
7 * Copyright (C) 2005-2013, Univ. of Florida. Author: Timothy A. Davis
8 * -------------------------------------------------------------------------- */
9
10 /* CHOLMOD interface to the CCOLAMD ordering routine. Finds a permutation
11 * p such that the Cholesky factorization of PAA'P' is sparser than AA'.
12 * The column etree is found and postordered, and the ccolamd ordering is then
13 * combined with its postordering. A must be unsymmetric.
14 *
15 * workspace: Iwork (MAX (nrow,ncol))
16 * Allocates a copy of its input matrix, which is
17 * then used as CCOLAMD's workspace.
18 *
19 * Supports any xtype (pattern, real, complex, or zomplex).
20 */
21
22 #ifndef NCAMD
23
24 #include "cholmod_internal.h"
25 #include "ccolamd.h"
26 #include "cholmod_camd.h"
27
28 #if (CCOLAMD_VERSION < CCOLAMD_VERSION_CODE (2,5))
29 #error "CCOLAMD v2.0 or later is required"
30 #endif
31
32 /* ========================================================================== */
33 /* === ccolamd_interface ==================================================== */
34 /* ========================================================================== */
35
36 /* Order with ccolamd */
37
ccolamd_interface(cholmod_sparse * A,size_t alen,Int * Perm,Int * Cmember,Int * fset,Int fsize,cholmod_sparse * C,cholmod_common * Common)38 static int ccolamd_interface
39 (
40 cholmod_sparse *A,
41 size_t alen,
42 Int *Perm,
43 Int *Cmember,
44 Int *fset,
45 Int fsize,
46 cholmod_sparse *C,
47 cholmod_common *Common
48 )
49 {
50 double knobs [CCOLAMD_KNOBS] ;
51 Int *Cp = NULL ;
52 Int ok, k, nrow, ncol, stats [CCOLAMD_STATS] ;
53
54 nrow = A->nrow ;
55 ncol = A->ncol ;
56
57 /* ---------------------------------------------------------------------- */
58 /* copy (and transpose) the input matrix A into the ccolamd workspace */
59 /* ---------------------------------------------------------------------- */
60
61 /* C = A (:,f)', which also packs A if needed. */
62 /* workspace: Iwork (nrow if no fset; MAX (nrow,ncol) if fset non-NULL) */
63 ok = CHOLMOD(transpose_unsym) (A, 0, NULL, fset, fsize, C, Common) ;
64
65 /* ---------------------------------------------------------------------- */
66 /* order the matrix (destroys the contents of C->i and C->p) */
67 /* ---------------------------------------------------------------------- */
68
69 /* get parameters */
70 #ifdef LONG
71 ccolamd_l_set_defaults (knobs) ;
72 #else
73 ccolamd_set_defaults (knobs) ;
74 #endif
75
76 if (Common->current < 0 || Common->current >= CHOLMOD_MAXMETHODS)
77 {
78 /* this is the CHOLMOD default, not the CCOLAMD default */
79 knobs [CCOLAMD_DENSE_ROW] = -1 ;
80 }
81 else
82 {
83 /* get the knobs from the Common parameters */
84 knobs [CCOLAMD_DENSE_COL] =Common->method[Common->current].prune_dense ;
85 knobs [CCOLAMD_DENSE_ROW] =Common->method[Common->current].prune_dense2;
86 knobs [CCOLAMD_AGGRESSIVE]=Common->method[Common->current].aggressive ;
87 knobs [CCOLAMD_LU] =Common->method[Common->current].order_for_lu;
88 }
89
90 if (ok)
91 {
92
93 #ifdef LONG
94 ccolamd_l (ncol, nrow, alen, C->i, C->p, knobs, stats, Cmember) ;
95 #else
96 ccolamd (ncol, nrow, alen, C->i, C->p, knobs, stats, Cmember) ;
97 #endif
98
99 ok = stats [CCOLAMD_STATUS] ;
100
101 ok = (ok == CCOLAMD_OK || ok == CCOLAMD_OK_BUT_JUMBLED) ;
102 /* permutation returned in C->p, if the ordering succeeded */
103 Cp = C->p ;
104 for (k = 0 ; k < nrow ; k++)
105 {
106 Perm [k] = Cp [k] ;
107 }
108 }
109
110 return (ok) ;
111 }
112
113
114 /* ========================================================================== */
115 /* === cholmod_ccolamd ====================================================== */
116 /* ========================================================================== */
117
118 /* Order AA' or A(:,f)*A(:,f)' using CCOLAMD. */
119
CHOLMOD(ccolamd)120 int CHOLMOD(ccolamd)
121 (
122 /* ---- input ---- */
123 cholmod_sparse *A, /* matrix to order */
124 Int *fset, /* subset of 0:(A->ncol)-1 */
125 size_t fsize, /* size of fset */
126 Int *Cmember, /* size A->nrow. Cmember [i] = c if row i is in the
127 * constraint set c. c must be >= 0. The # of
128 * constraint sets is max (Cmember) + 1. If Cmember is
129 * NULL, then it is interpretted as Cmember [i] = 0 for
130 * all i */
131 /* ---- output --- */
132 Int *Perm, /* size A->nrow, output permutation */
133 /* --------------- */
134 cholmod_common *Common
135 )
136 {
137 cholmod_sparse *C ;
138 Int ok, nrow, ncol ;
139 size_t alen ;
140
141 /* ---------------------------------------------------------------------- */
142 /* check inputs */
143 /* ---------------------------------------------------------------------- */
144
145 RETURN_IF_NULL_COMMON (FALSE) ;
146 RETURN_IF_NULL (A, FALSE) ;
147 RETURN_IF_NULL (Perm, FALSE) ;
148 RETURN_IF_XTYPE_INVALID (A, CHOLMOD_PATTERN, CHOLMOD_ZOMPLEX, FALSE) ;
149 if (A->stype != 0)
150 {
151 ERROR (CHOLMOD_INVALID, "matrix must be unsymmetric") ;
152 return (FALSE) ;
153 }
154 Common->status = CHOLMOD_OK ;
155
156 /* ---------------------------------------------------------------------- */
157 /* get inputs */
158 /* ---------------------------------------------------------------------- */
159
160 nrow = A->nrow ;
161 ncol = A->ncol ;
162
163 /* ---------------------------------------------------------------------- */
164 /* allocate workspace */
165 /* ---------------------------------------------------------------------- */
166
167 #ifdef LONG
168 alen = ccolamd_l_recommended (A->nzmax, ncol, nrow) ;
169 #else
170 alen = ccolamd_recommended (A->nzmax, ncol, nrow) ;
171 #endif
172
173 if (alen == 0)
174 {
175 ERROR (CHOLMOD_TOO_LARGE, "matrix invalid or too large") ;
176 return (FALSE) ;
177 }
178
179 CHOLMOD(allocate_work) (0, MAX (nrow,ncol), 0, Common) ;
180 if (Common->status < CHOLMOD_OK)
181 {
182 return (FALSE) ;
183 }
184
185 C = CHOLMOD(allocate_sparse) (ncol, nrow, alen, TRUE, TRUE, 0,
186 CHOLMOD_PATTERN, Common) ;
187
188 /* ---------------------------------------------------------------------- */
189 /* order with ccolamd */
190 /* ---------------------------------------------------------------------- */
191
192 ok = ccolamd_interface (A, alen, Perm, Cmember, fset, fsize, C, Common) ;
193
194 /* ---------------------------------------------------------------------- */
195 /* free the workspace and return result */
196 /* ---------------------------------------------------------------------- */
197
198 CHOLMOD(free_sparse) (&C, Common) ;
199 return (ok) ;
200 }
201 #endif
202