PaStiX Handbook  6.2.1
order.h
Go to the documentation of this file.
1 /**
2  *
3  * @file order.h
4  *
5  * PaStiX order structure routines
6  *
7  * @copyright 2004-2021 Bordeaux INP, CNRS (LaBRI UMR 5800), Inria,
8  * Univ. Bordeaux. All rights reserved.
9  *
10  * @version 6.2.0
11  * @author Francois Pellegrini
12  * @author Mathieu Faverge
13  * @author Gregoire Pichon
14  * @author Pierre Ramet
15  * @date 2021-01-14
16  *
17  *
18  * @addtogroup pastix_order
19  * @{
20  * @brief Functions to generate and manipulate the order structure.
21  *
22  * This module provides the set of function to prepare the order structure
23  * associated to a given sparse matrix. It is possible to call Scotch,
24  * PT-Scotch, Metis and ParMetis to build a new ordering that minimize the
25  * fill-in and maximize the level of parallelism.
26  *
27  **/
28 #ifndef _pastix_order_h_
29 #define _pastix_order_h_
30 
31 #include "pastix/config.h"
32 #include "pastix/datatypes.h"
33 
34 BEGIN_C_DECLS
35 
36 struct etree_s;
37 typedef struct etree_s EliminTree;
38 
39 /**
40  * @brief Order structure.
41  *
42  * This structure stores the permutation (and inverse permutation) associated to the ordering.
43  * It also stores the partitioning tree and the set of supernodes.
44  */
45 typedef struct pastix_order_s {
46  pastix_int_t baseval; /**< base value used for numbering */
47  pastix_int_t vertnbr; /**< Number of vertices */
48  pastix_int_t cblknbr; /**< Number of column blocks */
49  pastix_int_t *permtab; /**< Permutation array of size vertnbr [based] */
50  pastix_int_t *peritab; /**< Inverse permutation array of size vertnbr [based] */
51  pastix_int_t *rangtab; /**< Supernode array of size cblknbr+1 [based,+1] */
52  pastix_int_t *treetab; /**< Partitioning tree of size cblknbr+1 [based] */
53  int8_t *selevtx; /**< Selected vertices for low-rank clustering of size cblknbr */
54  pastix_int_t sndenbr; /**< The number of original supernodes before clustering */
55  pastix_int_t *sndetab; /**< Original supernode array of size sndenbr [based,+1] */
57 
58 /**
59  * @name Order basic subroutines
60  * @{
61  */
62 int pastixOrderInit ( pastix_order_t * const ordeptr,
63  pastix_int_t baseval,
64  pastix_int_t vertnbr,
65  pastix_int_t cblknbr,
66  pastix_int_t * const perm,
67  pastix_int_t * const invp,
68  pastix_int_t * const rang,
69  pastix_int_t * const tree );
70 int pastixOrderAlloc ( pastix_order_t * const ordeptr,
71  pastix_int_t vertnbr,
72  pastix_int_t cblknbr );
73 int pastixOrderAllocId( pastix_order_t * const ordeptr,
74  pastix_int_t vertnbr );
75 void pastixOrderExit ( pastix_order_t * const ordeptr );
76 void pastixOrderBase ( pastix_order_t * const ordeptr,
77  pastix_int_t baseval );
78 int pastixOrderCheck ( const pastix_order_t * const ordeptr );
79 void pastixOrderExpand( pastix_order_t * const ordeptr,
80  spmatrix_t * const spm);
81 int pastixOrderCopy ( pastix_order_t * const ordedst,
82  const pastix_order_t * const ordesrc );
83 
84 const pastix_order_t *pastixOrderGet( const pastix_data_t * const pastix_data );
85 
86 void pastixOrderBcast( pastix_order_t *ordemesh,
87  int root,
88  PASTIX_Comm pastix_comm );
89 
90 /**
91  * @}
92  * @name Order IO subroutines
93  * @{
94  */
95 int pastixOrderLoad( const pastix_data_t *pastix_data, pastix_order_t *ordeptr );
96 int pastixOrderSave( pastix_data_t *pastix_data, const pastix_order_t *ordeptr );
97 
98 /**
99  * @}
100  * @name Order compute subroutines
101  * @{
102  */
103 int pastixOrderComputeScotch( pastix_data_t *pastix_data, pastix_graph_t *graph );
104 int pastixOrderComputePTScotch( pastix_data_t *pastix_data, pastix_graph_t *graph );
105 int pastixOrderComputeMetis( pastix_data_t *pastix_data, pastix_graph_t *graph );
106 int pastixOrderComputeParMetis( pastix_data_t *pastix_data, pastix_graph_t *graph );
107 
108 int pastixOrderGrid( pastix_order_t **myorder, pastix_int_t nx,
109  pastix_int_t ny, pastix_int_t nz );
110 
111 /**
112  * @}
113  * @name Order manipulation subroutines
114  * @{
115  */
116 void pastixOrderFindSupernodes( const pastix_graph_t *graph,
117  pastix_order_t * const ordeptr );
118 
119 int pastixOrderAmalgamate( int verbose,
120  int ilu,
121  int levelk,
122  int rat_cblk,
123  int rat_blas,
124  pastix_graph_t *graph,
125  pastix_order_t *orderptr,
126  PASTIX_Comm pastix_comm );
127 
129  pastix_int_t level_tasks2d,
130  pastix_int_t width_tasks2d );
131 
133  pastix_int_t new_n,
134  const pastix_int_t *perm );
135 
136 /**
137  * @}
138  */
139 
140 END_C_DECLS
141 
142 #endif /* _pastix_order_h_ */
143 
144 /**
145  * @}
146  */
pastix_order_s::cblknbr
pastix_int_t cblknbr
Definition: order.h:48
pastixOrderSave
int pastixOrderSave(pastix_data_t *pastix_data, const pastix_order_t *ordeptr)
Save an ordering to a file.
Definition: order_io.c:294
etree_s
Elimination tree.
Definition: elimintree.h:39
pastixOrderAllocId
int pastixOrderAllocId(pastix_order_t *const ordeptr, pastix_int_t vertnbr)
Allocate the order structure for a given number of vertices with no cblk, and id permutation.
Definition: order.c:123
pastix_order_t
struct pastix_order_s pastix_order_t
Order structure.
pastix_order_s::peritab
pastix_int_t * peritab
Definition: order.h:50
pastix_order_s::permtab
pastix_int_t * permtab
Definition: order.h:49
pastixOrderExit
void pastixOrderExit(pastix_order_t *const ordeptr)
Free the arrays initialized in the order structure.
Definition: order.c:273
pastix_order_s::treetab
pastix_int_t * treetab
Definition: order.h:52
pastix_order_s
Order structure.
Definition: order.h:45
pastix_order_s::selevtx
int8_t * selevtx
Definition: order.h:53
pastixOrderBcast
void pastixOrderBcast(pastix_order_t *ordemesh, int root, PASTIX_Comm pastix_comm)
This routine broadcast the ordemesh structure from node root to all the other nodes.
Definition: order.c:605
pastixOrderComputeMetis
int pastixOrderComputeMetis(pastix_data_t *pastix_data, pastix_graph_t *graph)
Compute the ordering of the graph given as parameter with Metis library.
Definition: order_compute_metis.c:60
pastix_order_s::vertnbr
pastix_int_t vertnbr
Definition: order.h:47
pastixOrderAddIsolate
int pastixOrderAddIsolate(pastix_order_t *ordeptr, pastix_int_t new_n, const pastix_int_t *perm)
This routine combines two permutation arrays when a subset of vertices has been isolated from the ori...
Definition: order_add_isolate.c:56
pastixOrderGrid
int pastixOrderGrid(pastix_order_t **myorder, pastix_int_t nx, pastix_int_t ny, pastix_int_t nz)
Definition: order_grids.c:307
pastixOrderCopy
int pastixOrderCopy(pastix_order_t *const ordedst, const pastix_order_t *const ordesrc)
This routine copy a given ordering in a new one.
Definition: order.c:496
pastixOrderCheck
int pastixOrderCheck(const pastix_order_t *const ordeptr)
This routine checks the correctness of the ordering structure.
Definition: order_check.c:39
pastixOrderBase
void pastixOrderBase(pastix_order_t *const ordeptr, pastix_int_t baseval)
This routine sets the base of the given ordering structure to the given base value.
Definition: order.c:319
pastixOrderApplyLevelOrder
int pastixOrderApplyLevelOrder(pastix_order_t *ordeptr, pastix_int_t level_tasks2d, pastix_int_t width_tasks2d)
This routine reorder the elimination tree nodes per level.
Definition: order_apply_level_order.c:95
pastixOrderAlloc
int pastixOrderAlloc(pastix_order_t *const ordeptr, pastix_int_t vertnbr, pastix_int_t cblknbr)
Allocate the order structure.
Definition: order.c:55
pastixOrderComputePTScotch
int pastixOrderComputePTScotch(pastix_data_t *pastix_data, pastix_graph_t *graph)
Compute the ordering of the graph given as parameter with PT-Scotch library.
Definition: order_compute_ptscotch.c:60
pastix_order_s::baseval
pastix_int_t baseval
Definition: order.h:46
pastixOrderAmalgamate
int pastixOrderAmalgamate(int verbose, int ilu, int levelk, int rat_cblk, int rat_blas, pastix_graph_t *graph, pastix_order_t *orderptr, PASTIX_Comm pastix_comm)
Update the order structure with an amalgamation algorithm.
Definition: order_amalgamate.c:82
pastixOrderExpand
void pastixOrderExpand(pastix_order_t *const ordeptr, spmatrix_t *const spm)
This routine expand the permutation arrays and the rangtab when the spm is using multiple dof per unk...
Definition: order.c:393
pastixOrderInit
int pastixOrderInit(pastix_order_t *const ordeptr, pastix_int_t baseval, pastix_int_t vertnbr, pastix_int_t cblknbr, pastix_int_t *const perm, pastix_int_t *const invp, pastix_int_t *const rang, pastix_int_t *const tree)
Initialize the order structure with the given values.
Definition: order.c:212
pastix_order_s::rangtab
pastix_int_t * rangtab
Definition: order.h:51
pastixOrderLoad
int pastixOrderLoad(const pastix_data_t *pastix_data, pastix_order_t *ordeptr)
Load an ordering from a file.
Definition: order_io.c:132
pastixOrderFindSupernodes
void pastixOrderFindSupernodes(const pastix_graph_t *graph, pastix_order_t *const ordeptr)
Computes the set of supernodes for a given permutation.
Definition: order_find_supernodes.c:360
pastix_order_s::sndenbr
pastix_int_t sndenbr
Definition: order.h:54
pastixOrderComputeScotch
int pastixOrderComputeScotch(pastix_data_t *pastix_data, pastix_graph_t *graph)
Compute the ordering of the graph given as parameter with Scotch library.
Definition: order_compute_scotch.c:537
pastix_order_s::sndetab
pastix_int_t * sndetab
Definition: order.h:55
pastixOrderGet
const pastix_order_t * pastixOrderGet(const pastix_data_t *const pastix_data)
This routine returns the pointer to the internal order structure to access permutation information.
Definition: order.c:575