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

Contents of /trunk/paso/src/Pattern_mis.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3094 - (show annotations)
Fri Aug 13 08:38:06 2010 UTC (9 years, 2 months ago) by gross
File MIME type: text/plain
File size: 5573 byte(s)
The MPI and sequational GAUSS_SEIDEL have been merged.
The couring and main diagonal pointer is now manged by the patternm which means that they are calculated once only even if the preconditioner is deleted.



1
2 /*******************************************************
3 *
4 * Copyright (c) 2003-2010 by University of Queensland
5 * Earth Systems Science Computational Center (ESSCC)
6 * http://www.uq.edu.au/esscc
7 *
8 * Primary Business: Queensland, Australia
9 * Licensed under the Open Software License version 3.0
10 * http://www.opensource.org/licenses/osl-3.0.php
11 *
12 *******************************************************/
13
14
15 /**********************************************************************/
16
17 /* Paso: Pattern: Paso_Pattern_mis
18
19 searches for a maximal independent set MIS in the matrix pattern
20 vertices in the maximal independent set are marked in mis_marker
21 nodes to be considered are marked by -1 on the input in mis_marker
22
23 */
24 /**********************************************************************/
25
26 /* Copyrights by ACcESS Australia 2003,2004,2005 */
27 /* Author: Lutz Gross, l.gross@uq.edu.au */
28
29 /**************************************************************/
30
31 #include "mpi_C.h"
32 #include "Paso.h"
33 #include "PasoUtil.h"
34 #include "Pattern.h"
35
36
37 /* used to generate pseudo random numbers: */
38
39 static double Paso_Pattern_mis_seed=.4142135623730951;
40
41
42 /***************************************************************/
43
44 #define IS_AVAILABLE -1
45 #define IS_IN_MIS_NOW -2
46 #define IS_IN_MIS -3
47 #define IS_CONNECTED_TO_MIS -4
48
49 void Paso_Pattern_mis(Paso_Pattern* pattern_p, index_t* mis_marker) {
50
51 index_t index_offset=(pattern_p->type & PATTERN_FORMAT_OFFSET1 ? 1:0);
52 dim_t i;
53 double *value;
54 index_t naib,iptr;
55 bool_t flag;
56 dim_t n=pattern_p->numOutput;
57 if (pattern_p->type & PATTERN_FORMAT_SYM) {
58 Paso_setError(TYPE_ERROR,"Paso_Pattern_mis: symmetric matrix pattern is not supported yet");
59 return;
60 }
61 if (pattern_p->numOutput != pattern_p->numInput) {
62 Paso_setError(VALUE_ERROR,"Paso_Pattern_mis: pattern must be square.");
63 return;
64 }
65 value=TMPMEMALLOC(n,double);
66 if (!Paso_checkPtr(value)) {
67
68
69 /* is there any vertex available ?*/
70 while (Paso_Util_isAny(n,mis_marker,IS_AVAILABLE)) {
71 /* step 1: assign a random number in [0,1] to each vertex */
72 /* step 2: is the vertex is available, check if its value is the smaller than all values of its naigbours
73 if the answer is yes, the vertex is put into the independend set and all
74 its naighbours are removed from the graph by setting it mis_marker to FALSE */
75
76 /* step 2: is the vertex is available, check if its value is the smaller than all values of its naigbours */
77
78 /* assign random number in [0,1] to each vertex */
79 #pragma omp parallel for private(i) schedule(static)
80 for (i=0;i<n;++i) {
81 if (mis_marker[i]==IS_AVAILABLE) {
82 value[i]=fmod(Paso_Pattern_mis_seed*(i+1),1.);
83 } else {
84 value[i]=2.;
85 }
86 }
87 /* update the seed */
88 /* Paso_Pattern_mis_seed=fmod(sqrt(Paso_Pattern_mis_seed*(n+1)),1.); */
89 /* detect independent vertices as those vertices that have a value less than all values of its naigbours */
90 #pragma omp parallel for private(naib,i,iptr,flag) schedule(static)
91 for (i=0;i<n;++i) {
92 if (mis_marker[i]==IS_AVAILABLE) {
93 flag=IS_IN_MIS_NOW;
94 for (iptr=pattern_p->ptr[i]-index_offset;iptr<pattern_p->ptr[i+1]-index_offset; ++iptr) {
95 naib=pattern_p->index[iptr]-index_offset;
96 if (naib!=i && value[naib]<=value[i]) {
97 flag=IS_AVAILABLE;
98 break;
99 }
100 }
101 mis_marker[i]=flag;
102 }
103 }
104 /* detect independent vertices as those vertices that have a value less than all values of its naigbours */
105 #pragma omp parallel for private(naib,i,iptr) schedule(static)
106 for (i=0;i<n;i++) {
107 if (mis_marker[i]==IS_IN_MIS_NOW) {
108 for (iptr=pattern_p->ptr[i]-index_offset;iptr<pattern_p->ptr[i+1]-index_offset; ++iptr) {
109 naib=pattern_p->index[iptr]-index_offset;
110 if (naib!=i) mis_marker[naib]=IS_CONNECTED_TO_MIS;
111 }
112 mis_marker[i]=IS_IN_MIS;
113 }
114 }
115 }
116 /* swap to TRUE/FALSE in mis_marker */
117 #pragma omp parallel for private(i) schedule(static)
118 for (i=0;i<n;i++) mis_marker[i]=(mis_marker[i]==IS_IN_MIS);
119 }
120 TMPMEMFREE(value);
121 }
122 #undef IS_AVAILABLE
123 #undef IS_IN_MIS_NOW
124 #undef IS_IN_MIS
125 #undef IS_CONNECTED_TO_MIS
126
127 void Paso_Pattern_color(Paso_Pattern* pattern, index_t* num_colors, index_t* colorOf) {
128 index_t out=0, *mis_marker=NULL,i;
129 dim_t n=pattern->numOutput;
130 mis_marker=TMPMEMALLOC(n,index_t);
131 if ( !Paso_checkPtr(mis_marker) ) {
132 /* get coloring */
133 #pragma omp parallel for private(i) schedule(static)
134 for (i = 0; i < n; ++i) {
135 colorOf[i]=-1;
136 mis_marker[i]=-1;
137 }
138
139 while (Paso_Util_isAny(n,colorOf,-1) && Paso_noError()) {
140 /*#pragma omp parallel for private(i) schedule(static)
141 for (i = 0; i < n; ++i) mis_marker[i]=colorOf[i];*/
142 Paso_Pattern_mis(pattern,mis_marker);
143
144 #pragma omp parallel for private(i) schedule(static)
145 for (i = 0; i < n; ++i) {
146 if (mis_marker[i]) colorOf[i]=out;
147 mis_marker[i]=colorOf[i];
148 }
149 ++out;
150 }
151 TMPMEMFREE(mis_marker);
152 *num_colors=out;
153 }
154 }

  ViewVC Help
Powered by ViewVC 1.1.26