1 #include "BSprivate.h"
2
3 /*+ BSfnd_inode - Find and number the identical nodes (i-nodes)
4
5 Input Parameters:
6 . A - The sparse matrix
7 . max_inode_size - the limit on the number of nodes in an i-node
8 . procinfo - the usual processor info
9
10 Returns:
11 a numbering of the nodes in which if two nodes have the same
12 number, then they are in the same i-node
13
14 Notes:
15 This only finds i-nodes local to a processor
16
17 +*/
BSfnd_inode(BSspmat * A,int max_inode_size,BSprocinfo * procinfo)18 BSnumbering *BSfnd_inode(BSspmat *A, int max_inode_size, BSprocinfo *procinfo)
19 {
20 int n;
21 BSsprow **rows;
22 BSnumbering *numbering;
23 int *used;
24 int i, j, k;
25 int cur_num, cur_size;
26 BSsprow *cur_row;
27 BSsprow *neighbor_row;
28 int neighbor;
29 int same;
30
31 n = A->num_rows;
32 rows = A->rows;
33 numbering = BSalloc_numbering(n); CHKERRN(0);
34
35 if (procinfo->single) {
36 for (i=0;i<n;i++) numbering->numbers[i] = i;
37 return(numbering);
38 }
39
40 MY_MALLOCN(used,(int *),sizeof(int)*n,1);
41 for (i=0;i<n;i++) used[i] = FALSE;
42
43 cur_num = 0;
44
45 /* go over every node in my partition */
46 for (i=0;i<n;i++) {
47 /* if node is already numbered then skip it */
48 if (used[i]) continue;
49
50 /* examine nodes that this node is connected to
51 to check if that node is identical, do not examine
52 nodes that are not in my partition
53 */
54 numbering->numbers[i] = cur_num;
55 used[i] = TRUE;
56 cur_row = rows[i];
57 cur_size = 1;
58 for (j=0;j<cur_row->length;j++) {
59 /* don't look at myself */
60 if (j == cur_row->diag_ind) continue;
61 /* if inode is too big, then stop checking */
62 if (cur_size >= max_inode_size) break;
63 /* if neighbor is in my partition */
64 (*A->map->fglobal2local)(1,&(cur_row->col[j]),
65 &neighbor,procinfo,A->map); CHKERRN(0);
66
67 if (neighbor >= 0) {
68 /* continue if the neighbor is already numbered */
69 if (used[neighbor]) continue;
70
71 neighbor_row = rows[neighbor];
72 /* if neighbor has same number of nz */
73 if (neighbor_row->length == cur_row->length) {
74 /* check if the rows are the same */
75 same = TRUE;
76 for (k=0;k<cur_row->length;k++) {
77 if (neighbor_row->col[k] != cur_row->col[k]) {
78 same = FALSE;
79 break;
80 }
81 }
82 if (same) {
83 numbering->numbers[neighbor] = cur_num;
84 used[neighbor] = TRUE;
85 cur_size++;
86 }
87 }
88 }
89 }
90 cur_num++;
91 }
92
93 MY_FREEN(used);
94
95 return(numbering);
96 }
97