1 #include "BSprivate.h"
2
3 /*@ BSmain_perm - Permute the matrix for efficient parallel execution
4
5 Input Parameters:
6 . procinfo - the usual processor context information
7 . A - the sparse matrix
8
9 Returns:
10 the sparse matrix permuted into an efficient structure
11
12 Notes:
13 $ (1) The sparse matrix must be symmetric in structure
14 $ (2) The graph associated with the sparse matrix must be connected
15 $ (3) max_inode_size and max_clique_size should usually be set to
16 $ INT_MAX (they are kept in the context)
17 $ (4) see the manual for more details on what algorithms BSmain_perm uses
18 $ (5) the context variable "retain" will indicate whether or not
19 $ some extra data should be kept around to allow for fast permutation
20 $ of a matrix with the same structure in the future
21
22 @*/
BSmain_perm(BSprocinfo * procinfo,BSspmat * A)23 BSpar_mat *BSmain_perm(BSprocinfo *procinfo, BSspmat *A)
24 {
25 BSpar_mat *pA;
26 BSnumbering *inode_number;
27 BSdistribution *inode_distr;
28 BSpermutation *inode_perm;
29 BSnumbering *inode_row;
30 BSnumbering *clique_number;
31 BSdistribution *clique_distr;
32 BSpermutation *clique_perm;
33 BSnumbering *color_number;
34 BSdistribution *color_distr;
35 BSpermutation *color_perm;
36 BSspmat *iA;
37 BSspmat *cA;
38 BSnumbering *color_offset;
39 BSnumbering *color_base;
40 BSdistribution *new_clique_distr;
41 BSdistribution *new_color_distr;
42 BSnumbering *clique_gnum;
43 BSnumbering *inode_gnum;
44 BSnumbering *row_gnum;
45 BScl_2_inode *col_cA;
46 BSinode_list *col_iA;
47 BSnumbering *color_2_cl;
48 BSkey_arr *key_arr;
49 BSsprow **perm_rows;
50 BSpermutation *g_perm, *g_iperm;
51 int max_gcolors;
52 int max_row_len;
53 int local_num_inodes, global_num_inodes;
54 int local_num_cliques, global_num_cliques;
55 int num_colors;
56 int ierr;
57
58 /* *************************************************************** */
59 /* BEGIN SECTION: */
60 /* Find the various permutations and contracted graphs */
61 /* *************************************************************** */
62
63 /* first check that matrix symmetry property and storage will work */
64 if((!A->symmetric)&&(A->icc_storage)) {
65 MY_SETERRCN(SYM_ERROR,"Attempt to store nonsymmetric matrix in ICC structure\n");
66 }
67
68 /* check rows for consistency */
69 if (procinfo->error_check) {
70 BSrow_err_check(A,procinfo); CHKERRN(0);
71 }
72
73 /* now get an i-node numbering */
74 MLOG_ELM(procinfo->procset);
75 inode_number = BSfnd_inode(A,procinfo->max_inode_size,procinfo); CHKERRN(0);
76
77 inode_distr = BSnum2distr(inode_number); CHKERRN(0);
78
79 inode_perm = BSnum2perm(inode_number,inode_distr); CHKERRN(0);
80
81 inode_row = BSlow2high(A,inode_number,inode_distr,procinfo); CHKERRN(0);
82
83 if (procinfo->single) {
84 iA = A;
85 } else {
86 iA = BSdo_contract(A,inode_number,inode_perm,procinfo,TRUE); CHKERRN(0);
87 }
88
89 MLOG_IT(INODE);
90 local_num_inodes = iA->num_rows;
91 global_num_inodes = iA->global_num_rows;
92 if ((procinfo->print) && (PSISROOT(procinfo))) {
93 printf("************** Blocksolve Reordering Info *****************\n");
94 printf("o Inode graph size is %d\n",iA->global_num_rows);
95 }
96
97 /* check rows for consistency */
98 if (procinfo->error_check) {
99 BSrow_err_check(iA,procinfo); CHKERRN(0);
100 }
101
102 /* now get a clique numbering */
103 MLOG_ELM(procinfo->procset);
104 clique_number = BSfnd_clique(iA,procinfo->max_clique_size,
105 inode_distr->distribution,procinfo); CHKERRN(0);
106 clique_distr = BSnum2distr(clique_number); CHKERRN(0);
107 clique_perm = BSnum2perm(clique_number,clique_distr); CHKERRN(0);
108 if (procinfo->single) {
109 cA = A;
110 } else {
111 cA = BSdo_contract(iA,clique_number,clique_perm,procinfo,FALSE);
112 CHKERRN(0);
113 }
114 MLOG_IT(CLIQUE);
115 local_num_cliques = cA->num_rows;
116 global_num_cliques = cA->global_num_rows;
117 if ((procinfo->print) && (PSISROOT(procinfo))) {
118 printf("o Clique graph size is %d\n",cA->global_num_rows);
119 }
120
121 /* find weights */
122 new_clique_distr = BSfold_distr(clique_distr,inode_distr,clique_number);
123 CHKERRN(0);
124
125 /* now do the coloring */
126 BSrem_diag(cA); CHKERRN(0);
127 color_number = BSalloc_numbering(cA->num_rows); CHKERRN(0);
128 BSx_color(color_number->numbers,cA,procinfo,&max_gcolors,
129 procinfo->coloring_type); CHKERRN(0);
130 color_distr = BSnum2distr(color_number); CHKERRN(0);
131 color_perm = BSnum2perm(color_number,color_distr); CHKERRN(0);
132 BSins_diag(cA); CHKERRN(0);
133 /* check rows for consistency */
134 if (procinfo->error_check) {
135 BSrow_err_check(cA,procinfo); CHKERRN(0);
136 }
137
138 /* *************************************************************** */
139 /* END SECTION: */
140 /* *************************************************************** */
141
142 /* *************************************************************** */
143 /* BEGIN SECTION: */
144 /* Find global row numbers */
145 /* *************************************************************** */
146 MLOG_ELM(procinfo->procset);
147 new_color_distr = BSfold_distr(color_distr,new_clique_distr,color_number);
148 CHKERRN(0);
149
150 /* find the new global offsets for the colors */
151 MY_MALLOCN(color_offset,(BSnumbering *),sizeof(BSnumbering),1);
152 color_offset->length = BSoffset(new_color_distr->max+1,
153 new_color_distr->distribution,&(color_offset->numbers),procinfo);
154 CHKERRN(0);
155 num_colors = color_offset->length;
156 if ((procinfo->print) && (PSISROOT(procinfo))) {
157 printf("o Number of colors is %d\n",color_offset->length);
158 }
159
160 /* find the new global base addresses for the colors */
161 /* this is the same on every processors */
162 color_base = BSbase(new_color_distr,procinfo); CHKERRN(0);
163
164 /* find the new global offsets for the cliques */
165 clique_gnum = BSoff_gnum(color_offset,color_number,new_clique_distr);
166 CHKERRN(0);
167
168 /* find the new global offsets for the inodes */
169 inode_gnum = BSoff_gnum(clique_gnum,clique_number,inode_distr); CHKERRN(0);
170
171 /* find the new global addresses for the rows */
172 row_gnum = BSoff_gnum(inode_gnum,inode_number,NULL); CHKERRN(0);
173
174 /* get permutation based on new global addresses */
175 /* also get a permuted version of the rows */
176 g_perm = BSglobal_perm(row_gnum); CHKERRN(0);
177 g_iperm = BSalloc_permutation(g_perm->length); CHKERRN(0);
178 BSperm2iperm(g_perm,g_iperm); CHKERRN(0);
179
180 /* *************************************************************** */
181 /* END SECTION: */
182 /* *************************************************************** */
183
184 /* *************************************************************** */
185 /* BEGIN SECTION: */
186 /* Propagate the permutation until the row level */
187 /* *************************************************************** */
188 /* get the transpose structure of the cliques */
189 col_cA = BStrans_perm_cl(cA,clique_gnum,procinfo); CHKERRN(0);
190 /* get the tranpose structure of the inodes */
191 col_iA = BStrans_perm_in(iA,inode_gnum,inode_row,inode_distr,
192 procinfo); CHKERRN(0);
193 /* set the pointers of the clique structure into the inode structure */
194 BSclique_2_inode(A,col_cA,col_iA,procinfo); CHKERRN(0);
195 /* set the pointers of the color structure into the clique structure */
196 color_2_cl = BScolor_2_clique(color_base,col_cA); CHKERRN(0);
197
198 /* *************************************************************** */
199 /* END SECTION: */
200 /* *************************************************************** */
201
202 /* *************************************************************** */
203 /* BEGIN SECTION: */
204 /* Permute the nonzeros at the row level and sort them */
205 /* Remember to unsort them */
206 /* *************************************************************** */
207
208 key_arr = BSperm_rows(A,row_gnum,inode_perm,inode_distr,procinfo,TRUE,
209 &max_row_len); CHKERRN(0);
210
211 /* *************************************************************** */
212 /* END SECTION: */
213 /* *************************************************************** */
214
215 /* *************************************************************** */
216 /* BEGIN SECTION: */
217 /* Put the row numbers into the transposed inode structure */
218 /* *************************************************************** */
219
220 perm_rows = BSrow_perm(A,g_iperm); CHKERRN(0);
221 ierr = BSrows_2_inode(A,row_gnum,g_perm,g_iperm,perm_rows,col_iA,
222 col_cA,key_arr,inode_number,inode_distr,procinfo); CHKERRN(0);
223 BSfree_key_arr(key_arr); CHKERRN(0);
224
225 /* *************************************************************** */
226 /* END SECTION: */
227 /* *************************************************************** */
228
229 /* *************************************************************** */
230 /* BEGIN SECTION: */
231 /* Put the numeric values into the transposed inode structure */
232 /* *************************************************************** */
233 BSnz_2_inode(A,perm_rows,col_iA,col_cA,procinfo); CHKERRN(0);
234 MY_FREEN(perm_rows);
235
236 /* *************************************************************** */
237 /* END SECTION: */
238 /* *************************************************************** */
239
240 /* *************************************************************** */
241 /* BEGIN SECTION: */
242 /* Unsort the rows to original condition */
243 /* *************************************************************** */
244
245 BSsort_rows(A,inode_perm,inode_distr,max_row_len); CHKERRN(0);
246
247 /* *************************************************************** */
248 /* END SECTION: */
249 /* *************************************************************** */
250
251 BSfree_numbering(inode_number); CHKERRN(0);
252 BSfree_numbering(inode_row); CHKERRN(0);
253 BSfree_numbering(clique_number); CHKERRN(0);
254 BSfree_distribution(clique_distr); CHKERRN(0);
255 BSfree_permutation(clique_perm); CHKERRN(0);
256 BSfree_numbering(color_number); CHKERRN(0);
257 BSfree_distribution(color_distr); CHKERRN(0);
258 BSfree_permutation(color_perm); CHKERRN(0);
259 if (!procinfo->single) {
260 BSfree_spmat(iA);
261 CHKERRN(0);
262 }
263 if (!procinfo->single) {
264 BSfree_spmat(cA);
265 CHKERRN(0);
266 }
267 BSfree_numbering(color_offset); CHKERRN(0);
268 BSfree_numbering(color_base); CHKERRN(0);
269 BSfree_distribution(new_clique_distr); CHKERRN(0);
270 BSfree_distribution(new_color_distr); CHKERRN(0);
271 BSfree_numbering(clique_gnum); CHKERRN(0);
272 BSfree_numbering(inode_gnum); CHKERRN(0);
273
274 /* set up return structure */
275 MY_MALLOCN(pA,(BSpar_mat *),sizeof(BSpar_mat),2);
276 pA->num_rows = A->num_rows;
277 pA->global_num_rows = A->global_num_rows;
278 pA->local_num_inodes = local_num_inodes;
279 pA->global_num_inodes = global_num_inodes;
280 pA->local_num_cliques = local_num_cliques;
281 pA->global_num_cliques = global_num_cliques;
282 pA->num_colors = num_colors;
283 pA->symmetric = A->symmetric;
284 pA->icc_storage = A->icc_storage;
285 pA->perm = g_perm;
286 pA->inv_perm = g_iperm;
287 pA->color2clique = color_2_cl;
288 pA->clique2inode = col_cA;
289 pA->inodes = col_iA;
290 pA->global_row_num = row_gnum;
291 pA->map = A->map;
292 /* allocate space for and get the diagonals */
293 MY_MALLOCN(pA->diag,(FLOAT *),pA->num_rows*sizeof(FLOAT),3);
294 BSget_diag(pA,pA->diag,procinfo); CHKERRN(0);
295 pA->save_diag = pA->diag;
296 pA->scale_diag = NULL;
297 if (procinfo->retain) {
298 MY_MALLOCN(pA->reperm,(BSreperm *),sizeof(BSreperm),4);
299 pA->reperm->inode_perm = inode_perm;
300 pA->reperm->inode_distr = inode_distr;
301 } else {
302 pA->reperm = NULL;
303 BSfree_distribution(inode_distr); CHKERRN(0);
304 BSfree_permutation(inode_perm); CHKERRN(0);
305 }
306
307 /* go over and patch up inode structure with original inode numbers */
308 BSorig_inode(pA,procinfo); CHKERRN(0);
309 pA->local_nnz = BScount_nz(pA,procinfo); CHKERRN(0);
310 pA->max_local_row_length = max_row_len;
311 MLOG_IT(PERMUTE);
312
313 return(pA);
314 }
315