|
0
|
1 |
|
|
2 |
|
|
3 /* |
|
|
4 * -- SuperLU routine (version 2.0) -- |
|
|
5 * Univ. of California Berkeley, Xerox Palo Alto Research Center, |
|
|
6 * and Lawrence Berkeley National Lab. |
|
|
7 * November 15, 1997 |
|
|
8 * |
|
|
9 */ |
|
|
10 /* |
|
|
11 Copyright (c) 1994 by Xerox Corporation. All rights reserved. |
|
|
12 |
|
|
13 THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY |
|
|
14 EXPRESSED OR IMPLIED. ANY USE IS AT YOUR OWN RISK. |
|
|
15 |
|
|
16 Permission is hereby granted to use or copy this program for any |
|
|
17 purpose, provided the above notices are retained on all copies. |
|
|
18 Permission to modify the code and to distribute modified code is |
|
|
19 granted, provided the above notices are retained, and a notice that |
|
|
20 the code was modified is included with the above copyright notice. |
|
|
21 */ |
|
|
22 |
|
|
23 #include "dsp_defs.h" |
|
|
24 #include "util.h" |
|
|
25 |
|
|
26 int |
|
|
27 dsnode_dfs ( |
|
|
28 const int jcol, /* in - start of the supernode */ |
|
|
29 const int kcol, /* in - end of the supernode */ |
|
|
30 const int *asub, /* in */ |
|
|
31 const int *xa_begin, /* in */ |
|
|
32 const int *xa_end, /* in */ |
|
|
33 int *xprune, /* out */ |
|
|
34 int *marker, /* modified */ |
|
|
35 GlobalLU_t *Glu /* modified */ |
|
|
36 ) |
|
|
37 { |
|
|
38 /* Purpose |
|
|
39 * ======= |
|
|
40 * dsnode_dfs() - Determine the union of the row structures of those |
|
|
41 * columns within the relaxed snode. |
|
|
42 * Note: The relaxed snodes are leaves of the supernodal etree, therefore, |
|
|
43 * the portion outside the rectangular supernode must be zero. |
|
|
44 * |
|
|
45 * Return value |
|
|
46 * ============ |
|
|
47 * 0 success; |
|
|
48 * >0 number of bytes allocated when run out of memory. |
|
|
49 * |
|
|
50 */ |
|
|
51 register int i, k, ifrom, ito, nextl, new_next; |
|
|
52 int nsuper, krow, kmark, mem_error; |
|
|
53 int *xsup, *supno; |
|
|
54 int *lsub, *xlsub; |
|
|
55 int nzlmax; |
|
|
56 |
|
|
57 xsup = Glu->xsup; |
|
|
58 supno = Glu->supno; |
|
|
59 lsub = Glu->lsub; |
|
|
60 xlsub = Glu->xlsub; |
|
|
61 nzlmax = Glu->nzlmax; |
|
|
62 |
|
|
63 nsuper = ++supno[jcol]; /* Next available supernode number */ |
|
|
64 nextl = xlsub[jcol]; |
|
|
65 |
|
|
66 for (i = jcol; i <= kcol; i++) { |
|
|
67 /* For each nonzero in A[*,i] */ |
|
|
68 for (k = xa_begin[i]; k < xa_end[i]; k++) { |
|
|
69 krow = asub[k]; |
|
|
70 kmark = marker[krow]; |
|
|
71 if ( kmark != kcol ) { /* First time visit krow */ |
|
|
72 marker[krow] = kcol; |
|
|
73 lsub[nextl++] = krow; |
|
|
74 if ( nextl >= nzlmax ) { |
|
|
75 if ( mem_error = dLUMemXpand(jcol, nextl, LSUB, &nzlmax, Glu) ) |
|
|
76 return (mem_error); |
|
|
77 lsub = Glu->lsub; |
|
|
78 } |
|
|
79 } |
|
|
80 } |
|
|
81 supno[i] = nsuper; |
|
|
82 } |
|
|
83 |
|
|
84 /* Supernode > 1, then make a copy of the subscripts for pruning */ |
|
|
85 if ( jcol < kcol ) { |
|
|
86 new_next = nextl + (nextl - xlsub[jcol]); |
|
|
87 while ( new_next > nzlmax ) { |
|
|
88 if ( mem_error = dLUMemXpand(jcol, nextl, LSUB, &nzlmax, Glu) ) |
|
|
89 return (mem_error); |
|
|
90 lsub = Glu->lsub; |
|
|
91 } |
|
|
92 ito = nextl; |
|
|
93 for (ifrom = xlsub[jcol]; ifrom < nextl; ) |
|
|
94 lsub[ito++] = lsub[ifrom++]; |
|
|
95 for (i = jcol+1; i <= kcol; i++) xlsub[i] = nextl; |
|
|
96 nextl = ito; |
|
|
97 } |
|
|
98 |
|
|
99 xsup[nsuper+1] = kcol + 1; |
|
|
100 supno[kcol+1] = nsuper; |
|
|
101 xprune[kcol] = nextl; |
|
|
102 xlsub[kcol+1] = nextl; |
|
|
103 |
|
|
104 return 0; |
|
|
105 } |
|
|
106 |
