/[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 150 - (hide annotations)
Thu Sep 15 03:44:45 2005 UTC (14 years, 2 months ago) by jgs
Original Path: trunk/esys2/paso/src/SystemMatrixPattern_mis.c
File MIME type: text/plain
File size: 4325 byte(s)
Merge of development branch dev-02 back to main trunk on 2005-09-15

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    
10     */
11     /**********************************************************************/
12    
13     /* Copyrights by ACcESS Australia 2003,2004,2005 */
14     /* Author: gross@access.edu.au */
15    
16     /**************************************************************/
17    
18     #include "Paso.h"
19     #include "Util.h"
20     #include "SystemMatrixPattern.h"
21    
22    
23     /* used to generate pseudo random numbers: */
24    
25     static double Paso_SystemMatrixPattern_mis_seed=.4142135623730951;
26    
27    
28     /***************************************************************/
29    
30     #define IS_AVAILABLE -1
31     #define IS_IN_MIS_NOW -2
32     #define IS_IN_MIS -3
33     #define IS_CONNECTED_TO_MIS -4
34    
35     void Paso_SystemMatrixPattern_mis(Paso_SystemMatrixPattern* pattern_p, index_t* mis_marker) {
36    
37     dim_t i;
38     index_t naib,iptr;
39     bool_t flag;
40     dim_t n=pattern_p->n_ptr;
41     double *value=TMPMEMALLOC(n,double);
42     if (!Paso_checkPtr(value)) {
43     #pragma omp parallel for private(i) schedule(static)
44     for (i=0;i<n;++i) mis_marker[i]=IS_AVAILABLE;
45    
46     /* is there any vertex available ?*/
47     while (Paso_Util_isAny(n,mis_marker,IS_AVAILABLE)) {
48     /* step 1: assign a random number in [0,1] to each vertex */
49     /* step 2: is the vertex is available, check if its value is the smaller than all values of its naigbours
50     if the answer is yes, the vertex is put into the independend set and all
51     its naighbours are removed from the graph by setting it mis_marker to FALSE */
52    
53     /* step 2: is the vertex is available, check if its value is the smaller than all values of its naigbours */
54    
55     /* assign random number in [0,1] to each vertex */
56     #pragma omp parallel for private(i) schedule(static)
57     for (i=0;i<n;++i) {
58     if (mis_marker[i]==IS_AVAILABLE) {
59     value[i]=fmod(Paso_SystemMatrixPattern_mis_seed*(i+1),1.);
60     } else {
61     value[i]=2.;
62     }
63     }
64     /* update the seed */
65     Paso_SystemMatrixPattern_mis_seed=fmod(sqrt(Paso_SystemMatrixPattern_mis_seed*(n+1)),1.);
66     /* detect independent vertices as those vertices that have a value less than all values of its naigbours */
67     #pragma omp parallel for private(naib,i,iptr,flag) schedule(static)
68     for (i=0;i<n;++i) {
69     if (mis_marker[i]==IS_AVAILABLE) {
70     flag=IS_IN_MIS_NOW;
71     for (iptr=pattern_p->ptr[i];iptr<pattern_p->ptr[i+1]; ++iptr) {
72     naib=pattern_p->index[iptr];
73     if (naib!=i && value[naib]<=value[i]) {
74     flag=IS_AVAILABLE;
75     break;
76     }
77     }
78     mis_marker[i]=flag;
79     }
80     }
81     /* detect independent vertices as those vertices that have a value less than all values of its naigbours */
82     #pragma omp parallel for private(naib,i,iptr) schedule(static)
83     for (i=0;i<n;i++) {
84     if (mis_marker[i]==IS_IN_MIS_NOW) {
85     for (iptr=pattern_p->ptr[i];iptr<pattern_p->ptr[i+1]; ++iptr) {
86     naib=pattern_p->index[iptr];
87     if (naib!=i) mis_marker[naib]=IS_CONNECTED_TO_MIS;
88     }
89     mis_marker[i]=IS_IN_MIS;
90     }
91     }
92     }
93     /* swap to TRUE/FALSE in mis_marker */
94     #pragma omp parallel for private(i) schedule(static)
95     for (i=0;i<n;i++) mis_marker[i]=(mis_marker[i]==IS_IN_MIS);
96     }
97     TMPMEMFREE(value);
98     }
99     #undef IS_AVAILABLE
100     #undef IS_IN_MIS_NOW
101     #undef IS_IN_MIS
102     #undef IS_CONNECTED_TO_MIS
103    
104     /*
105     * $Log$
106     * Revision 1.2 2005/09/15 03:44:39 jgs
107     * Merge of development branch dev-02 back to main trunk on 2005-09-15
108     *
109     * Revision 1.1.2.1 2005/09/05 06:29:47 gross
110     * These files have been extracted from finley to define a stand alone libray for iterative
111     * linear solvers on the ALTIX. main entry through Paso_solve. this version compiles but
112     * has not been tested yet.
113     *
114     *
115     */

Properties

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

  ViewVC Help
Powered by ViewVC 1.1.26