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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 633 - (show annotations)
Thu Mar 23 05:37:00 2006 UTC (13 years, 5 months ago) by dhawcroft
File MIME type: text/plain
File size: 4868 byte(s)


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