/[escript]/trunk/esys2/finley/src/finleyC/Solvers/Solver_mis.c
ViewVC logotype

Contents of /trunk/esys2/finley/src/finleyC/Solvers/Solver_mis.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 113 - (show annotations)
Mon Feb 28 07:06:33 2005 UTC (14 years, 1 month ago) by jgs
File MIME type: text/plain
File size: 3904 byte(s)
*** empty log message ***

1 /* $Id$ */
2
3 /**********************************************************************/
4
5 /* Finley: Solver: Finley_Solver_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 "Finley.h"
19 #include "System.h"
20 #include "Util.h"
21 #include "Solver.h"
22
23
24 /* used to generate pseudo random numbers: */
25
26 static double Finley_Solver_coloring_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 Finley_Solver_mis(Finley_SystemMatrixPattern* pattern_p, maybelong* mis_marker) {
37
38 maybelong i,naib,iptr;
39 int flag;
40 maybelong n=pattern_p->n_ptr;
41 double *value=TMPMEMALLOC(n,double);
42 if (!Finley_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 (Finley_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 #pragma omp parallel
56 {
57 /* assign random number in [0,1] to each vertex */
58 #pragma omp for private(i) schedule(static)
59 for (i=0;i<n;i++) value[i]=fmod(Finley_Solver_coloring_seed*(i+1),1.);
60 /* update the seed */
61 #pragma omp master
62 Finley_Solver_coloring_seed=fmod(sqrt(Finley_Solver_coloring_seed*(n+1)),1.);
63 /* detect independent vertices as those vertices that have a value less than all values of its naigbours */
64 #pragma omp for private(naib,i,iptr,flag) schedule(static)
65 for (i=0;i<n;i++) {
66 if (mis_marker[i]==IS_AVAILABLE) {
67 flag=IS_IN_MIS_NOW;
68 for (iptr=pattern_p->ptr[i];iptr<pattern_p->ptr[i+1]; ++iptr) {
69 naib=pattern_p->index[iptr];
70 if (naib!=i && value[naib]<=value[i]) {
71 flag=IS_AVAILABLE;
72 break;
73 }
74 }
75 mis_marker[i]=flag;
76 }
77 }
78 /* detect independent vertices as those vertices that have a value less than all values of its naigbours */
79 #pragma omp for private(naib,i,iptr) schedule(static)
80 for (i=0;i<n;i++)
81 if (mis_marker[i]==IS_IN_MIS_NOW) {
82 for (iptr=pattern_p->ptr[i];iptr<pattern_p->ptr[i+1]; ++iptr) mis_marker[pattern_p->index[iptr]]=IS_CONNECTED_TO_MIS;
83 mis_marker[i]=IS_IN_MIS;
84 }
85 }
86 }
87 /* swap to TRUE/FALSE in mis_marker */
88 #pragma omp parallel for private(i) schedule(static)
89 for (i=0;i<n;i++) mis_marker[i]=(mis_marker[i]==IS_IN_MIS);
90 }
91 TMPMEMFREE(value);
92 }
93 #undef IS_AVAILABLE
94 #undef IS_IN_MIS_NOW
95 #undef IS_IN_MIS
96 #undef IS_CONNECTED_TO_MIS
97
98 /*
99 * $Log$
100 * Revision 1.2 2005/02/28 07:06:33 jgs
101 * *** empty log message ***
102 *
103 * Revision 1.1.2.1 2005/02/18 03:35:17 gross
104 * another function added in prepartion for the reimplementation of ILU
105 *
106 *
107 */

Properties

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

  ViewVC Help
Powered by ViewVC 1.1.26