Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
Amd.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2010 Gael Guennebaud <gael.guennebaud@inria.fr>
5//
6// This Source Code Form is subject to the terms of the Mozilla
7// Public License v. 2.0. If a copy of the MPL was not distributed
8// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9// SPDX-License-Identifier: MPL-2.0
10
11/*
12NOTE: this routine has been adapted from the CSparse library:
13
14Copyright (c) 2006, Timothy A. Davis.
15http://www.suitesparse.com
16
17The author of CSparse, Timothy A. Davis., has executed a license with Google LLC
18to permit distribution of this code and derivative works as part of Eigen under
19the Mozilla Public License v. 2.0, as stated at the top of this file.
20*/
21
22#ifndef EIGEN_SPARSE_AMD_H
23#define EIGEN_SPARSE_AMD_H
24
25// IWYU pragma: private
26#include "./InternalHeaderCheck.h"
27
28namespace Eigen {
29
30namespace internal {
31
32template <typename T>
33inline T amd_flip(const T& i) {
34 return -i - 2;
35}
36
37/* clear w */
38template <typename StorageIndex>
39static StorageIndex cs_wclear(StorageIndex mark, StorageIndex lemax, StorageIndex* w, StorageIndex n) {
40 StorageIndex k;
41 if (mark < 2 || (mark + lemax < 0)) {
42 for (k = 0; k < n; k++)
43 if (w[k] != 0) w[k] = 1;
44 mark = 2;
45 }
46 return (mark); /* at this point, w[0..n-1] < mark holds */
47}
48
49/* depth-first search and postorder of a tree rooted at node j */
50template <typename StorageIndex>
51StorageIndex cs_tdfs(StorageIndex j, StorageIndex k, StorageIndex* head, const StorageIndex* next, StorageIndex* post,
52 StorageIndex* stack) {
53 StorageIndex i, p, top = 0;
54 if (!head || !next || !post || !stack) return (-1); /* check inputs */
55 stack[0] = j; /* place j on the stack */
56 while (top >= 0) /* while (stack is not empty) */
57 {
58 p = stack[top]; /* p = top of stack */
59 i = head[p]; /* i = youngest child of p */
60 if (i == -1) {
61 top--; /* p has no unordered children left */
62 post[k++] = p; /* node p is the kth postordered node */
63 } else {
64 head[p] = next[i]; /* remove i from children of p */
65 stack[++top] = i; /* start dfs on child node i */
66 }
67 }
68 return k;
69}
70
80template <typename Scalar, typename StorageIndex>
81void minimum_degree_ordering(SparseMatrix<Scalar, ColMajor, StorageIndex>& C,
82 PermutationMatrix<Dynamic, Dynamic, StorageIndex>& perm) {
83 StorageIndex d, dk, dext, lemax = 0, e, elenk, eln, i, j, k, k1, k2, k3, jlast, ln, dense, nzmax, mindeg = 0, nvi,
84 nvj, nvk, mark, wnvi, ok, nel = 0, p, p1, p2, p3, p4, pj, pk, pk1, pk2, pn, q, t, h;
85 // Unsigned, so that the sum of up to `dense` indices wraps instead of overflowing and hash % n is in [0, n),
86 // as in SuiteSparse AMD (amd_2.c).
87 using UnsignedIndex = std::make_unsigned_t<StorageIndex>;
88 UnsignedIndex hash;
89
90 StorageIndex n = StorageIndex(C.cols());
91 dense = std::max<StorageIndex>(16, StorageIndex(10 * numext::sqrt(double(n)))); /* find dense threshold */
92 dense = (std::min)(n - 2, dense);
93
94 StorageIndex cnz = StorageIndex(C.nonZeros());
95 perm.resize(n + 1);
96 t = cnz + cnz / 5 + 2 * n; /* add elbow room to C */
97 C.resizeNonZeros(t);
98
99 // get workspace
100 ei_declare_aligned_stack_constructed_variable(StorageIndex, W, 8 * (n + 1), 0);
101 StorageIndex* len = W;
102 StorageIndex* nv = W + (n + 1);
103 StorageIndex* next = W + 2 * (n + 1);
104 StorageIndex* head = W + 3 * (n + 1);
105 StorageIndex* elen = W + 4 * (n + 1);
106 StorageIndex* degree = W + 5 * (n + 1);
107 StorageIndex* w = W + 6 * (n + 1);
108 StorageIndex* hhead = W + 7 * (n + 1);
109 StorageIndex* last = perm.indices().data(); /* use P as workspace for last */
110
111 /* --- Initialize quotient graph ---------------------------------------- */
112 StorageIndex* Cp = C.outerIndexPtr();
113 StorageIndex* Ci = C.innerIndexPtr();
114 for (k = 0; k < n; k++) len[k] = Cp[k + 1] - Cp[k];
115 len[n] = 0;
116 nzmax = t;
117
118 for (i = 0; i <= n; i++) {
119 head[i] = -1; // degree list i is empty
120 last[i] = -1;
121 next[i] = -1;
122 hhead[i] = -1; // hash list i is empty
123 nv[i] = 1; // node i is just one node
124 w[i] = 1; // node i is alive
125 elen[i] = 0; // Ek of node i is empty
126 degree[i] = len[i]; // degree of node i
127 }
128 mark = internal::cs_wclear<StorageIndex>(0, 0, w, n); /* clear w */
129
130 /* --- Initialize degree lists ------------------------------------------ */
131 for (i = 0; i < n; i++) {
132 bool has_diag = false;
133 for (p = Cp[i]; p < Cp[i + 1]; ++p)
134 if (Ci[p] == i) {
135 has_diag = true;
136 break;
137 }
138
139 d = degree[i];
140 if (d == 1 && has_diag) /* node i is empty */
141 {
142 elen[i] = -2; /* element i is dead */
143 nel++;
144 Cp[i] = -1; /* i is a root of assembly tree */
145 w[i] = 0;
146 } else if (d > dense || !has_diag) /* node i is dense or has no structural diagonal element */
147 {
148 nv[i] = 0; /* absorb i into element n */
149 elen[i] = -1; /* node i is dead */
150 nel++;
151 Cp[i] = amd_flip(n);
152 nv[n]++;
153 } else {
154 if (head[d] != -1) last[head[d]] = i;
155 next[i] = head[d]; /* put node i in degree list d */
156 head[d] = i;
157 }
158 }
159
160 elen[n] = -2; /* n is a dead element */
161 Cp[n] = -1; /* n is a root of assembly tree */
162 w[n] = 0; /* n is a dead element */
163
164 while (nel < n) /* while (selecting pivots) do */
165 {
166 /* --- Select node of minimum approximate degree -------------------- */
167 for (k = -1; mindeg < n && (k = head[mindeg]) == -1; mindeg++) {
168 }
169 if (next[k] != -1) last[next[k]] = -1;
170 head[mindeg] = next[k]; /* remove k from degree list */
171 elenk = elen[k]; /* elenk = |Ek| */
172 nvk = nv[k]; /* # of nodes k represents */
173 nel += nvk; /* nv[k] nodes of A eliminated */
174
175 /* --- Garbage collection ------------------------------------------- */
176 if (elenk > 0 && cnz + mindeg >= nzmax) {
177 for (j = 0; j < n; j++) {
178 p = Cp[j];
179 if (p >= 0) /* j is a live node or element */
180 {
181 Cp[j] = Ci[p]; /* save first entry of object */
182 Ci[p] = amd_flip(j); /* first entry is now amd_flip(j) */
183 }
184 }
185 for (q = 0, p = 0; p < cnz;) /* scan all of memory */
186 {
187 j = amd_flip(Ci[p++]);
188 if (j >= 0) /* found object j */
189 {
190 Ci[q] = Cp[j]; /* restore first entry of object */
191 Cp[j] = q++; /* new pointer to object j */
192 for (k3 = 0; k3 < len[j] - 1; k3++) Ci[q++] = Ci[p++];
193 }
194 }
195 cnz = q; /* Ci[cnz...nzmax-1] now free */
196 }
197
198 /* --- Construct new element ---------------------------------------- */
199 dk = 0;
200 nv[k] = -nvk; /* flag k as in Lk */
201 p = Cp[k];
202 pk1 = (elenk == 0) ? p : cnz; /* do in place if elen[k] == 0 */
203 pk2 = pk1;
204 for (k1 = 1; k1 <= elenk + 1; k1++) {
205 if (k1 > elenk) {
206 e = k; /* search the nodes in k */
207 pj = p; /* list of nodes starts at Ci[pj]*/
208 ln = len[k] - elenk; /* length of list of nodes in k */
209 } else {
210 e = Ci[p++]; /* search the nodes in e */
211 pj = Cp[e];
212 ln = len[e]; /* length of list of nodes in e */
213 }
214 for (k2 = 1; k2 <= ln; k2++) {
215 i = Ci[pj++];
216 nvi = nv[i];
217 if (nvi <= 0) continue; /* node i dead, or seen */
218 dk += nvi; /* degree[Lk] += size of node i */
219 nv[i] = -nvi; /* negate nv[i] to denote i in Lk*/
220 Ci[pk2++] = i; /* place i in Lk */
221 if (next[i] != -1) last[next[i]] = last[i];
222 if (last[i] != -1) /* remove i from degree list */
223 {
224 next[last[i]] = next[i];
225 } else {
226 head[degree[i]] = next[i];
227 }
228 }
229 if (e != k) {
230 Cp[e] = amd_flip(k); /* absorb e into k */
231 w[e] = 0; /* e is now a dead element */
232 }
233 }
234 if (elenk != 0) cnz = pk2; /* Ci[cnz...nzmax] is free */
235 degree[k] = dk; /* external degree of k - |Lk\i| */
236 Cp[k] = pk1; /* element k is in Ci[pk1..pk2-1] */
237 len[k] = pk2 - pk1;
238 elen[k] = -2; /* k is now an element */
239
240 /* --- Find set differences ----------------------------------------- */
241 mark = internal::cs_wclear<StorageIndex>(mark, lemax, w, n); /* clear w if necessary */
242 for (pk = pk1; pk < pk2; pk++) /* scan 1: find |Le\Lk| */
243 {
244 i = Ci[pk];
245 eln = elen[i];
246 if (eln <= 0) continue; /* skip if elen[i] empty */
247 nvi = -nv[i]; /* nv[i] was negated */
248 wnvi = mark - nvi;
249 for (p = Cp[i]; p <= Cp[i] + eln - 1; p++) /* scan Ei */
250 {
251 e = Ci[p];
252 if (w[e] >= mark) {
253 w[e] -= nvi; /* decrement |Le\Lk| */
254 } else if (w[e] != 0) /* ensure e is a live element */
255 {
256 w[e] = degree[e] + wnvi; /* 1st time e seen in scan 1 */
257 }
258 }
259 }
260
261 /* --- Degree update ------------------------------------------------ */
262 for (pk = pk1; pk < pk2; pk++) /* scan2: degree update */
263 {
264 i = Ci[pk]; /* consider node i in Lk */
265 p1 = Cp[i];
266 p2 = p1 + elen[i] - 1;
267 pn = p1;
268 for (hash = 0, d = 0, p = p1; p <= p2; p++) /* scan Ei */
269 {
270 e = Ci[p];
271 if (w[e] != 0) /* e is an unabsorbed element */
272 {
273 dext = w[e] - mark; /* dext = |Le\Lk| */
274 if (dext > 0) {
275 d += dext; /* sum up the set differences */
276 Ci[pn++] = e; /* keep e in Ei */
277 hash += UnsignedIndex(e); /* compute the hash of node i */
278 } else {
279 Cp[e] = amd_flip(k); /* aggressive absorb. e->k */
280 w[e] = 0; /* e is a dead element */
281 }
282 }
283 }
284 elen[i] = pn - p1 + 1; /* elen[i] = |Ei| */
285 p3 = pn;
286 p4 = p1 + len[i];
287 for (p = p2 + 1; p < p4; p++) /* prune edges in Ai */
288 {
289 j = Ci[p];
290 nvj = nv[j];
291 if (nvj <= 0) continue; /* node j dead or in Lk */
292 d += nvj; /* degree(i) += |j| */
293 Ci[pn++] = j; /* place j in node list of i */
294 hash += UnsignedIndex(j); /* compute hash for node i */
295 }
296 if (d == 0) /* check for mass elimination */
297 {
298 Cp[i] = amd_flip(k); /* absorb i into k */
299 nvi = -nv[i];
300 dk -= nvi; /* |Lk| -= |i| */
301 nvk += nvi; /* |k| += nv[i] */
302 nel += nvi;
303 nv[i] = 0;
304 elen[i] = -1; /* node i is dead */
305 } else {
306 degree[i] = std::min<StorageIndex>(degree[i], d); /* update degree(i) */
307 Ci[pn] = Ci[p3]; /* move first node to end */
308 Ci[p3] = Ci[p1]; /* move 1st el. to end of Ei */
309 Ci[p1] = k; /* add k as 1st element in Ei */
310 len[i] = pn - p1 + 1; /* new len of adj. list of node i */
311 h = StorageIndex(hash % UnsignedIndex(n)); /* finalize hash of i */
312 next[i] = hhead[h]; /* place i in hash bucket */
313 hhead[h] = i;
314 last[i] = h; /* save hash of i in last[i] */
315 }
316 } /* scan2 is done */
317 degree[k] = dk; /* finalize |Lk| */
318 lemax = std::max<StorageIndex>(lemax, dk);
319 mark = internal::cs_wclear<StorageIndex>(mark + lemax, lemax, w, n); /* clear w */
320
321 /* --- Supernode detection ------------------------------------------ */
322 for (pk = pk1; pk < pk2; pk++) {
323 i = Ci[pk];
324 if (nv[i] >= 0) continue; /* skip if i is dead */
325 h = last[i]; /* scan hash bucket of node i */
326 i = hhead[h];
327 hhead[h] = -1; /* hash bucket will be empty */
328 for (; i != -1 && next[i] != -1; i = next[i], mark++) {
329 ln = len[i];
330 eln = elen[i];
331 for (p = Cp[i] + 1; p <= Cp[i] + ln - 1; p++) w[Ci[p]] = mark;
332 jlast = i;
333 for (j = next[i]; j != -1;) /* compare i with all j */
334 {
335 ok = (len[j] == ln) && (elen[j] == eln);
336 for (p = Cp[j] + 1; ok && p <= Cp[j] + ln - 1; p++) {
337 if (w[Ci[p]] != mark) ok = 0; /* compare i and j*/
338 }
339 if (ok) /* i and j are identical */
340 {
341 Cp[j] = amd_flip(i); /* absorb j into i */
342 nv[i] += nv[j];
343 nv[j] = 0;
344 elen[j] = -1; /* node j is dead */
345 j = next[j]; /* delete j from hash bucket */
346 next[jlast] = j;
347 } else {
348 jlast = j; /* j and i are different */
349 j = next[j];
350 }
351 }
352 }
353 }
354
355 /* --- Finalize new element------------------------------------------ */
356 for (p = pk1, pk = pk1; pk < pk2; pk++) /* finalize Lk */
357 {
358 i = Ci[pk];
359 nvi = -nv[i];
360 if (nvi <= 0) continue; /* skip if i is dead */
361 nv[i] = nvi; /* restore nv[i] */
362 d = degree[i] + dk - nvi; /* compute external degree(i) */
363 d = std::min<StorageIndex>(d, n - nel - nvi);
364 if (head[d] != -1) last[head[d]] = i;
365 next[i] = head[d]; /* put i back in degree list */
366 last[i] = -1;
367 head[d] = i;
368 mindeg = std::min<StorageIndex>(mindeg, d); /* find new minimum degree */
369 degree[i] = d;
370 Ci[p++] = i; /* place i in Lk */
371 }
372 nv[k] = nvk; /* # nodes absorbed into k */
373 len[k] = p - pk1;
374 if (len[k] == 0) /* length of adj list of element k*/
375 {
376 Cp[k] = -1; /* k is a root of the tree */
377 w[k] = 0; /* k is now a dead element */
378 }
379 if (elenk != 0) cnz = p; /* free unused space in Lk */
380 }
381
382 /* --- Postordering ----------------------------------------------------- */
383 for (i = 0; i < n; i++) Cp[i] = amd_flip(Cp[i]); /* fix assembly tree */
384 for (j = 0; j <= n; j++) head[j] = -1;
385 for (j = n; j >= 0; j--) /* place unordered nodes in lists */
386 {
387 if (nv[j] > 0) continue; /* skip if j is an element */
388 next[j] = head[Cp[j]]; /* place j in list of its parent */
389 head[Cp[j]] = j;
390 }
391 for (e = n; e >= 0; e--) /* place elements in lists */
392 {
393 if (nv[e] <= 0) continue; /* skip unless e is an element */
394 if (Cp[e] != -1) {
395 next[e] = head[Cp[e]]; /* place e in list of its parent */
396 head[Cp[e]] = e;
397 }
398 }
399 for (k = 0, i = 0; i <= n; i++) /* postorder the assembly tree */
400 {
401 if (Cp[i] == -1) k = internal::cs_tdfs<StorageIndex>(i, k, head, next, perm.indices().data(), w);
402 }
403
404 perm.indices().conservativeResize(n);
405}
406
407} // namespace internal
408
409} // end namespace Eigen
410
411#endif // EIGEN_SPARSE_AMD_H