PaStiX Handbook  6.3.2
graph_compute_kway.c
Go to the documentation of this file.
1 /**
2  *
3  * @file graph_compute_kway.c
4  *
5  * PaStiX routines to compute kway on a given supernode
6  *
7  * @copyright 2004-2023 Bordeaux INP, CNRS (LaBRI UMR 5800), Inria,
9  *
10  * @version 6.3.2
11  * @author Gregoire Pichon
12  * @author Mathieu Faverge
13  * @author Tony Delarue
14  * @date 2023-07-21
15  *
16  **/
17 #include "common.h"
18 #if !defined(PASTIX_ORDERING_SCOTCH)
19 #error "This file should be compiled inly if SCOTCH is enabled and found"
20 #endif /* defined(PASTIX_ORDERING_PTSCOTCH) */
21 #include <spm.h>
22 #include "graph/graph.h"
23 #include "pastix/order.h"
24 #include <scotch.h>
25
26 /**
27  *******************************************************************************
28  *
29  * @ingroup pastix_graph
30  *
31  * @brief Compute the K-way partition of a given set of unknowns
32  *
33  * Take a graph with its own associated ordering, and generates a k-way
34  * partition of the graph.
35  *
36  *******************************************************************************
37  *
38  * @param[in] graph
39  * The pointer to the graph structure on wich to apply the K-way
40  * partitioning on the subcomponent comp_id.
41  *
42  * @param[inout] order
43  * The order structure associated to the given graph.
44  * On entry, the structure is initialized through previous operation on
45  * the graph, and on exit vertices are reordered by components in the
46  * K-way partitioning.
47  *
48  * @param[inout] peritab
49  * Array of size n.
50  * Pointer to the peritab array of the global graph in which the
51  * subproblem belongs to. This array is updated according to the
52  * eprmutation performed for the K-way partitioning.
53  *
54  * @param[inout] comp_nbr
55  * On entry the number of components in the graph.
56  * On exit, the new number of components after K-way partitioning.
57  *
58  * @param[inout] comp_sze
59  * The size of each components in the graph.
60  * On entry, only the first comp_nbr sizes are initialized, others are 0.
61  * On exit, the array is extended to store the size of the new
62  * components generated by the k-way partitionning.
63  *
64  * @param[inout] comp_vtx
65  * Array of size n that hold the index of the component for each vertex
66  * of the graph.
67  *
68  * @param[in] comp_id
69  * The index of the component that must be split by K-way paritioning.
70  *
71  * @param[in] nbpart
72  * The number of part wanted in the k-way partitioning.
73  *
74  *******************************************************************************
75  *
76  * @retval PASTIX_SUCCESS on success,
77  * @retval PASTIX_ERR_UNKNOWN if something went wrong with Scotch.
78  *
79  *******************************************************************************/
80 int graphComputeKway( const pastix_graph_t *graph,
81  pastix_order_t *order,
82  pastix_int_t *peritab,
83  pastix_int_t *comp_nbr,
84  pastix_int_t *comp_sze,
85  pastix_int_t *comp_vtx,
86  pastix_int_t comp_id,
87  pastix_int_t nbpart )
88 {
89  SCOTCH_Graph comp_sgraph;
90  SCOTCH_Strat sstrat;
91  pastix_graph_t comp_graph;
92  pastix_int_t i, n, comp_n, fnode, lnode;
93  pastix_int_t *perm = order->permtab;
94  pastix_int_t *invp = order->peritab;
95  pastix_int_t *parttab;
96
97  n = graph->n;
98
99  fnode = 0;
100  for (i=0; i<comp_id; i++) {
101  fnode += comp_sze[i];
102  }
103  lnode = fnode + comp_sze[comp_id];
104  assert( comp_sze[comp_id] != 0 );
105  assert( lnode <= n );
106
107  comp_n = lnode - fnode;
108
109  /* Isolate unknowns of the component */
110  if ( comp_n == n ) {
111  memcpy( &comp_graph, graph, sizeof(pastix_graph_t) );
112  }
113  else {
114  /* First, let's make sure everything is sorted by component to extract it */
115  {
116  void *sortptr[3];
117  sortptr[0] = comp_vtx;
118  sortptr[1] = invp;
119  sortptr[2] = peritab;
120
121  qsort3IntAsc( sortptr, n );
122
123  /* Update the perm array */
124  for(i=0; i<n; i++) {
125  perm[invp[i]] = i;
126  }
127
128  /* pastixOrderCheck( order ); */
129  }
130  memset( &comp_graph, 0, sizeof(pastix_graph_t) );
131  graphIsolateRange( graph, order, &comp_graph,
132  fnode, lnode, 0 );
133  }
134  assert( comp_graph.n == comp_n );
135
136  /* Build Scotch graph */
137  if ( ! SCOTCH_graphInit( &comp_sgraph ) ) {
138  SCOTCH_graphBuild( &comp_sgraph,
139  order->baseval,
140  comp_n,
141  comp_graph.colptr,
142  NULL,
143  NULL,
144  NULL,
145  comp_graph.colptr[ comp_n ] - comp_graph.colptr[ 0 ],
146  comp_graph.rowptr,
147  NULL);
148  }
149  else {
150  fprintf(stderr,"Failed to build graph\n");
151  }
152
153 #if !defined(NDEBUG)
154  if ( SCOTCH_graphCheck( &comp_sgraph ) ) {
155  pastix_print_error( "error in graph graphCheck()...\n" );
157  }
158 #endif
159
160  if ( SCOTCH_stratInit( &sstrat ) != 0 ) {
161  pastix_print_error( "Failed to initialize partitioning strategy\n" );
162  return PASTIX_ERR_UNKNOWN;
163  }
164
165  parttab = malloc( comp_n * sizeof(pastix_int_t) );
166  memset( parttab, 0, comp_n * sizeof(pastix_int_t) );
167
168  SCOTCH_graphPart( &comp_sgraph, nbpart,
169  &sstrat, parttab );
170
171  SCOTCH_graphExit( &comp_sgraph );
172  SCOTCH_stratExit( &sstrat );
173
174  /* Update the comp_vtx, and comp_size */
175  {
176  pastix_int_t *vtx;
177  pastix_int_t newid;
178
179  for(i=0; i<nbpart; i++) {
180  comp_sze[ *comp_nbr + i ] = 0;
181  }
182
183  for(i=0; i<comp_n; i++) {
184  vtx = comp_vtx + fnode + i;
185  assert( *vtx == comp_id );
186  newid = *comp_nbr + parttab[i];
187  comp_sze[newid]++;
188  *vtx = newid;
189  }
190  comp_sze[comp_id] = 0;
191  *comp_nbr += nbpart;
192  }
193
194  if ( comp_n != n ) {
195  graphExit( &comp_graph );
196  }
197
198  /* /\* Sort the unknown of the component *\/ */
199  /* { */
200  /* void *sortptr[3]; */
201  /* sortptr[0] = comp_vtx + fnode; */
202  /* sortptr[1] = invp + fnode; */
203  /* sortptr[2] = peritab + fnode; */
204
205  /* qsort3IntAsc( sortptr, comp_n ); */
206
207  /* /\* If necessary, move the partition to the end to keep the right order *\/ */
208  /* if ( (graph->n - lnode) != 0 ) { */
209  /* move_to_end( comp_n, graph->n - lnode, */
210  /* comp_vtx + fnode, parttab ); */
211  /* move_to_end( comp_n, graph->n - lnode, */
212  /* invp + fnode, parttab ); */
213  /* move_to_end( comp_n, graph->n - lnode, */
214  /* peritab + fnode, parttab ); */
215
216  /* /\* Update the perm array *\/ */
217  /* for(i=0; i<graph->n; i++) { */
218  /* perm[invp[i]] = i; */
219  /* } */
220  /* } */
221  /* else { */
222  /* /\* Update the perm array *\/ */
223  /* for(i=fnode; i<lnode; i++) { */
224  /* perm[invp[i]] = i; */
225  /* } */
226  /* } */
227  /* } */
228
229  free( parttab );
230  return PASTIX_SUCCESS;
231 }
BEGIN_C_DECLS typedef int pastix_int_t
Definition: datatypes.h:51
@ PASTIX_ERR_UNKNOWN
Definition: api.h:368
@ PASTIX_SUCCESS
Definition: api.h:367
Definition: api.h:374
void graphExit(pastix_graph_t *graph)
Free the content of the graph structure.
Definition: graph.c:73
int graphIsolateRange(const pastix_graph_t *graphIn, const pastix_order_t *order, pastix_graph_t *graphOut, pastix_int_t fnode, pastix_int_t lnode, pastix_int_t distance)
Isolate the subgraph associated to a range of unknowns in the permuted graph.
int graphComputeKway(const pastix_graph_t *graph, pastix_order_t *order, pastix_int_t *peritab, pastix_int_t *comp_nbr, pastix_int_t *comp_sze, pastix_int_t *comp_vtx, pastix_int_t comp_id, pastix_int_t nbpart)
Compute the K-way partition of a given set of unknowns.
pastix_int_t baseval
Definition: order.h:48
pastix_int_t * permtab
Definition: order.h:51
pastix_int_t * peritab
Definition: order.h:52
Order structure.
Definition: order.h:47