PaStiX Handbook  6.4.0
symbol_reordering.c
Go to the documentation of this file.
1 /**
2  *
3  * @file symbol_reordering.c
4  *
5  * PaStiX symbol structure reordering routines
6  *
7  * @copyright 2015-2024 Bordeaux INP, CNRS (LaBRI UMR 5800), Inria,
9  *
10  * @version 6.4.0
11  * @author Gregoire Pichon
12  * @author Mathieu Faverge
13  * @author Pierre Ramet
14  * @author Vincent Bridonneau
15  * @date 2024-07-05
16  *
17  **/
18 #include "common.h"
19 #include "pastix/order.h"
20 #include "symbol/symbol.h"
21 #include "symbol_reorder.h"
22
23 /**
24  *******************************************************************************
25  *
26  * @ingroup symbol_dev_reordering
27  *
28  * @brief Compute the level of supernode cblknum, with Scotch treetab.
29  *
30  *******************************************************************************
31  *
32  * @param[in] treetab
33  * The pointer to the elimination tree from Scotch.
34  *
35  * @param[in] levels
36  * The supernode array which contains levels. Used to check if
37  * the level was already computed.
38  *
39  * @param[in] cblknum
40  * The supernode for which the level is computed.
41  *
42  *******************************************************************************
43  *
44  * @return the level of cblknum.
45  *
46  *******************************************************************************/
47 static inline pastix_int_t
49  const pastix_int_t *levels,
50  pastix_int_t cblknum )
51 {
52  /* If cblknum level has already been computed */
53  if ( levels[cblknum] != 0 ) {
54  return levels[cblknum];
55  }
56  else {
57  pastix_int_t father = treetab[cblknum];
58
59  if ( father == -1 ) {
60  return 1;
61  }
62  else {
63  return compute_cblklevel( treetab, levels, father ) + 1;
64  }
65  }
66 }
67
68 /**
69  *******************************************************************************
70  *
71  * @ingroup symbol_dev_reordering
72  *
73  * @brief Compute the distance between two rows of a same supernode.
74  *
75  *******************************************************************************
76  *
77  * @param[in] vectors
78  * The pointer to the sets of contributing supernodes for
79  * each row of the current supernode.
80  *
81  * @param[in] vectors_size
82  * The pointer to the sizes of each set of contributing
83  * supernode, to stop the computation when a row have been totally
84  * covered.
85  *
86  * @param[in] xi
87  * The index of the first row.
88  *
89  * @param[in] xj
90  * The index of the second row.
91  *
92  * @param[in] stop
93  * The stop criterion to disregard rows that are far away.
94  *
95  *******************************************************************************
96  *
97  * @return The distance between rows xi and xj.
98  *
99  *******************************************************************************/
100 static inline pastix_int_t
102  pastix_int_t *vectors_size,
103  pastix_int_t xi,
104  pastix_int_t xj,
105  pastix_int_t stop )
106 {
107  /* For the fictive vertex */
108  if ( xi == -1 ) {
109  return vectors_size[xj];
110  }
111  if ( xj == -1 ) {
112  return vectors_size[xi];
113  }
114
115  pastix_int_t sum = 0;
116  pastix_int_t *set1 = vectors[xi];
117  pastix_int_t *set2 = vectors[xj];
118  pastix_int_t *end1 = vectors[xi] + vectors_size[xi];
119  pastix_int_t *end2 = vectors[xj] + vectors_size[xj];
120
121  if ( vectors_size[xi] - vectors_size[xj] >= stop ) {
122  return stop;
123  }
124  if ( vectors_size[xj] - vectors_size[xi] >= stop ) {
125  return stop;
126  }
127
128  while( ( set1 < end1 ) && ( set2 < end2 ) ) {
129  if( *set1 == *set2 ) {
130  set1++;
131  set2++;
132  }
133  else if( *set1 < *set2 ) {
134  while ( ( set1 < end1 ) && ( *set1 < *set2 ) ) {
135  sum ++;
136  set1++;
137  }
138  }
139  else if( *set1 > *set2 ) {
140  while ( ( set2 < end2 ) && ( *set1 > *set2 ) ) {
141  sum ++;
142  set2++;
143  }
144  }
145  else {
146  pastix_print_error( "reordering: fatal error occured" );
147  }
148
149  /* The computation is stopped if sum overlapped a given limit (stop criterion) */
150  if ( sum >= stop ) {
151  return stop;
152  }
153  }
154
155  sum += end1 - set1;
156  sum += end2 - set2;
157
158  if ( sum >= stop ) {
159  return stop;
160  }
161
162  return sum;
163 }
164
165 /**
166  *******************************************************************************
167  *
168  * @ingroup symbol_dev_reordering
169  *
170  * @brief Reorder rows of a supernode with the nearest insertion TSP heuristic.
171  *
172  * See reordering paper: http://epubs.siam.org/doi/10.1137/16M1062454.
173  *
174  *******************************************************************************
175  *
176  * @param[in] size
177  * Number of rows in the current supernode.
178  *
179  * @param[in, out] order
180  * The pointer to the ordering structure. At exit, this
181  * ordering is updated with the new ordering for the current supernode
182  * being reordered.
183  *
184  * @param[in] sn_id
185  * Identifier for the current supernode.
186  *
187  * @param[in] lw_vectors
188  * The pointer to the sets of lower contributing
189  * supernodes for each row of the current supernode. Those lower
190  * contributing supernodes correspond to supernodes with a level higher
191  * than split_level criterion.
192  *
193  * @param[in] lw_vectors_size
194  * The pointer to the sizes of each set of lower contributing
195  * supernode, to stop the computation when a row have been totally
196  * covered.
197  *
198  * @param[in] up_vectors
199  * The pointer to the sets of upper contributing
200  * supernodes for each row of the current supernode. Those upper
201  * contributing supernodes correspond to supernodes with a level smaller
202  * than split_level criterion.
203  *
204  * @param[in] up_vectors_size
205  * The pointer to the sizes of each set of upper contributing
206  * supernode, to stop the computation when a row have been totally
207  * covered.
208  *
209  * @param[in] stop_criterion
210  * The stop criterion to disregard rows that are far away.
211  *
212  *******************************************************************************/
213 static inline void
215  pastix_int_t **lw_vectors, pastix_int_t *lw_vectors_size,
216  pastix_int_t **up_vectors, pastix_int_t *up_vectors_size,
217  pastix_int_t stop_criterion )
218 {
219  pastix_int_t i, j, k, l, elected;
220  pastix_int_t *tmpinvp;
221  pastix_int_t *tmplen;
222  pastix_int_t distance;
223
224
225  if ( size < 3 ) {
226  return;
227  }
228
229  MALLOC_INTERN( tmpinvp, size+1, pastix_int_t );
230  MALLOC_INTERN( tmplen, size+1, pastix_int_t );
231  memset( tmplen, 0, ( size + 1 ) * sizeof(pastix_int_t) );
232
233  /* Insert a ghost element with no connexion to any supernodes */
234  tmpinvp[0] = -1;
235  tmpinvp[1] = 0;
236
237  distance = hamming_distance( lw_vectors, lw_vectors_size, 0, -1, stop_criterion );
238
239  tmplen[0] = distance;
240  tmplen[1] = distance;
241
242  for (i=1; i<size; i++) {
243  pastix_int_t first_pos;
244  pastix_int_t last_pos;
245
246  pastix_int_t lw_before_pos;
247  pastix_int_t lw_after_pos;
248
249  pastix_int_t up_before_pos;
250  pastix_int_t up_after_pos;
251
252  pastix_int_t minl;
253  pastix_int_t mpos;
254  pastix_int_t min_cut;
255
256  /* Start by adding the row in first position */
257  lw_before_pos = hamming_distance( lw_vectors, lw_vectors_size, i,
258  tmpinvp[0], stop_criterion );
259  lw_after_pos = hamming_distance( lw_vectors, lw_vectors_size, i,
260  tmpinvp[1], stop_criterion );
261  up_after_pos = hamming_distance( up_vectors, up_vectors_size, i,
262  tmpinvp[1], 1 );
263
264  minl = lw_before_pos + lw_after_pos - tmplen[0];
265  mpos = 1;
266  min_cut = -1;
267
268  for (j=1; j<i; j++) {
269  up_before_pos = up_after_pos;
270  up_after_pos = hamming_distance( up_vectors, up_vectors_size, i,
271  tmpinvp[j+1], 1 );
272
273  if ( (up_before_pos < 1) ||
274  (up_after_pos < 1) )
275  {
276  /* If split was used previously, this first distance may not be already computed */
277  if ( lw_after_pos == -1 ) {
278  lw_before_pos = hamming_distance( lw_vectors, lw_vectors_size, i,
279  tmpinvp[j], stop_criterion );
280  }
281  else {
282  lw_before_pos = lw_after_pos;
283  }
284
285  lw_after_pos = hamming_distance( lw_vectors, lw_vectors_size, i,
286  tmpinvp[j+1], stop_criterion );
287
288  l = lw_before_pos + lw_after_pos - tmplen[j];
289
290  /* Minimize the cut between two lines, for the same TSP result */
291  if ( l == minl ) {
292  if ( lw_before_pos < min_cut ) {
293  min_cut = lw_before_pos;
294  minl = l;
295  mpos = j + 1;
296  }
297  if ( lw_after_pos < min_cut ) {
298  min_cut = lw_after_pos;
299  minl = l;
300  mpos = j + 1;
301  }
302  }
303
304  /* Position that minimizes TSP */
305  if ( l < minl ) {
306  min_cut = lw_before_pos;
307  minl = l;
308  mpos = j + 1;
309  if ( lw_after_pos < min_cut ) {
310  min_cut = lw_after_pos;
311  }
312  }
313
314  /* Stop if two lines are equal (already done tmpinvp[j]) */
315  if ( lw_after_pos == 0 ) {
316  min_cut = 0;
317  minl = l;
318  mpos = j + 1;
319  j = i;
320  }
321  }
322  else {
323  lw_after_pos = -1;
324  }
325  }
326
327  /* Test between last and first */
328  first_pos = hamming_distance( lw_vectors, lw_vectors_size, i,
329  tmpinvp[0], stop_criterion );
330  last_pos = hamming_distance( lw_vectors, lw_vectors_size, i,
331  tmpinvp[i], stop_criterion );
332
333  lw_before_pos = hamming_distance( lw_vectors, lw_vectors_size, i,
334  tmpinvp[mpos-1], stop_criterion );
335  lw_after_pos = hamming_distance( lw_vectors, lw_vectors_size, i,
336  tmpinvp[mpos ], stop_criterion );
337
338  l = first_pos + last_pos - tmplen[i];
339  if ( l < minl ) {
340  minl = l;
341  mpos = i + 1;
342  }
343
344  if ( mpos > 0 ) {
345  tmplen[mpos-1] = lw_before_pos;
346  }
347
348  if ( mpos < ( i + 1 ) ) {
349  pastix_int_t tmpi, tmpl;
350  k = i;
351  l = lw_after_pos;
352
353  /* Insert the line in the tmpinvp/tmplen arrays */
354  for (j=mpos; j<i+2; j++) {
355  tmpi = tmpinvp[j];
356  tmpl = tmplen[j];
357
358  tmpinvp[j] = k;
359  tmplen[j] = l;
360
361  k = tmpi;
362  l = tmpl;
363  }
364  }
365  else {
366  tmpinvp[i+1] = i;
367  tmplen[i+1] = first_pos;
368  }
369  }
370
371  /* Look for the ghost element */
372  elected = 0;
373  for (i=0; i<size; i++) {
374  if ( tmpinvp[i] == -1 ) {
375  elected = i;
376  }
377  }
378
379  /* Apply the local permutation to the global one */
380  {
381  pastix_int_t *sn_connected;
382  pastix_int_t *peritab = order->peritab + order->rangtab[sn_id];
383
384  MALLOC_INTERN( sn_connected, size, pastix_int_t );
385  for (i=0; i<size; i++) {
386  sn_connected[i] = peritab[ tmpinvp[(i + 1 + elected)%(size+1)] ];
387  }
388  memcpy( peritab, sn_connected, size * sizeof(pastix_int_t) );
389  memFree_null( sn_connected );
390  }
391
392  memFree_null( tmpinvp );
393  memFree_null( tmplen );
394 }
395
396 /**
397  *******************************************************************************
398  *
399  * @ingroup symbol_dev_reordering
400  *
401  * @brief Reorder a supernode
402  *
403  * This function computes the set of contributing supernodes for each row, and
404  * then call a TSP heuristic to minimize the Hamiltonian Path.
405  *
406  *******************************************************************************
407  *
408  * @param[in] symbptr
409  * The pointer to the symbolic structure.
410  *
411  * @param[in] cblk
412  * The pointer to the current supernode being reordered.
413  *
414  * @param[in, out] order
415  * The ordering providing by Scotch. This ordering will be
416  * updated with the new rows permutation for the current supernode.
417  *
418  * @param[out] levels
419  * The pointer to the levels structure, giving the level of
420  * each supernode in the elimination tree. To be computed inside.
421  *
422  * @param[in, out] depthweight
423  * This array provides the number of supernodes
424  * corresponding to depth from 1 to depthmax.
425  *
426  * @param[in] depthmax
427  * The maximum depth in the elimination tree.
428  *
429  * @param[in] split_level
430  * Parameter to activate the split level heuristic,
431  * dividing distances computations into two stages: for upper and for
432  * lower contruibuting supernodes. If a resulting distance for upper
433  * supernodes is large enough, the computation is stopped, as long as
434  * it will be large taking into account lower contributing supernodes.
435  *
436  * @param[in] stop_criterion
437  * The stop criterion to disregard rows that are far away.
438  *
439  *******************************************************************************/
440 void
442  const symbol_cblk_t *cblk,
443  pastix_order_t *order,
444  const pastix_int_t *levels,
445  pastix_int_t *depthweight,
446  pastix_int_t depthmax,
447  pastix_int_t split_level,
448  pastix_int_t stop_criterion )
449 {
450  symbol_blok_t *blok;
451  pastix_int_t **up_vectors, *up_vectors_size;
452  pastix_int_t **lw_vectors, *lw_vectors_size;
453
454  pastix_int_t size = cblk->lcolnum - cblk->fcolnum + 1;
455  pastix_int_t local_split_level = split_level;
456  pastix_int_t i, iterblok;
457  pastix_int_t *brow = symbptr->browtab;
458
459  /**
460  * Compute hamming vectors in two subsets:
461  * - The upper subset contains the cblk with level higher than the split_level
462  * in the elimination tree, (or depth lower than levels[cblk])
463  * - The lower subset contains the cblk with level lower than the split_level
464  * in the elimination tree, (or depth higher than levels[cblk])
465  *
466  * The delimitation between the lower and upper levels is made such that
467  * the upper level represents 17% to 25% of the total number of cblk.
468  */
469  {
470  pastix_int_t blokweight;
471  pastix_int_t weight = 0;
472
473  /* Compute the weigth of each level */
474  for (iterblok=cblk[0].brownum; iterblok<cblk[1].brownum; iterblok++) {
475  blok = symbptr->bloktab + brow[iterblok];
476  blokweight = blok->lrownum - blok->frownum + 1;
477
478  depthweight[ levels[ blok->lcblknm ] - 1 ] += blokweight;
479  weight += blokweight;
480  }
481
482  /**
483  * Compute the split_level:
485  * and we try to correct it to minimize the following iterative process
486  */
487  {
488  /* Current for each line within the current cblk the number of contributions */
489  pastix_int_t up_total = 0;
490  pastix_int_t lw_total = 0;
491  pastix_int_t sign = 0;
492
493  split:
494  up_total = 0;
495  lw_total = 0;
496
497  for (i=0; i<local_split_level; i++) {
498  up_total += depthweight[i];
499  }
500  for (; i<depthmax; i++) {
501  lw_total += depthweight[i];
502  }
503
504  /* If there are too many upper bloks */
505  if ( (lw_total < (5 * up_total)) &&
506  (lw_total > 10) && (up_total > 10) && (sign <= 0)) {
507  local_split_level--;
508  sign--;
509  goto split;
510  }
511
512  /* If there are too many lower bloks */
513  if ( (lw_total > (3 * up_total)) &&
514  (lw_total > 10) && (up_total > 10) && (sign >= 0) ) {
515  local_split_level++;
516  sign++;
517  goto split;
518  }
519  }
520
521  /* Compute the Hamming vector size for each row of the cblk */
522  MALLOC_INTERN( up_vectors_size, size, pastix_int_t );
523  memset( up_vectors_size, 0, size * sizeof(pastix_int_t) );
524  MALLOC_INTERN( lw_vectors_size, size, pastix_int_t );
525  memset( lw_vectors_size, 0, size * sizeof(pastix_int_t) );
526
527  for (iterblok=cblk[0].brownum; iterblok<cblk[1].brownum; iterblok++) {
528  blok = symbptr->bloktab + brow[iterblok];
529
530  /* For upper levels in nested dissection */
531  if (levels[blok->lcblknm] <= local_split_level) {
532  for (i=blok->frownum; i<=blok->lrownum; i++) {
533  pastix_int_t index = i - cblk->fcolnum;
534  up_vectors_size[index]++;
535  }
536  }
537  else {
538  for (i=blok->frownum; i<=blok->lrownum; i++) {
539  pastix_int_t index = i - cblk->fcolnum;
540  lw_vectors_size[index]++;
541  }
542  }
543  }
544
545  /* Initiate Hamming vectors structure */
546  MALLOC_INTERN(lw_vectors, size, pastix_int_t*);
547  MALLOC_INTERN(up_vectors, size, pastix_int_t*);
548  for (i=0; i<size; i++) {
549  MALLOC_INTERN(lw_vectors[i], lw_vectors_size[i], pastix_int_t);
550  MALLOC_INTERN(up_vectors[i], up_vectors_size[i], pastix_int_t);
551  memset(lw_vectors[i], 0, lw_vectors_size[i] * sizeof(pastix_int_t));
552  memset(up_vectors[i], 0, up_vectors_size[i] * sizeof(pastix_int_t));
553  }
554  memset( lw_vectors_size, 0, size * sizeof(pastix_int_t) );
555  memset( up_vectors_size, 0, size * sizeof(pastix_int_t) );
556
557  /* Fill-in vectors structure with contributing cblks */
558  for (iterblok=cblk[0].brownum; iterblok<cblk[1].brownum; iterblok++)
559  {
560  blok = symbptr->bloktab + brow[iterblok];
561
562  /* For upper levels in nested dissection */
563  if (levels[blok->lcblknm] <= local_split_level) {
564  for (i=blok->frownum; i<=blok->lrownum; i++) {
565  pastix_int_t index = i - cblk->fcolnum;
566  up_vectors[index][up_vectors_size[index]] = blok->lcblknm;
567  up_vectors_size[index]++;
568  }
569  }
570  else{
571  for (i=blok->frownum; i<=blok->lrownum; i++) {
572  pastix_int_t index = i - cblk->fcolnum;
573  lw_vectors[index][lw_vectors_size[index]] = blok->lcblknm;
574  lw_vectors_size[index]++;
575  }
576  }
577  }
578  (void)weight;
579  }
580
581  /* Apply the pseudo-TSP algorithm to the rows in the current supernode */
582  symbol_reorder_tsp( size, order, cblk - symbptr->cblktab,
583  lw_vectors, lw_vectors_size,
584  up_vectors, up_vectors_size,
585  stop_criterion );
586
587  for (i=0; i<size; i++) {
588  memFree_null( lw_vectors[i] );
589  memFree_null( up_vectors[i] );
590  }
591  memFree_null( lw_vectors );
592  memFree_null( up_vectors );
593  memFree_null( lw_vectors_size );
594  memFree_null( up_vectors_size );
595 }
596
597 /**
598  *******************************************************************************
599  *
600  * @ingroup pastix_symbol
601  *
602  * @brief Compute the reordering on the complete matrix.
603  *
604  *******************************************************************************
605  *
606  * @param[in] pastix_data
607  * The pastix_data structure that describes the solver instance. On
608  * exit, the field symbmtx is updated with the new symbol matrix, and
609  * the field ordemesh is updated with the new ordering. The split_level
610  * field activates the split level heuristic,
611  * dividing distances computations into two stages: for upper and for
612  * lower contruibuting supernodes. If a resulting distance for upper
613  * supernodes is large enough, the computation is stopped, as long as
614  * it will be large taking into account lower contributing supernodes.
615  * The stop_criterion field disregards rows that are far away.
616  *
617  *******************************************************************************/
618 void
620 {
621  symbol_matrix_t *symbptr = pastix_data->symbmtx;
622  pastix_int_t cblknbr = symbptr->cblknbr;
623
624  pastix_int_t i, maxdepth;
625  pastix_int_t *levels;
626  pastix_order_t *order = pastix_data->ordemesh;
627
628  /* Create the levels array to compute the depth of each cblk and the maximum depth */
629  {
630  maxdepth = 0;
631  levels = calloc( cblknbr, sizeof(pastix_int_t) );
632
633  for (i=0; i<cblknbr; i++) {
634  levels[i] = compute_cblklevel( order->treetab, levels, i );
635  maxdepth = pastix_imax( maxdepth, levels[i] );
636  }
637  }
638
639  /**
640  * Compute the reordering using either sequential or parallel method
641  */
642  symbol_reorder( pastix_data, maxdepth, levels );
643
644  /* Update the permutation */
645  for (i=0; i<symbptr->nodenbr; i++) {
646  order->permtab[ order->peritab[i] ] = i;
647  }
648  memFree_null( levels );
649 }
650
651 /**
652  *******************************************************************************
653  *
654  * @ingroup pastix_symbol
655  *
656  * @brief Compute the number of operations required to compute the reordering on
657  * the complete matrix.
658  *
659  * The number of operation is compuyted and then printed on the standard output.
660  *
661  *******************************************************************************
662  *
663  * @param[in] symbptr
664  * The pointer to the symbolic structure.
665  *
666  *******************************************************************************/
667 void
669 {
670  symbol_cblk_t *cblk;
671  pastix_int_t itercblk, iterblok;
672  pastix_int_t cblknbr;
673  pastix_int_t nbiops, schur_nbiops = 0;
674
675  cblk = symbptr->cblktab;
676  cblknbr = symbptr->cblknbr;
677  nbiops = 0;
678
679  /*
680  * nbcblk is the number of non zeroes intersection between indivudal rows
681  * and block columns.
682  */
683  for (itercblk=0; itercblk<cblknbr; itercblk++, cblk++) {
684  pastix_int_t width;
685  pastix_int_t nbcblk = 0;
686
687  if (cblk->fcolnum >= symbptr->schurfcol )
688  continue;
689
690  for (iterblok=cblk[0].brownum; iterblok<cblk[1].brownum; iterblok++) {
691  symbol_blok_t *blok = symbptr->bloktab + symbptr->browtab[iterblok];
692  assert( blok->fcblknm == itercblk );
693
694  nbcblk += blok->lrownum - blok->frownum + 1;
695  }
696  width = cblk->lcolnum - cblk->fcolnum + 1;
697  nbiops += nbcblk * (width-1);
698
699  if ( itercblk == (cblknbr-1) ) {
700  schur_nbiops = nbcblk * (width-1);
701  }
702  }
703
704  if ( nbiops == 0 ) {
705  nbiops = 1;
706  }
707  fprintf( stdout, OUT_REORDERING_OPS,
708  (long)schur_nbiops, (double)schur_nbiops / (double)(nbiops) * 100.,
709  (long)nbiops );
710 }
BEGIN_C_DECLS typedef int pastix_int_t
Definition: datatypes.h:51
pastix_int_t * treetab
Definition: order.h:54
pastix_int_t * permtab
Definition: order.h:51
pastix_int_t * peritab
Definition: order.h:52
pastix_int_t * rangtab
Definition: order.h:53
Order structure.
Definition: order.h:47
pastix_int_t fcblknm
Definition: symbol.h:63
pastix_int_t frownum
Definition: symbol.h:60
pastix_int_t lrownum
Definition: symbol.h:61
pastix_int_t * browtab
Definition: symbol.h:85
symbol_cblk_t * cblktab
Definition: symbol.h:83
pastix_int_t schurfcol
Definition: symbol.h:82
pastix_int_t brownum
Definition: symbol.h:49
pastix_int_t fcolnum
Definition: symbol.h:46
pastix_int_t lcolnum
Definition: symbol.h:47
symbol_blok_t * bloktab
Definition: symbol.h:84
pastix_int_t lcblknm
Definition: symbol.h:62
pastix_int_t nodenbr
Definition: symbol.h:81
pastix_int_t cblknbr
Definition: symbol.h:79
void pastixSymbolReordering(pastix_data_t *)
Compute the reordering on the complete matrix.
void pastixSymbolReorderingPrintComplexity(const symbol_matrix_t *symbptr)
Compute the number of operations required to compute the reordering on the complete matrix.
Symbol block structure.
Definition: symbol.h:59
Symbol column block structure.
Definition: symbol.h:45
Symbol matrix structure.
Definition: symbol.h:77
pastix_order_t * ordemesh
Definition: pastixdata.h:98
symbol_matrix_t * symbmtx
Definition: pastixdata.h:100
Main PaStiX data structure.
Definition: pastixdata.h:68
void symbol_reorder(pastix_data_t *pastix_data, pastix_int_t maxdepth, pastix_int_t *levels)
Reorder all node.
static pastix_int_t hamming_distance(pastix_int_t **vectors, pastix_int_t *vectors_size, pastix_int_t xi, pastix_int_t xj, pastix_int_t stop)
Compute the distance between two rows of a same supernode.
static void symbol_reorder_tsp(pastix_int_t size, pastix_order_t *order, pastix_int_t sn_id, pastix_int_t **lw_vectors, pastix_int_t *lw_vectors_size, pastix_int_t **up_vectors, pastix_int_t *up_vectors_size, pastix_int_t stop_criterion)
Reorder rows of a supernode with the nearest insertion TSP heuristic.
static pastix_int_t compute_cblklevel(const pastix_int_t *treetab, const pastix_int_t *levels, pastix_int_t cblknum)
Compute the level of supernode cblknum, with Scotch treetab.
void symbol_reorder_cblk(const symbol_matrix_t *symbptr, const symbol_cblk_t *cblk, pastix_order_t *order, const pastix_int_t *levels, pastix_int_t *depthweight, pastix_int_t depthmax, pastix_int_t split_level, pastix_int_t stop_criterion)
Reorder a supernode.