PaStiX Handbook  6.2.1
symbol.h
Go to the documentation of this file.
1 /**
2  *
3  * @file symbol.h
4  *
5  * PaStiX symbol 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 David Goudin
12  * @author Francois Pellegrini
13  * @author Mathieu Faverge
14  * @author Pascal Henon
15  * @author Pierre Ramet
16  * @author Gregoire Pichon
17  * @author Tony Delarue
18  * @author Vincent Bridonneau
19  * @date 2020-06-17
20  *
21  * @addtogroup pastix_symbol
22  * @{
23  * @brief Functions to generate and manipulate the symbolic factorization
24  * structure
25  *
26  * This module provides the set of function to generate the symbolic
27  * factorization structure based on a given graph, and an associated
28  * ordering. The symbolic structure is described in the symbol_matrix_t
29  * structure, and it can be generated through two different algorithms
30  * respectively for direct and incomplete factorization.
31  *
32  **/
33 #ifndef _symbol_h_
34 #define _symbol_h_
35 
36 #define SYMBCBLK_NOTHING 0
37 #define SYMBCBLK_PROJ 1
38 #define SYMBCBLK_KWAY 2
39 
40 /**
41  * @brief Symbol column block structure.
42  */
43 typedef struct symbol_cblk_s {
44  pastix_int_t fcolnum; /**< First column index */
45  pastix_int_t lcolnum; /**< Last column index (inclusive) */
46  pastix_int_t bloknum; /**< First block in column (diagonal) */
47  pastix_int_t brownum; /**< First block in row facing the diagonal block in browtab, 0-based */
48  int8_t selevtx;
49 #if defined( PASTIX_SYMBOL_DUMP_SYMBMTX )
50  pastix_int_t split_cblk;
51 #endif
53 
54 /**
55  * @brief Symbol block structure.
56  */
57 typedef struct symbol_blok_s {
58  pastix_int_t frownum; /**< First row index */
59  pastix_int_t lrownum; /**< Last row index (inclusive) */
60  pastix_int_t lcblknm; /**< Local column block */
61  pastix_int_t fcblknm; /**< Facing column block */
63 
64 /**
65  * @brief Symbol matrix structure.
66  *
67  * This structure describes the symbolic block structure of the factorized
68  * matrix L, U is never stored as it is a symmetry of L. This structure is
69  * global and replicated on all processes. The default way to number the block
70  * is the CSC format where block are continuously number per column, the browtab
71  * array stores the CSR representation of the L structure to have a faster
72  * access to the list of blocks updating a column block.
73  *
74  */
75 typedef struct symbol_matrix_s {
76  pastix_int_t baseval; /**< Base value for numbering */
77  pastix_int_t cblknbr; /**< Number of column blocks */
78  pastix_int_t bloknbr; /**< Number of blocks */
79  pastix_int_t nodenbr; /**< Number of nodes (Equal to gN in spm) */
80  pastix_int_t schurfcol; /**< First column of the schur complement */
81  symbol_cblk_t *cblktab; /**< Array of column blocks [+1,based] */
82  symbol_blok_t *bloktab; /**< Array of blocks in CSC format [based] */
83  pastix_int_t *browtab; /**< Array of blocks in CSR format [based] */
84  pastix_int_t browmax; /**< Maximum number of input edges per node */
85  pastix_int_t dof; /**< Degrees of freedom per node (constant
86  if > 0, variadic if < 1 */
87  pastix_int_t *dofs; /**< Array of the first column of each element
88  in the expanded matrix [+1,based] */
90 
91 /**
92  *******************************************************************************
93  *
94  * @brief Get the expanded column indexes of a symbol_cblk.
95  *
96  *******************************************************************************
97  *
98  * @param[in] symbmtx
99  * Pointer to the symbol matrix.
100  *
101  * @param[in] symbcblk
102  * The pointer to the current symbol_cblk.
103  *
104  * @param[inout] fcolnum
105  * First column index of the current cblk.
106  *
107  * @param[inout] symbcblk
108  * Last column index of the current cblk.
109  *
110  * @return The number of columns of the expanded cblk.
111  *
112  *******************************************************************************/
113 static inline pastix_int_t
115  symbol_cblk_t *symbcblk,
116  pastix_int_t *fcolnum,
117  pastix_int_t *lcolnum )
118 {
119  if ( symbmtx->dof < 0 ) {
120  *fcolnum = symbmtx->dofs[symbcblk->fcolnum];
121  *lcolnum = symbmtx->dofs[symbcblk->lcolnum + 1] - 1;
122  }
123  else {
124  *fcolnum = symbmtx->dof * symbcblk->fcolnum;
125  *lcolnum = symbmtx->dof * ( symbcblk->lcolnum + 1 ) - 1;
126  }
127  return (*lcolnum) - (*fcolnum) + 1;
128 }
129 
130 /**
131  *******************************************************************************
132  *
133  * @brief Get the expanded row index of a symbol_blok.
134  *
135  *******************************************************************************
136  *
137  * @param[in] symbmtx
138  * Pointer to the symbol matrix.
139  *
140  * @param[in] symbblok
141  * The pointer to the current symbol_blok.
142  *
143  * @param[inout] frownum
144  * First row index of the current blok.
145  *
146  * @param[inout] lrownum
147  * Last row index of the current blok.
148  *
149  * @return The number of rows of the expanded blok.
150  *
151  *******************************************************************************/
152 static inline pastix_int_t
154  symbol_blok_t *symbblok,
155  pastix_int_t *frownum,
156  pastix_int_t *lrownum )
157 {
158  if ( symbmtx->dof < 0 ) {
159  *frownum = symbmtx->dofs[symbblok->frownum];
160  *lrownum = symbmtx->dofs[symbblok->lrownum + 1] - 1;
161  }
162  else {
163  *frownum = symbmtx->dof * symbblok->frownum;
164  *lrownum = symbmtx->dof * ( symbblok->lrownum + 1 ) - 1;
165  }
166  return (*lrownum) - (*frownum) + 1;
167 }
168 
169 /**
170  * @brief Check if a block is included inside another one.
171  *
172  * Indicate if a blok is included inside another block.
173  * i.e. indicate if the row range of the first block is included in the
174  * one of the second.
175  *
176  * @param[in] blok The block that is tested for inclusion.
177  * @param[in] fblok The block that is suppose to include the first one.
178  *
179  * @retval true if the first block is included in the second one.
180  * @retval false if the first block is not included in the second one.
181  */
182 static inline int
184  const symbol_blok_t *fblok )
185 {
186  return ((blok->frownum >= fblok->frownum) &&
187  (blok->lrownum <= fblok->lrownum));
188 }
189 
190 /**
191  * @name Symbol basic subroutines
192  * @{
193  */
194 void pastixSymbolInit ( const pastix_graph_t *graph,
195  const pastix_order_t *order,
196  symbol_matrix_t *symbptr );
197 void pastixSymbolExit ( symbol_matrix_t *symbptr );
198 void pastixSymbolBase ( symbol_matrix_t *symbptr,
199  const pastix_int_t baseval );
200 void pastixSymbolRealloc( symbol_matrix_t *symbptr );
201 int pastixSymbolCheck ( const symbol_matrix_t *symbptr );
202 void pastixSymbolExpand ( symbol_matrix_t *symbptr );
203 
204 /**
205  * @}
206  * @name Symbol IO subroutines
207  * @{
208  */
209 int pastixSymbolSave( const symbol_matrix_t *symbptr, FILE *stream );
210 int pastixSymbolLoad( symbol_matrix_t *symbptr, FILE *stream );
211 int pastixSymbolDraw( const symbol_matrix_t *symbptr, FILE *stream );
212 void pastixSymbolDrawMap( pastix_data_t *pastix_data,
213  const char *extname,
214  pastix_int_t sndeidx );
215 
216 /**
217  * @}
218  * @name Symbol statistical information subroutines
219  * @{
220  */
221 void pastixSymbolPrintStats( const symbol_matrix_t *symbptr );
222 pastix_int_t pastixSymbolGetNNZ( const symbol_matrix_t *symbptr );
223 void pastixSymbolGetFlops( const symbol_matrix_t *symbmtx,
224  pastix_coeftype_t flttype,
225  pastix_factotype_t factotype,
226  double *thflops,
227  double *rlflops );
228 void pastixSymbolGetTimes( const symbol_matrix_t *symbmtx,
229  pastix_coeftype_t flttype,
230  pastix_factotype_t factotype,
231  double *cblkcost,
232  double *blokcost );
233 
234 /**
235  * @}
236  * @name Symbol reordering subroutines
237  * @{
238  */
239 void pastixSymbolReordering( pastix_data_t * );
241 
242 /**
243  * @}
244  * @name Symbol construction subroutines
245  * @{
246  */
248  const pastix_graph_t *graphA,
249  const pastix_order_t *ordeptr );
250 int pastixSymbolFaxILUk ( symbol_matrix_t *symbptr,
251  pastix_int_t levelk,
252  const pastix_graph_t *graphA,
253  const pastix_order_t *ordeptr );
254 void pastixSymbolRustine ( symbol_matrix_t *symbptr, symbol_matrix_t *symbptr2 );
256 pastix_int_t pastixSymbolGetFacingBloknum( const symbol_matrix_t *symbptr,
257  pastix_int_t bloksrc,
258  pastix_int_t bloknum,
259  pastix_int_t startsearch,
260  int ricar );
261 /**
262  * @}
263  */
264 
265 #endif /* _symbol_h_ */
266 
267 /**
268  * @}
269  */
symbol_blok_get_rownum
static pastix_int_t symbol_blok_get_rownum(const symbol_matrix_t *symbmtx, symbol_blok_t *symbblok, pastix_int_t *frownum, pastix_int_t *lrownum)
Get the expanded row index of a symbol_blok.
Definition: symbol.h:153
symbol_matrix_s
Symbol matrix structure.
Definition: symbol.h:75
symbol_blok_s::lcblknm
pastix_int_t lcblknm
Definition: symbol.h:60
symbol_matrix_s::schurfcol
pastix_int_t schurfcol
Definition: symbol.h:80
pastixSymbolLoad
int pastixSymbolLoad(symbol_matrix_t *symbptr, FILE *stream)
Load the given block matrix structure from the given stream.
Definition: symbol_io.c:51
symbol_cblk_t
struct symbol_cblk_s symbol_cblk_t
Symbol column block structure.
pastixSymbolSave
int pastixSymbolSave(const symbol_matrix_t *symbptr, FILE *stream)
Save the given block matrix structure to the given stream.
Definition: symbol_io.c:147
symbol_blok_t
struct symbol_blok_s symbol_blok_t
Symbol block structure.
symbol_matrix_s::bloktab
symbol_blok_t * bloktab
Definition: symbol.h:82
pastixSymbolGetNNZ
pastix_int_t pastixSymbolGetNNZ(const symbol_matrix_t *symbptr)
Computes the number of non-zero elements in L.
Definition: symbol_cost.c:327
pastixSymbolExit
void pastixSymbolExit(symbol_matrix_t *symbptr)
Free the content of symbolic matrix.
Definition: symbol.c:140
symbol_matrix_s::dofs
pastix_int_t * dofs
Definition: symbol.h:87
symbol_cblk_s::fcolnum
pastix_int_t fcolnum
Definition: symbol.h:44
pastix_order_s
Order structure.
Definition: order.h:45
symbol_matrix_s::nodenbr
pastix_int_t nodenbr
Definition: symbol.h:79
pastixSymbolFaxILUk
int pastixSymbolFaxILUk(symbol_matrix_t *symbptr, pastix_int_t levelk, const pastix_graph_t *graphA, const pastix_order_t *ordeptr)
Create the symbol matrix from the graph of the non zero pattern of the factorized matrix and the supe...
Definition: symbol_fax_iluk.c:55
pastixSymbolBase
void pastixSymbolBase(symbol_matrix_t *symbptr, const pastix_int_t baseval)
Sets the base of the given symbol matrix structure to the given base value.
Definition: symbol_base.c:37
symbol_matrix_s::cblknbr
pastix_int_t cblknbr
Definition: symbol.h:77
symbol_matrix_s::baseval
pastix_int_t baseval
Definition: symbol.h:76
symbol_matrix_s::browtab
pastix_int_t * browtab
Definition: symbol.h:83
symbol_matrix_s::dof
pastix_int_t dof
Definition: symbol.h:85
symbol_matrix_s::bloknbr
pastix_int_t bloknbr
Definition: symbol.h:78
symbol_blok_s::fcblknm
pastix_int_t fcblknm
Definition: symbol.h:61
pastixSymbolDraw
int pastixSymbolDraw(const symbol_matrix_t *symbptr, FILE *stream)
Export the symbol structure in a PostScript format.
Definition: symbol_draw.c:248
pastixSymbolExpand
void pastixSymbolExpand(symbol_matrix_t *symbptr)
Expand the symbol matrix structure based on the dof information (compressed -> expanded)
Definition: symbol_expand.c:181
pastixSymbolReorderingPrintComplexity
void pastixSymbolReorderingPrintComplexity(const symbol_matrix_t *symbptr)
Compute the number of operations required to compute the reordering on the complete matrix.
Definition: symbol_reordering.c:667
symbol_cblk_s::bloknum
pastix_int_t bloknum
Definition: symbol.h:46
pastixSymbolRealloc
void pastixSymbolRealloc(symbol_matrix_t *symbptr)
Reallocate the data structure to optimize the memory alignment.
Definition: symbol.c:173
pastix_factotype_t
enum pastix_factotype_e pastix_factotype_t
Factorization algorithms available for IPARM_FACTORIZATION parameter.
pastixSymbolGetFlops
void pastixSymbolGetFlops(const symbol_matrix_t *symbmtx, pastix_coeftype_t flttype, pastix_factotype_t factotype, double *thflops, double *rlflops)
Computes the number of theoretical and real flops.
Definition: symbol_cost.c:424
symbol_matrix_t
struct symbol_matrix_s symbol_matrix_t
Symbol matrix structure.
symbol_cblk_s::brownum
pastix_int_t brownum
Definition: symbol.h:47
symbol_cblk_s::lcolnum
pastix_int_t lcolnum
Definition: symbol.h:45
pastixSymbolCheck
int pastixSymbolCheck(const symbol_matrix_t *symbptr)
Checks the consistency of the given symbolic block matrix.
Definition: symbol_check.c:47
symbol_blok_s::frownum
pastix_int_t frownum
Definition: symbol.h:58
pastixSymbolGetTimes
void pastixSymbolGetTimes(const symbol_matrix_t *symbmtx, pastix_coeftype_t flttype, pastix_factotype_t factotype, double *cblkcost, double *blokcost)
Computes the cost of structure for the costMatrixBuild() function.
Definition: symbol_cost.c:482
symbol_matrix_s::cblktab
symbol_cblk_t * cblktab
Definition: symbol.h:81
symbol_blok_s
Symbol block structure.
Definition: symbol.h:57
pastixSymbolBuildRowtab
void pastixSymbolBuildRowtab(symbol_matrix_t *symbptr)
Construct the browtab array that stores the blocks in a CSR way.
Definition: symbol.c:305
pastixSymbolReordering
void pastixSymbolReordering(pastix_data_t *)
Compute the reordering on the complete matrix.
Definition: symbol_reordering.c:618
symbol_cblk_s
Symbol column block structure.
Definition: symbol.h:43
symbol_matrix_s::browmax
pastix_int_t browmax
Definition: symbol.h:84
symbol_cblk_get_colnum
static pastix_int_t symbol_cblk_get_colnum(const symbol_matrix_t *symbmtx, symbol_cblk_t *symbcblk, pastix_int_t *fcolnum, pastix_int_t *lcolnum)
Get the expanded column indexes of a symbol_cblk.
Definition: symbol.h:114
is_symbblock_inside_fblock
static int is_symbblock_inside_fblock(const symbol_blok_t *blok, const symbol_blok_t *fblok)
Check if a block is included inside another one.
Definition: symbol.h:183
pastix_coeftype_t
#define pastix_coeftype_t
Arithmetic types.
Definition: api.h:283
pastixSymbolPrintStats
void pastixSymbolPrintStats(const symbol_matrix_t *symbptr)
Print statistical information about the symbolic matrix structure.
Definition: symbol.c:392
symbol_blok_s::lrownum
pastix_int_t lrownum
Definition: symbol.h:59
pastixSymbolGetFacingBloknum
pastix_int_t pastixSymbolGetFacingBloknum(const symbol_matrix_t *symbptr, pastix_int_t bloksrc, pastix_int_t bloknum, pastix_int_t startsearch, int ricar)
Search the targeted block C for a couple of blocks A and B.
Definition: symbol.c:235
pastixSymbolFaxDirect
int pastixSymbolFaxDirect(symbol_matrix_t *symbptr, const pastix_graph_t *graphA, const pastix_order_t *ordeptr)
Compute the block symbolic factorization of the given matrix graph according to the given vertex orde...
Definition: symbol_fax_direct.c:77