1
2 /*! @file dpanel_dfs.c
3 * \brief Peforms a symbolic factorization on a panel of symbols
4 *
5 * <pre>
6 * -- SuperLU routine (version 2.0) --
7 * Univ. of California Berkeley, Xerox Palo Alto Research Center,
8 * and Lawrence Berkeley National Lab.
9 * November 15, 1997
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 * </pre>
22 */
23
24
25 #include "slu_ddefs.h"
26
27 /*! \brief
28 *
29 * <pre>
30 * Purpose
31 * =======
32 *
33 * Performs a symbolic factorization on a panel of columns [jcol, jcol+w).
34 *
35 * A supernode representative is the last column of a supernode.
36 * The nonzeros in U[*,j] are segments that end at supernodal
37 * representatives.
38 *
39 * The routine returns one list of the supernodal representatives
40 * in topological order of the dfs that generates them. This list is
41 * a superset of the topological order of each individual column within
42 * the panel.
43 * The location of the first nonzero in each supernodal segment
44 * (supernodal entry location) is also returned. Each column has a
45 * separate list for this purpose.
46 *
47 * Two marker arrays are used for dfs:
48 * marker[i] == jj, if i was visited during dfs of current column jj;
49 * marker1[i] >= jcol, if i was visited by earlier columns in this panel;
50 *
51 * marker: A-row --> A-row/col (0/1)
52 * repfnz: SuperA-col --> PA-row
53 * parent: SuperA-col --> SuperA-col
54 * xplore: SuperA-col --> index to L-structure
55 * </pre>
56 */
57
58 void
dpanel_dfs(const int m,const int w,const int jcol,SuperMatrix * A,int * perm_r,int * nseg,double * dense,int * panel_lsub,int * segrep,int * repfnz,int * xprune,int * marker,int * parent,int * xplore,GlobalLU_t * Glu)59 dpanel_dfs (
60 const int m, /* in - number of rows in the matrix */
61 const int w, /* in */
62 const int jcol, /* in */
63 SuperMatrix *A, /* in - original matrix */
64 int *perm_r, /* in */
65 int *nseg, /* out */
66 double *dense, /* out */
67 int *panel_lsub, /* out */
68 int *segrep, /* out */
69 int *repfnz, /* out */
70 int *xprune, /* out */
71 int *marker, /* out */
72 int *parent, /* working array */
73 int *xplore, /* working array */
74 GlobalLU_t *Glu /* modified */
75 )
76 {
77
78 NCPformat *Astore;
79 double *a;
80 int *asub;
81 int *xa_begin, *xa_end;
82 int krep, chperm, chmark, chrep, oldrep, kchild, myfnz;
83 int k, krow, kmark, kperm;
84 int xdfs, maxdfs, kpar;
85 int jj; /* index through each column in the panel */
86 int *marker1; /* marker1[jj] >= jcol if vertex jj was visited
87 by a previous column within this panel. */
88 int *repfnz_col; /* start of each column in the panel */
89 double *dense_col; /* start of each column in the panel */
90 int nextl_col; /* next available position in panel_lsub[*,jj] */
91 int *xsup, *supno;
92 int *lsub, *xlsub;
93
94 /* Initialize pointers */
95 Astore = A->Store;
96 a = Astore->nzval;
97 asub = Astore->rowind;
98 xa_begin = Astore->colbeg;
99 xa_end = Astore->colend;
100 marker1 = marker + m;
101 repfnz_col = repfnz;
102 dense_col = dense;
103 *nseg = 0;
104 xsup = Glu->xsup;
105 supno = Glu->supno;
106 lsub = Glu->lsub;
107 xlsub = Glu->xlsub;
108
109 /* For each column in the panel */
110 for (jj = jcol; jj < jcol + w; jj++) {
111 nextl_col = (jj - jcol) * m;
112
113 #ifdef CHK_DFS
114 printf("\npanel col %d: ", jj);
115 #endif
116
117 /* For each nonz in A[*,jj] do dfs */
118 for (k = xa_begin[jj]; k < xa_end[jj]; k++) {
119 krow = asub[k];
120 dense_col[krow] = a[k];
121 kmark = marker[krow];
122 if ( kmark == jj )
123 continue; /* krow visited before, go to the next nonzero */
124
125 /* For each unmarked nbr krow of jj
126 * krow is in L: place it in structure of L[*,jj]
127 */
128 marker[krow] = jj;
129 kperm = perm_r[krow];
130
131 if ( kperm == EMPTY ) {
132 panel_lsub[nextl_col++] = krow; /* krow is indexed into A */
133 }
134 /*
135 * krow is in U: if its supernode-rep krep
136 * has been explored, update repfnz[*]
137 */
138 else {
139
140 krep = xsup[supno[kperm]+1] - 1;
141 myfnz = repfnz_col[krep];
142
143 #ifdef CHK_DFS
144 printf("krep %d, myfnz %d, perm_r[%d] %d\n", krep, myfnz, krow, kperm);
145 #endif
146 if ( myfnz != EMPTY ) { /* Representative visited before */
147 if ( myfnz > kperm ) repfnz_col[krep] = kperm;
148 /* continue; */
149 }
150 else {
151 /* Otherwise, perform dfs starting at krep */
152 oldrep = EMPTY;
153 parent[krep] = oldrep;
154 repfnz_col[krep] = kperm;
155 xdfs = xlsub[krep];
156 maxdfs = xprune[krep];
157
158 #ifdef CHK_DFS
159 printf(" xdfs %d, maxdfs %d: ", xdfs, maxdfs);
160 for (i = xdfs; i < maxdfs; i++) printf(" %d", lsub[i]);
161 printf("\n");
162 #endif
163 do {
164 /*
165 * For each unmarked kchild of krep
166 */
167 while ( xdfs < maxdfs ) {
168
169 kchild = lsub[xdfs];
170 xdfs++;
171 chmark = marker[kchild];
172
173 if ( chmark != jj ) { /* Not reached yet */
174 marker[kchild] = jj;
175 chperm = perm_r[kchild];
176
177 /* Case kchild is in L: place it in L[*,j] */
178 if ( chperm == EMPTY ) {
179 panel_lsub[nextl_col++] = kchild;
180 }
181 /* Case kchild is in U:
182 * chrep = its supernode-rep. If its rep has
183 * been explored, update its repfnz[*]
184 */
185 else {
186
187 chrep = xsup[supno[chperm]+1] - 1;
188 myfnz = repfnz_col[chrep];
189 #ifdef CHK_DFS
190 printf("chrep %d,myfnz %d,perm_r[%d] %d\n",chrep,myfnz,kchild,chperm);
191 #endif
192 if ( myfnz != EMPTY ) { /* Visited before */
193 if ( myfnz > chperm )
194 repfnz_col[chrep] = chperm;
195 }
196 else {
197 /* Cont. dfs at snode-rep of kchild */
198 xplore[krep] = xdfs;
199 oldrep = krep;
200 krep = chrep; /* Go deeper down G(L) */
201 parent[krep] = oldrep;
202 repfnz_col[krep] = chperm;
203 xdfs = xlsub[krep];
204 maxdfs = xprune[krep];
205 #ifdef CHK_DFS
206 printf(" xdfs %d, maxdfs %d: ", xdfs, maxdfs);
207 for (i = xdfs; i < maxdfs; i++) printf(" %d", lsub[i]);
208 printf("\n");
209 #endif
210 } /* else */
211
212 } /* else */
213
214 } /* if... */
215
216 } /* while xdfs < maxdfs */
217
218 /* krow has no more unexplored nbrs:
219 * Place snode-rep krep in postorder DFS, if this
220 * segment is seen for the first time. (Note that
221 * "repfnz[krep]" may change later.)
222 * Backtrack dfs to its parent.
223 */
224 if ( marker1[krep] < jcol ) {
225 segrep[*nseg] = krep;
226 ++(*nseg);
227 marker1[krep] = jj;
228 }
229
230 kpar = parent[krep]; /* Pop stack, mimic recursion */
231 if ( kpar == EMPTY ) break; /* dfs done */
232 krep = kpar;
233 xdfs = xplore[krep];
234 maxdfs = xprune[krep];
235
236 #ifdef CHK_DFS
237 printf(" pop stack: krep %d,xdfs %d,maxdfs %d: ", krep,xdfs,maxdfs);
238 for (i = xdfs; i < maxdfs; i++) printf(" %d", lsub[i]);
239 printf("\n");
240 #endif
241 } while ( kpar != EMPTY ); /* do-while - until empty stack */
242
243 } /* else */
244
245 } /* else */
246
247 } /* for each nonz in A[*,jj] */
248
249 repfnz_col += m; /* Move to next column */
250 dense_col += m;
251
252 } /* for jj ... */
253
254 }
255