/[escript]/trunk/finley/src/Mesh_optimizeNodeLabeling.c
ViewVC logotype

Diff of /trunk/finley/src/Mesh_optimizeNodeLabeling.c

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1170 by gross, Wed May 23 23:56:39 2007 UTC revision 1171 by gross, Fri May 25 06:55:05 2007 UTC
# Line 12  Line 12 
12    
13  /**************************************************************/  /**************************************************************/
14    
15  /*   Finley: Mesh : optimizes the labeling of nodes */  /*   Finley: Mesh : optimizes the labeling of DOFs */
16    
17  /**************************************************************/  /**************************************************************/
18    
# Line 27  Line 27 
27    
28  void Finley_Mesh_optimizeNodeLabeling(Finley_Mesh* mesh_p) {  void Finley_Mesh_optimizeNodeLabeling(Finley_Mesh* mesh_p) {
29    
30     index_t *DOF_permutation=NULL, i;  #if 0
31  /*  
32    
33       index_t i, n, initial_bandwidth, first_available_DOF, first_available_level, max_level_size, num_levels;
34       bool_t next_iteration,
35     Paso_SystemMatrixPattern* pattern_p=NULL;     Paso_SystemMatrixPattern* pattern_p=NULL;
36    
37       /* get access to the matrix pattern */
38     pattern_p=Finley_getPattern(mesh_p,FALSE,FALSE);     pattern_p=Finley_getPattern(mesh_p,FALSE,FALSE);
39       if (Finley_noError()) {
40     if no error {     if no error {
41         XXX=pattern_p. ;         n=pattern_p->n_ptr;
42         DOF_permutation=MEMALLOC(XXX, index_t);  old_to_new=MEMALLOC(n, index_t);
43         availbale=MEMALLOC(XXX, index_t);  availbale_DOF=MEMALLOC(n, bool_t);
44         #pragma omp for private(i)         #pragma omp for private(i)
45         for (i=0;i< ;++i) {         for (i=0;i<n;++i) {
46             DOF_permutation[i]=i;             old_to_new[i]=i;
47               availbale_DOF=TRUE;
48         }         }
49         first_available_node=0;         /* get initial bandwidth */
50         while (first_available_node <= XXX) {         initial_bandwidth=Finley_Mesh_getDegree(pattern_p,old_to_new);
51              // get an available node with minimum number of naighbours  printf("initial_bandwidth = %d\n",initial_bandwidth);
52              max_level_size=XXX;         /* make sure that all connection components are processed */
53              root=...         first_available_DOF=0;
54              // get the leveling string from root         first_available_level=0;
55              num_levels_tmp=1;         while (root=Finley_Mesh_FindMinDegreeNode(pattern_p,availbale_DOF, TRUE) >-1) {
56              num_nodes_in_level_tmp[0]=0;              // get an available DOF with minimum number of naighbours
57              levels_tmp[];              max_level_size=n;
58              // get maximum level size              next_iteration=TRUE;
59              max_level_size_tmp=MAX(num_nodes_in_level_tmp[i+1]-num_nodes_in_level_tmp[i], max_level_size_tmp);              num_levels=n;
60              // use new leveling if              #pragma omp parallel for private(i)
61              if (max_level_size_tmp<max_level_size) {              for (i=0;i<n;++i) {
62                  max_level_size=max_level_size_tmp;                  if (availbale_DOF[i])
63                  num_levels=num_levels_tmp;                      level_mask[i]=num_levels-1;
64                  num_nodes_in_level=num_nodes_in_level_tmp;                  } else {
65                        level_mask[i]=-1;
66                    }
67                }
68                /* run through graph diameter and creates levels until the maximum level size cannot be improved anymore */
69                while (root>-1) {
70                   /*   num_levels_new is the number of levels spanned from root.
71                        The DOFs ptr_DOFs_in_level_new[i] to ptr_DOFs_in_level_new[i+1]-1 in DOFs_in_level_new are
72                        maked for level i = 0,...,num_levels_new-1 */
73                   Finley_Mesh_MarkLevels(root,pattern_p,level_mask,num_levels-1,
74                                          &num_levels_new, ptr_DOFs_in_level_new, DOFs_in_level_new);
75                   /* now we calculate the maximum level size */
76                   max_level_size_new=0;
77                   for (i=0;i<num_levels_new;++i) {
78                       max_level_size_new=MAX(ptr_DOFs_in_level_new[i+1]-ptr_DOFs_in_level_new[i], max_level_size_new);
79                   }
80                   /* if there is a reduction in the maximum level size the we accept this leveling  */
81                   /* otherwise we give up                                                           */
82                   if (max_level_size_new < max_level_size) {
83                      max_level_size=max_level_size_new;
84                      num_levels=num_levels_new;
85                      for (i=0;i<num_levels_new+1;++i) {
86                          ptr_DOFs_in_level[i+first_available_level]=ptr_DOFs_in_level_new[i];
87                      }
88                      for (i=0;i<ptr_DOFs_in_level_new[num_levels_new];++i) {
89                          DOFs_in_level[i+first_available_DOF]=DOFs_in_level_new[i]+first_available_level;
90                      }
91                      root=Finley_Mesh_FindMinDegreeNodeFromList(pattern_p,
92                                                                 ptr_DOFs_in_level_new[num_levels_new]-ptr_DOFs_in_level_new[num_levels_new-1],
93                                                                 DOFs_in_level_new[ptr_DOFs_in_level_new[num_levels_new-1]]);
94                                                                
95                   } else {
96                       root=-1;
97                   }
98                }
99                #pragma omp parallel for private(i)
100                for (i=first_available_DOF;i<ptr_DOFs_in_level_new[num_levels];++i) {
101                     availbale_DOF[DOFs_in_level[i]]=FALSE;
102              }              }
103                            first_available_DOF+=ptr_DOFs_in_level_new[num_levels];
104                            first_available_level+=num_levels;
         
105         }         }
106     }         /* create new_to_old labeling (we don't do anything here) */
107  */         #pragma omp parallel for private(i)
108           for (i=0;i<n;++i) new_to_old[i]=DOFs_in_level[i];
109           /* invert the new_to_old labeling */
110           #pragma omp parallel for private(i)
111           for (i=0;i<n;++i) old_to_new[new_to_old[i]]=i;
112           /* now we can start to assign new labels to DOFs */
113           new_bandwidth=Finley_Mesh_getDegree(pattern_p,old_to_new);
114           if (new_bandwidth < initial_bandwidth) {
115    
116    
117           }
118    #endif
119    }
120    #if 0
121    dim_t Finley_Mesh_FindMinDegreeNode(Paso_SystemMatrixPattern* pattern_p,index_t* available,index_t indicator) {
122          index_t min_deg_local, min_deg_node_local, min_deg, min_deg_node;
123          register index_t deg;
124          min_deg=pattern_p->n_ptr;
125          min_deg_node=-1;
126          #pragma omp parallel private(min_deg_local, min_deg_node_local)
127          {
128            min_deg_local=pattern_p->n_ptr;
129            min_deg_node=-1;
130            #pragma omp for private(i,iptr,deg)
131            for (i=0,i<pattern->n_ptr,++i) {
132               if ( available[i] == indicator) {
133                  deg=0;
134                  for (iptr = pattern->ptr[i+1]; iptr<pattern->ptr[i+1]; ++iptr) {
135                       if (available[pattern->index[iptr]]==indicator) ++deg;
136                  }
137                  if (deg < min_deg_local) {
138                      min_deg_local=deg;
139                      min_deg_node_local=i;
140                  }
141               }
142             }
143             #pragma omp critical
144             {
145                if ((min_deg_local<min_deg) && (min_deg_local<min_deg)) {
146                    min_deg=min_deg_local;
147                    min_deg_node=min_deg_node_local;
148                }
149             }
150          }
151          return min_deg_node;
152    }
153    
154    index_t Finley_Mesh_getDegree(Paso_SystemMatrixPattern* pattern_p, index_t *label) {
155          index_t bandwidth, i, iptr, local_bandwidth;
156          bandwidth = 0;
157          #pragma omp parallel private(local_bandwidth)
158          {
159            local_bandwidth=0;
160            #pragma omp for private(i,i_ptr)
161            for (i=0,i<pattern->n_ptr,++i) {
162               for (iptr=pattern->ptr[i],iptr<pattern->ptr[i+1],++iptr) {
163                   local_bandwidth = MAX(local_bandwidth,ABS(label[i] - label(pattern->index[iptr])));
164               }
165             }
166             #pragma omp critical
167             {
168                bandwidth=MAX(bandwidth,local_bandwidth);
169             }
170          }
171          return bandwidth;
172    }
173    
174    void Finley_Mesh_MarkLevels(index_t root,
175                                Paso_SystemMatrixPattern* pattern_p,
176                                dim_t *num_levels, dim_t *ptr_DOFs_in_level, index_t *DOFs_in_level)
177    
178    {
179      DOFs_in_level[0]=root;
180      available[root]=FALSE;
181      ptr_DOFs_in_level[0]=0;
182      level_count=1;
183      nn=1;
184      while (ptr_DOFs_in_level[level_count-1] < nn ) {
185          ptr_DOFs_in_level[level_count] = nn;
186          ++level_count;
187          for (i = ptr_DOFs_in_level[level_count-1]; i < ptr_DOFs_in_level[level_count]; ++i) {
188               dof=DOFs_in_level[i]
189               for (iptr=pattern->ptr[dof],iptr<pattern->ptr[dof+1],++iptr) {
190                  itmp=pattern->index[iptr];
191                  if (! available[itmp]) {
192                       available[itmp]=FALSE;
193                       DOFs_in_level[nn]=itmp;
194                       ++nn;
195                  }
196    
197    
198    
199          }
200      }
201      *num_levels=level_count;
202      ptr_DOFs_in_level[level_count]=  ;
203  }  }
204    #endif
Legend:
Removed from v.1170  
changed lines
  Added in v.1171
  ViewVC Help
Powered by ViewVC 1.1.26