/[escript]/trunk/paso/src/SystemMatrixPattern_mis.c
ViewVC logotype

Annotation of /trunk/paso/src/SystemMatrixPattern_mis.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 431 - (hide annotations)
Fri Jan 13 05:07:10 2006 UTC (14 years, 7 months ago) by gross
File MIME type: text/plain
File size: 4219 byte(s)
new implementation of ILU0
1 jgs 150 /* $Id$ */
2    
3     /**********************************************************************/
4    
5     /* Paso: SystemMatrixPattern: Paso_SystemMatrixPattern_mis
6    
7     searches for a maximal independent set MIS in the matrix pattern
8     vertices in the maximal independent set are marked in mis_marker
9 gross 431 nodes to be considered are marked by -1 on the input in mis_marker
10 jgs 150
11     */
12     /**********************************************************************/
13    
14     /* Copyrights by ACcESS Australia 2003,2004,2005 */
15     /* Author: gross@access.edu.au */
16    
17     /**************************************************************/
18    
19     #include "Paso.h"
20     #include "Util.h"
21     #include "SystemMatrixPattern.h"
22    
23    
24     /* used to generate pseudo random numbers: */
25    
26     static double Paso_SystemMatrixPattern_mis_seed=.4142135623730951;
27    
28    
29     /***************************************************************/
30    
31     #define IS_AVAILABLE -1
32     #define IS_IN_MIS_NOW -2
33     #define IS_IN_MIS -3
34     #define IS_CONNECTED_TO_MIS -4
35    
36     void Paso_SystemMatrixPattern_mis(Paso_SystemMatrixPattern* pattern_p, index_t* mis_marker) {
37    
38 gross 415 index_t index_offset=(pattern_p->type & PATTERN_FORMAT_OFFSET1 ? 1:0);
39 jgs 150 dim_t i;
40     index_t naib,iptr;
41     bool_t flag;
42     dim_t n=pattern_p->n_ptr;
43 gross 415 if (pattern_p->type & PATTERN_FORMAT_SYM) {
44     Paso_setError(TYPE_ERROR,"Paso_SystemMatrixPattern_mis: symmetric matrix pattern is not supported yet");
45     return;
46     }
47 jgs 150 double *value=TMPMEMALLOC(n,double);
48     if (!Paso_checkPtr(value)) {
49 gross 431
50 jgs 150
51     /* is there any vertex available ?*/
52     while (Paso_Util_isAny(n,mis_marker,IS_AVAILABLE)) {
53     /* step 1: assign a random number in [0,1] to each vertex */
54     /* step 2: is the vertex is available, check if its value is the smaller than all values of its naigbours
55     if the answer is yes, the vertex is put into the independend set and all
56     its naighbours are removed from the graph by setting it mis_marker to FALSE */
57    
58     /* step 2: is the vertex is available, check if its value is the smaller than all values of its naigbours */
59    
60     /* assign random number in [0,1] to each vertex */
61     #pragma omp parallel for private(i) schedule(static)
62     for (i=0;i<n;++i) {
63     if (mis_marker[i]==IS_AVAILABLE) {
64     value[i]=fmod(Paso_SystemMatrixPattern_mis_seed*(i+1),1.);
65     } else {
66     value[i]=2.;
67     }
68     }
69     /* update the seed */
70 jgs 154 /* Paso_SystemMatrixPattern_mis_seed=fmod(sqrt(Paso_SystemMatrixPattern_mis_seed*(n+1)),1.); */
71 jgs 150 /* detect independent vertices as those vertices that have a value less than all values of its naigbours */
72     #pragma omp parallel for private(naib,i,iptr,flag) schedule(static)
73     for (i=0;i<n;++i) {
74     if (mis_marker[i]==IS_AVAILABLE) {
75     flag=IS_IN_MIS_NOW;
76 gross 415 for (iptr=pattern_p->ptr[i]-index_offset;iptr<pattern_p->ptr[i+1]-index_offset; ++iptr) {
77     naib=pattern_p->index[iptr]-index_offset;
78 jgs 150 if (naib!=i && value[naib]<=value[i]) {
79     flag=IS_AVAILABLE;
80     break;
81     }
82     }
83     mis_marker[i]=flag;
84     }
85     }
86     /* detect independent vertices as those vertices that have a value less than all values of its naigbours */
87     #pragma omp parallel for private(naib,i,iptr) schedule(static)
88     for (i=0;i<n;i++) {
89     if (mis_marker[i]==IS_IN_MIS_NOW) {
90 gross 415 for (iptr=pattern_p->ptr[i]-index_offset;iptr<pattern_p->ptr[i+1]-index_offset; ++iptr) {
91     naib=pattern_p->index[iptr]-index_offset;
92 jgs 150 if (naib!=i) mis_marker[naib]=IS_CONNECTED_TO_MIS;
93     }
94     mis_marker[i]=IS_IN_MIS;
95     }
96     }
97     }
98     /* swap to TRUE/FALSE in mis_marker */
99     #pragma omp parallel for private(i) schedule(static)
100     for (i=0;i<n;i++) mis_marker[i]=(mis_marker[i]==IS_IN_MIS);
101     }
102     TMPMEMFREE(value);
103     }
104     #undef IS_AVAILABLE
105     #undef IS_IN_MIS_NOW
106     #undef IS_IN_MIS
107     #undef IS_CONNECTED_TO_MIS

Properties

Name Value
svn:eol-style native
svn:keywords Author Date Id Revision

  ViewVC Help
Powered by ViewVC 1.1.26