PaStiX Handbook  6.3.2
Ordering

Functions to generate and manipulate the order structure. More...

Modules

 Ordering internal function documentation
 

Data Structures

struct  pastix_order_s
 Order structure. More...
 

Typedefs

typedef BEGIN_C_DECLS struct pastix_order_s pastix_order_t
 Order structure. More...
 

Functions

pastix_int_torderGetExpandedPeritab (pastix_order_t *ordeptr, const spmatrix_t *spm)
 This routine expand the peritab array for multi-dof matrices. More...
 
int orderAddIsolate (pastix_order_t *ordemesh, 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 original graph through graphIsolate() function. More...
 
int orderAmalgamate (int verbose, int ilu, int levelk, int rat_cblk, int rat_blas, pastix_graph_t *csc, pastix_order_t *orderptr, PASTIX_Comm pastix_comm)
 Update the order structure with an amalgamation algorithm. More...
 
int orderApplyLevelOrder (pastix_order_t *order, pastix_int_t level_tasks2d, pastix_int_t width_tasks2d)
 This routine reorder the elimination tree nodes per level. More...
 
void orderDraw (pastix_data_t *pastix_data, const char *extname, pastix_int_t sndeidx, int dump)
 Dump the last separator into an ivview file. More...
 
void orderFindSupernodes (const pastix_graph_t *graph, pastix_order_t *const ordeptr)
 Computes the set of supernodes for a given permutation. More...
 
int orderComputeMetis (pastix_data_t *pastix_data, pastix_graph_t *graph)
 Compute the ordering of the graph given as parameter with Metis library. More...
 
static void ocpts_graph_check (const SCOTCH_Dgraph *graph, int procnum)
 Check the PT-Scotch distributed graph. More...
 
static void ocpts_graph_init (SCOTCH_Dgraph *scotchgraph, pastix_graph_t *graph, PASTIX_Comm comm)
 Build the PT-Scotch distributed graph. More...
 
static void ocpts_graph_exit (SCOTCH_Dgraph *scotchgraph, PASTIX_Comm comm)
 Cleanup the PT-Scotch graph structure and free the associated data. More...
 
static int ocpts_compute_graph_ordering (pastix_data_t *pastix_data, SCOTCH_Dgraph *scotchgraph)
 Compute the graph ordering. More...
 
int orderComputePTScotch (pastix_data_t *pastix_data, pastix_graph_t *graph)
 Compute the ordering of the graph given as parameter with PT-Scotch library. More...
 
static void ocs_graph_check (const SCOTCH_Graph *graph, int procnum)
 Check the generated Scotch graph. More...
 
static void ocs_graph_init (SCOTCH_Graph *scotchgraph, pastix_graph_t *graph)
 Build the Scotch graph. More...
 
static void ocs_graph_exit (SCOTCH_Graph *scotchgraph)
 Cleanup the Scotch graph structure and free the associated data. More...
 
static int ocs_compute_graph_ordering (pastix_data_t *pastix_data, SCOTCH_Graph *scotchgraph)
 Compute the graph ordering. More...
 
int orderComputeScotch (pastix_data_t *pastix_data, pastix_graph_t *graph)
 Compute the ordering of the graph given as parameter with Scotch library. More...
 
int orderComputePersonal (pastix_data_t *pastix_data, pastix_graph_t *graph, pastix_order_t *myorder)
 Computes the personal ordering of the PaStiX instance. More...
 
char * order_scotch_build_strategy (const pastix_int_t *iparm, pastix_int_t procnum, int isPTscotch)
 Generate the ordering strategy string based on the input parameters. More...
 
void order_scotch_reallocate_ordemesh (pastix_order_t *ordemesh)
 Reallocate the ordering structure. More...
 
pastix_int_t orderSupernodes (const pastix_graph_t *graph, pastix_order_t *order, EliminTree *etree, pastix_int_t *iparm, int do_schur)
 Order the supernodes with one of the clustering strategies. More...
 

Order basic subroutines

int pastixOrderInit (pastix_order_t *const ordeptr, pastix_int_t baseval, pastix_int_t vertnbr, pastix_int_t cblknbr, pastix_int_t *const permtab, pastix_int_t *const peritab, pastix_int_t *const rangtab, pastix_int_t *const treetab)
 Initialize the order structure with the given values. More...
 
int pastixOrderAlloc (pastix_order_t *const ordeptr, pastix_int_t vertnbr, pastix_int_t cblknbr)
 Allocate the order structure. More...
 
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. More...
 
void pastixOrderExit (pastix_order_t *const ordeptr)
 Free the arrays initialized in the order structure. More...
 
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. More...
 
int pastixOrderCheck (const pastix_order_t *const ordeptr)
 This routine checks the correctness of the ordering structure. More...
 
void pastixOrderExpand (pastix_order_t *ordeptr, const spmatrix_t *spm)
 This routine expand the permutation arrays and the rangtab when the spm is using multiple dof per unknown. More...
 
int pastixOrderCopy (pastix_order_t *const ordedst, const pastix_order_t *const ordesrc)
 This routine copy a given ordering in a new one. More...
 
pastix_order_tpastixOrderGet (const pastix_data_t *const pastix_data)
 This routine returns the pointer to the internal order structure to access permutation information. More...
 
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. More...
 
int pastixOrderGrid (pastix_order_t **myorder, pastix_int_t nx, pastix_int_t ny, pastix_int_t nz)
 

Order IO subroutines

int pastixOrderLoad (const pastix_data_t *pastix_data, pastix_order_t *ordemesh)
 Load an ordering from a file. More...
 
int pastixOrderSave (pastix_data_t *pastix_data, const pastix_order_t *ordemesh)
 Save an ordering to a file. More...
 

Detailed Description

Functions to generate and manipulate the order structure.

This module provides the set of function to prepare the order structure associated to a given sparse matrix. It is possible to call Scotch, PT-Scotch, Metis and ParMetis to build a new ordering that minimize the fill-in and maximize the level of parallelism.


Data Type Documentation

◆ pastix_order_s

struct pastix_order_s

Order structure.

This structure stores the permutation (and inverse permutation) associated to the ordering. It also stores the partitioning tree and the set of supernodes.

Definition at line 47 of file order.h.

Data Fields
pastix_int_t baseval

base value used for numbering

pastix_int_t vertnbr

Number of vertices

pastix_int_t cblknbr

Number of column blocks

pastix_int_t * permtab

Permutation array of size vertnbr [based]

pastix_int_t * peritab

Inverse permutation array of size vertnbr [based]

pastix_int_t * rangtab

Supernode array of size cblknbr+1 [based,+1]

pastix_int_t * treetab

Partitioning tree of size cblknbr+1 [based]

int8_t * selevtx

Selected vertices for low-rank clustering of size cblknbr

pastix_int_t sndenbr

The number of original supernodes before clustering

pastix_int_t * sndetab

Original supernode array of size sndenbr [based,+1]

pastix_int_t * peritab_exp

Computed field that should not be modified by the user

Typedef Documentation

◆ pastix_order_t

typedef BEGIN_C_DECLS struct pastix_order_s pastix_order_t

Order structure.

This structure stores the permutation (and inverse permutation) associated to the ordering. It also stores the partitioning tree and the set of supernodes.

Function Documentation

◆ pastixOrderInit()

int pastixOrderInit ( pastix_order_t *const  ordeptr,
pastix_int_t  baseval,
pastix_int_t  vertnbr,
pastix_int_t  cblknbr,
pastix_int_t *const  permtab,
pastix_int_t *const  peritab,
pastix_int_t *const  rangtab,
pastix_int_t *const  treetab 
)

Initialize the order structure with the given values.

The base value is set to 0 by default. This is useful to give a personal ordering to the pastix_task_order() function.

Parameters
[in,out]ordeptrThe data structure is set to 0 and then initialize. Need to call orderExit to release the memory first if required to prevent memory leak.
[in]basevalThe base value used in the given arrays. Usually 0 for C, 1 for Fortran. Must be >= 0.
[in]vertnbrThe number of nodes, this is the size of the internal permtab and peritab arrays.
[in]cblknbrThe number of supernodes. The internal rangtab and treetab arrays are of size cblknbr+1.
[in]permtabThe permutation array which must be of size vertnbr, and based on baseval value. If NULL, the permtab field is not initialized.
[in]peritabThe inverse permutation array which must be of size vertnbr, and based on baseval value. If NULL, the peritab field is not initialized.
[in]rangtabThe rangtab array that describes the supernodes in the graph. This array must be of size cblknbr+1, and based on baseval value. If NULL, the rangtab field is not initialized.
[in]treetabThe treetab array that describes the elimination tree connecting the supernodes. This array must be defined as follow:
  • of size cblknbr;
  • based on baseval value;
  • each treetab[i] > i, unless i is a root and treetab[i] == -1
  • all roots of the tree must have -1 as father If NULL, the treetab field is not initialized.
Return values
PASTIX_SUCCESSon successful exit
PASTIX_ERR_BADPARAMETERif one parameter is incorrect.
PASTIX_ERR_OUTOFMEMORYif one allocation failed.

Definition at line 212 of file order.c.

References pastix_order_s::baseval, pastix_order_s::cblknbr, PASTIX_ERR_BADPARAMETER, pastix_int_t, PASTIX_SUCCESS, pastix_order_s::peritab, pastix_order_s::permtab, pastix_order_s::rangtab, pastix_order_s::sndenbr, pastix_order_s::sndetab, pastix_order_s::treetab, and pastix_order_s::vertnbr.

◆ pastixOrderAlloc()

int pastixOrderAlloc ( pastix_order_t *const  ordeptr,
pastix_int_t  vertnbr,
pastix_int_t  cblknbr 
)

Allocate the order structure.

The base value is set to 0 by default.

Parameters
[in,out]ordeptrThe data structure is set to 0 and then initialize. Need to call pastixOrderExit() to release the memory first if required to prevent memory leak.
[in]vertnbrThe number of nodes, this is the size of the internal permtab and peritab arrays. If vertnbr == 0, permtab and peritab are not allocated.
[in]cblknbrThe number of supernodes. The internal rangtab array is of size cblknbr+1, and treetab of size cblknbr. If cblknbr == 0, rangtab and treetab are not allocated.
Return values
PASTIX_SUCCESSon successful exit,
PASTIX_ERR_BADPARAMETERif one parameter is incorrect,
PASTIX_ERR_OUTOFMEMORYif one allocation failed.

Definition at line 55 of file order.c.

References pastix_order_s::cblknbr, PASTIX_ERR_BADPARAMETER, pastix_int_t, PASTIX_SUCCESS, pastix_order_s::peritab, pastix_order_s::permtab, pastix_order_s::rangtab, pastix_order_s::sndenbr, pastix_order_s::sndetab, pastix_order_s::treetab, and pastix_order_s::vertnbr.

Referenced by orderAddIsolate(), orderApplyLevelOrder(), orderComputeMetis(), orderComputePersonal(), orderComputePTScotch(), orderComputeScotch(), ordering_load(), pastix(), pastix_subtask_order(), pastixOrderAllocId(), pastixOrderCopy(), and pastixOrderGrid().

◆ 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.

The base value is set to 0 by default.

Parameters
[in,out]ordeptrThe data structure is set to 0 and then initialize. Need to call pastixOrderExit() to release the memory first if required to prevent memory leak.
[in]vertnbrThe number of nodes, this is the size of the internal permtab and peritab arrays. If vertnbr == 0, permtab and peritab are not allocated.
Return values
PASTIX_SUCCESSon successful exit,
PASTIX_ERR_BADPARAMETERif one parameter is incorrect,
PASTIX_ERR_OUTOFMEMORYif one allocation failed.

Definition at line 123 of file order.c.

References pastix_int_t, PASTIX_SUCCESS, pastixOrderAlloc(), pastix_order_s::peritab, pastix_order_s::permtab, pastix_order_s::rangtab, and pastix_order_s::treetab.

Referenced by orderSupernodes().

◆ pastixOrderExit()

void pastixOrderExit ( pastix_order_t *const  ordeptr)

Free the arrays initialized in the order structure.

Parameters
[in,out]ordeptrThe data structure to clean. All arrays of the structure are freed and the structure is set to 0.

Definition at line 273 of file order.c.

References pastix_order_s::peritab, pastix_order_s::peritab_exp, pastix_order_s::permtab, pastix_order_s::rangtab, pastix_order_s::selevtx, pastix_order_s::sndetab, and pastix_order_s::treetab.

Referenced by orderAddIsolate(), orderApplyLevelOrder(), orderComputePTScotch(), orderComputeScotch(), ordering_load(), orderSupernodes(), pastix(), pastix_subtask_order(), pastixFinalize(), and pastixOrderBcast().

◆ 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.

Parameters
[in,out]ordeptrThe ordering to rebase.
[in]basevalThe base value to be used (needs to be 0 or 1).

Definition at line 322 of file order.c.

References pastix_order_s::baseval, pastix_order_s::cblknbr, pastix_int_t, pastix_order_s::peritab, pastix_order_s::permtab, pastix_order_s::rangtab, pastix_order_s::sndenbr, pastix_order_s::sndetab, pastix_order_s::treetab, and pastix_order_s::vertnbr.

Referenced by orderAmalgamate(), orderComputePersonal(), orderSupernodes(), pastix_subtask_order(), pastix_subtask_symbfact(), and pastixOrderExpand().

◆ pastixOrderCheck()

int pastixOrderCheck ( const pastix_order_t *const  ordeptr)

This routine checks the correctness of the ordering structure.

Parameters
[in]ordeptrThe ordering structure to check.
Return values
PASTIX_SUCCESSon successful exit,
PASTIX_ERR_BADPARAMETERif the ordering structure is incorrect.

Definition at line 39 of file order_check.c.

References pastix_order_s::baseval, pastix_order_s::cblknbr, PASTIX_ERR_BADPARAMETER, pastix_int_t, PASTIX_SUCCESS, pastix_order_s::peritab, pastix_order_s::permtab, pastix_order_s::rangtab, pastix_order_s::treetab, and pastix_order_s::vertnbr.

Referenced by faxCSRAmalgamate(), orderSupernodes(), pastix_subtask_order(), pastix_subtask_symbfact(), and pastixExpand().

◆ pastixOrderExpand()

void pastixOrderExpand ( pastix_order_t ordeptr,
const spmatrix_t *  spm 
)

This routine expand the permutation arrays and the rangtab when the spm is using multiple dof per unknown.

Parameters
[in,out]ordeptrThe ordering to expand. On entry, the order of the compressed matrix/graph. On exit, the ordering is 0-based and contains the permutation for the expanded matrix. peritab_ext remains untouched (=NULL) because peritab will already be expanded.
[in]spmThe sparse matrix structure providing dof information.

Definition at line 396 of file order.c.

References pastix_int_t, pastixOrderBase(), pastix_order_s::peritab, pastix_order_s::permtab, pastix_order_s::rangtab, pastix_order_s::sndetab, and pastix_order_s::vertnbr.

Referenced by pastixExpand().

◆ pastixOrderCopy()

int pastixOrderCopy ( pastix_order_t *const  ordedst,
const pastix_order_t *const  ordesrc 
)

This routine copy a given ordering in a new one.

This function copies an order structure into another one. If all subpointers are NULL, then they are all allocated and conatins the original ordesrc values on exit. If one or more array pointers are not NULL, then, only those are copied to the ordedst structure.

Parameters
[in,out]ordedstThe destination ordering
[in]ordesrcThe source ordering
Return values
PASTIX_SUCCESSon successful exit
PASTIX_ERR_BADPARAMETERif one parameter is incorrect.

Definition at line 570 of file order.c.

References pastix_order_s::baseval, pastix_order_s::cblknbr, PASTIX_ERR_BADPARAMETER, pastix_int_t, PASTIX_SUCCESS, pastixOrderAlloc(), pastix_order_s::peritab, pastix_order_s::permtab, pastix_order_s::rangtab, pastix_order_s::sndenbr, pastix_order_s::sndetab, pastix_order_s::treetab, and pastix_order_s::vertnbr.

Referenced by pastix_subtask_order().

◆ pastixOrderGet()

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.

Warning
The data returned by the routines must not be freed or modified by the user, and are valid as long as no operation on the ordering is performed (pastix_subtask_order(), pastix_subtask_reordering(), or pastixFinalize()).
Parameters
[in]pastix_dataThe pastix_data structure of the problem
Returns
The pointer to the internal ordering structure with permutation information, or NULL if pastix_data is invalid.

Definition at line 649 of file order.c.

References pastix_data_s::ordemesh.

◆ 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.

Parameters
[in,out]ordemeshThe ordering structure of the problem.
[in]rootThe node that will broadcast its ordemesh.
[in]pastix_commThe MPI communicator of the problem.

Definition at line 679 of file order.c.

References pastix_order_s::cblknbr, pastix_int_t, pastixOrderExit(), pastix_order_s::permtab, pastix_order_s::sndenbr, and pastix_order_s::vertnbr.

Referenced by pastix_subtask_order().

◆ pastixOrderGrid()

int pastixOrderGrid ( pastix_order_t **  myorder,
pastix_int_t  nx,
pastix_int_t  ny,
pastix_int_t  nz 
)

orderComputeOptimal - Compute the ordering of a regular 2D or 3D laplacian, with an optimal strategy.

Parameters
[out]myorderPersonal ordering for regular laplacians
[in]nxThe number of vertices for the first dimension of the graph
[in]nyThe number of vertices for the second dimension of the graph
[in]nzThe number of vertices for the third dimension of the graph
Returns
Return values
PASTIX_SUCCESSon successful exit

Definition at line 307 of file order_grids.c.

References pastix_order_s::cblknbr, order_grid3D_classic(), pastix_int_t, PASTIX_SUCCESS, pastixOrderAlloc(), pastix_order_s::peritab, pastix_order_s::permtab, pastix_order_s::rangtab, and pastix_order_s::treetab.

◆ pastixOrderLoad()

int pastixOrderLoad ( const pastix_data_t pastix_data,
pastix_order_t ordemesh 
)

Load an ordering from a file.

The filename is defined by the environment variable PASTIX_FILE_ORDER, and if PASTIX_FILE_ORDER is not defined, the default filename "ordername" in the current directory is used.

Parameters
[in]pastix_dataThe pointer to the solver instance to get options as rank, communicators, ...
[in,out]ordemeshThe initialized ordering structure to fill in.
Return values
PASTIX_SUCCESSon successful exit,
PASTIX_ERR_BADPARAMETERif one parameter is incorrect,
PASTIX_ERR_FILEif a problem occurs during the read.

Definition at line 132 of file order_io.c.

References ordering_load(), PASTIX_ERR_BADPARAMETER, pastix_fopen(), and PASTIX_SUCCESS.

Referenced by orderComputePersonal().

◆ pastixOrderSave()

int pastixOrderSave ( pastix_data_t pastix_data,
const pastix_order_t ordemesh 
)

Save an ordering to a file.

The graph file is store in the directory pastix-XXXXXX uniquely generated per instance, and is named by the PASTIX_FILE_ORDER environment variable, or ordergen by default.

Parameters
[in]pastix_dataThe pointer to the solver instance to get options as rank, communicators, ...
[in]ordemeshThe initialized ordering structure to save.
Return values
PASTIX_SUCCESSon successful exit,
PASTIX_ERR_BADPARAMETERif one parameter is incorrect,
PASTIX_ERR_FILEif a problem occurs during the write.

Definition at line 293 of file order_io.c.

References pastix_data_s::dir_global, ordering_save(), PASTIX_ERR_BADPARAMETER, pastix_fopenw(), pastix_gendirectories(), PASTIX_SUCCESS, and pastix_data_s::procnbr.

Referenced by pastix_subtask_order().

◆ orderGetExpandedPeritab()

pastix_int_t* orderGetExpandedPeritab ( pastix_order_t ordeptr,
const spmatrix_t *  spm 
)

This routine expand the peritab array for multi-dof matrices.

Parameters
[in,out]ordeptrTODO
[in]spmThe sparse matrix structure providing the dof information.
Returns
The expanded peritab array.

Definition at line 494 of file order.c.

References pastix_order_s::baseval, pastix_int_t, pastix_order_s::peritab, pastix_order_s::peritab_exp, and pastix_order_s::vertnbr.

Referenced by bvec_clapmr_shm(), bvec_dlapmr_shm(), bvec_slapmr_shm(), and bvec_zlapmr_shm().

◆ orderAddIsolate()

int orderAddIsolate ( pastix_order_t ordemesh,
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 original graph through graphIsolate() function.

Parameters
[in,out]ordemeshThe ordering generated by the ordering tool.
[in]new_nThe total number of vertices in the combined graph
[in]permArray of size new_n that must be 0-based. The permutation array that isolated the extra vertices at the end of the graph. This permutation will be combined with the one stored in ordemesh to generate a permutation array for the full graph. This permutation must be 0-based.
Return values
PASTIX_SUCCESSon successful exit,
PASTIX_ERR_BADPARAMETERif one parameter is incorrect,
PASTIX_ERR_OUTOFMEMORYif one allocation failed.
See also
graphIsolate

Definition at line 56 of file order_add_isolate.c.

References pastix_order_s::baseval, pastix_order_s::cblknbr, PASTIX_ERR_BADPARAMETER, pastix_int_t, PASTIX_SUCCESS, pastixOrderAlloc(), pastixOrderExit(), pastix_order_s::peritab, pastix_order_s::permtab, pastix_order_s::rangtab, pastix_order_s::treetab, and pastix_order_s::vertnbr.

Referenced by pastix_subtask_order().

◆ orderAmalgamate()

int orderAmalgamate ( int  verbose,
int  ilu,
int  levelk,
int  rat_cblk,
int  rat_blas,
pastix_graph_t *  csc,
pastix_order_t orderptr,
PASTIX_Comm  pastix_comm 
)

Update the order structure with an amalgamation algorithm.

This algorithm almagamates small blocks together in larger ones, and generates an updated order structure. See after for the different parameters.

Parameters
[in]verboseAdjust the level of verbosity of the function
[in]ilu
  • 1: incomplete factorization will be performed.
  • 0: direct factorization will be performed.
[in]levelkUnused if ilu == 0.
  • k >= 0: ordering for ILU(k) factorization will be generated.
  • < 0: ordering for direct factorization will be generated.
[in]rat_cblkMust be >= 0. Fill ratio that limits the amalgamation process based on the graph structure.
[in]rat_blasMust be >= rat_cblk. Fill ratio that limits the amalgamation process that merges blocks in order to reduce the BLAS computational time (see amalgamate() for further informations).
[in,out]cscThe original csc for which the symbol matrix needs to be generated. Rebase to C numbering on exit.
[in,out]orderptrThe oder structure that contains the perm and invp array generated by the ordering step. The supernode partition might be initialized or not. On exit, it is rebased to c numbering and contains the updated perm/invp arrays as well as the supernode partition.
[in]pastix_commThe PaStiX instance communicator.
Return values
PASTIX_SUCCESSon success.
PASTIX_ERR_ALLOCif allocation went wrong.
PASTIX_ERR_BADPARAMETERif incorrect parameters are given.

Definition at line 77 of file order_amalgamate.c.

References pastix_order_s::cblknbr, faxCSRAmalgamate(), faxCSRClean(), faxCSRFactDirect(), faxCSRFactILUk(), faxCSRGenPA(), faxCSRGetNNZ(), graphBase(), PASTIX_ERR_BADPARAMETER, pastix_int_t, PASTIX_SUCCESS, pastixOrderBase(), PastixVerboseYes, and pastix_order_s::permtab.

Referenced by pastix_subtask_order().

◆ orderApplyLevelOrder()

int orderApplyLevelOrder ( pastix_order_t order,
pastix_int_t  level_tasks2d,
pastix_int_t  width_tasks2d 
)

This routine reorder the elimination tree nodes per level.

Parameters
[in]orderThe ordering structure to reorder.
[in]level_tasks2dDefine the ways 2D tasks are decided. If < 0, autolvel will be made based on all blocks above the minimal width_tasks2d criterion. If 0, 1D tasks will be used, and if > 0, only the first level_tasks2d lvel of the elimination tree will be considered as 2D tasks.
[in]width_tasks2dDefine the minimal width for the supernodes that are considered as 2D blocks if level_tasks2d < 0. Unused otherwise.
Return values
PASTIX_SUCCESSon successful exit,
PASTIX_ERR_BADPARAMETERif the ordering structure is incorrect.

Definition at line 95 of file order_apply_level_order.c.

References pastix_order_s::baseval, pastix_order_s::cblknbr, eTreeExit(), eTreeSonI(), etree_node_s::fathnum, etree_node_s::fsonnum, etree_s::nodetab, orderBuildEtree(), PASTIX_ERR_BADPARAMETER, pastix_int_t, PASTIX_SUCCESS, pastixOrderAlloc(), pastixOrderExit(), pastix_order_s::peritab, pastix_order_s::permtab, pastix_order_s::rangtab, etree_node_s::sonsnbr, etree_s::sonstab, pastix_order_s::treetab, and pastix_order_s::vertnbr.

Referenced by pastix_subtask_order().

◆ orderDraw()

void orderDraw ( pastix_data_t pastix_data,
const char *  extname,
pastix_int_t  sndeidx,
int  dump 
)

Dump the last separator into an ivview file.

Parameters
[in,out]pastix_dataThe pastix data structure that holds the graph and the ordering. On exit the output directories may be initialized, if not previously.
[in]extnameFilename extension to specify the .map file if multiple.
[in]sndeidxThe index of the supernode to dump into file.
[in]dumpDefine which information to dump:
  • (0x1 << 0) dumps the graph file
  • (0x1 << 1) dumps the coordinate file
  • (0x1 << 2) dumps the color mapping file

Extract the subgraph with unknowns of the supernode sndeidx

1 is sufficient for the max_distance in most cases, but set to 2 for corner cases that need extra connexions, and to match order_supernode.

Definition at line 52 of file order_draw.c.

References pastix_order_s::baseval, pastix_order_s::cblknbr, pastix_data_s::dir_global, pastix_data_s::graph, graphIsolateRange(), pastix_data_s::ordemesh, pastix_fopenw(), pastix_gendirectories(), pastix_int_t, pastix_order_s::permtab, pastix_order_s::rangtab, pastix_order_s::sndetab, and pastix_order_s::vertnbr.

Referenced by pastix_subtask_order().

◆ orderFindSupernodes()

void orderFindSupernodes ( const pastix_graph_t *  graph,
pastix_order_t *const  ordeptr 
)

Computes the set of supernodes for a given permutation.

The permutation of the matrix given on entry is modified to obtain a postorder of the elimination tree: this does not affect the fill-in properties of the initial ordering.

WARNING: The matrix pattern is assumed to be symmetric.

NOTE: This function can take on entry the lower triangular part or the whole matrix A.

Parameters
[in]graphThe graph associated with the order structuree on which we need to find the supernodes.
[in,out]ordeptrPointer to a pastix_order_t structure, that will be further initialized by the routine.

On entry:

  • orderptr->permtab: the original permutation vector for the elimination tree.
  • orderptr->permtab: the original inverse permutation vector for the elimination tree.

On exit:

  • orderptr->cblknbr: The number of supernodes found.
  • orderptr->rangtab: Contains the first element of each supernode. rangtab[i] is the first element of the ith supernode.
  • orderptr->permtab: the permutation vector for the postorder of the nodes in the elimination tree.
  • orderptr->permtab: the inverse permutation vector for the postorder of the nodes in the elimination tree.
  • orderptr->treetab: treetab[i] is the number of the father of supernode i in the supernodal elimination tree.

Definition at line 360 of file order_find_supernodes.c.

References pastix_order_s::cblknbr, compute_elimination_tree(), compute_post_order(), compute_subtree_size(), pastix_int_t, pastix_order_s::peritab, pastix_order_s::permtab, pastix_order_s::rangtab, and pastix_order_s::treetab.

Referenced by pastix_subtask_order().

◆ orderComputeMetis()

int orderComputeMetis ( pastix_data_t pastix_data,
pastix_graph_t *  graph 
)

Compute the ordering of the graph given as parameter with Metis library.

This routine is affected by the following parameters: IPARM_VERBOSE, IPARM_ORDERING_DEFAULT, IPARM_METIS_CTYPE, IPARM_METIS_RTYPE, IPARM_METIS_NO2HOP, IPARM_METIS_NSEPS, IPARM_METIS_NITER, IPARM_METIS_UFACTOR, IPARM_METIS_COMPRESS, IPARM_METIS_CCORDER, IPARM_METIS_PFACTOR, IPARM_METIS_SEED, IPARM_METIS_DBGLVL.

Parameters
[in,out]pastix_dataThe pastix_data structure that describes the solver instance. On exit, the field oerdemesh is initialize with the result of the ordering realized by Scotch.
[in,out]graphThe graph prepared by graphPrepare function on which we want to perform the ordering. On exit, the graph might be rebased.
Return values
PASTIX_SUCCESSon successful exit,
PASTIX_ERR_BADPARAMETERif one parameter is incorrect,
PASTIX_ERR_OUTOFMEMORYif one allocation failed,
PASTIX_ERR_INTEGER_TYPEif Metis integer type is not the same size as PaStiX ones,
PASTIX_ERR_INTERNALif an error occurs internally to Metis.

Definition at line 60 of file order_compute_metis.c.

References pastix_order_s::baseval, pastix_data_s::iparm, IPARM_METIS_CCORDER, IPARM_METIS_COMPRESS, IPARM_METIS_CTYPE, IPARM_METIS_DBGLVL, IPARM_METIS_NITER, IPARM_METIS_NO2HOP, IPARM_METIS_NSEPS, IPARM_METIS_PFACTOR, IPARM_METIS_RTYPE, IPARM_METIS_SEED, IPARM_METIS_UFACTOR, IPARM_ORDERING_DEFAULT, pastix_data_s::ordemesh, PASTIX_ERR_INTEGER_TYPE, PASTIX_ERR_INTERNAL, pastix_int_t, PASTIX_SUCCESS, pastixOrderAlloc(), pastix_order_s::peritab, and pastix_order_s::permtab.

Referenced by pastix_subtask_order().

◆ ocpts_graph_check()

static void ocpts_graph_check ( const SCOTCH_Dgraph *  graph,
int  procnum 
)
inlinestatic

Check the PT-Scotch distributed graph.

Parameters
[in]graphPointer to the SCOTCH_Dgraph structure.
[in]procnumProcnum of the process. Output purpose.

Definition at line 42 of file order_compute_ptscotch.c.

Referenced by ocpts_graph_init().

◆ ocpts_graph_init()

static void ocpts_graph_init ( SCOTCH_Dgraph *  scotchgraph,
pastix_graph_t *  graph,
PASTIX_Comm  comm 
)
inlinestatic

Build the PT-Scotch distributed graph.

Parameters
[in,out]scotchgraphThe SCOTCH_Dgraph structure that will be build.
[in,out]graphThe graph prepared by graphPrepare function on which we want to perform the ordering.
[in]commPaStiX communicator.

Definition at line 80 of file order_compute_ptscotch.c.

References graphBase(), graphGetWeights(), ocpts_graph_check(), and pastix_int_t.

Referenced by orderComputePTScotch().

◆ ocpts_graph_exit()

static void ocpts_graph_exit ( SCOTCH_Dgraph *  scotchgraph,
PASTIX_Comm  comm 
)
inlinestatic

Cleanup the PT-Scotch graph structure and free the associated data.

Parameters
[in,out]scotchgraphThe SCOTCH_Dgraph structure that will be clean.
[in,out]commThe PaStiX communicator.

Definition at line 148 of file order_compute_ptscotch.c.

References pastix_int_t.

Referenced by orderComputePTScotch().

◆ ocpts_compute_graph_ordering()

static int ocpts_compute_graph_ordering ( pastix_data_t pastix_data,
SCOTCH_Dgraph *  scotchgraph 
)
inlinestatic

Compute the graph ordering.

Parameters
[in,out]pastix_dataPointer to the pastix_data instance.
[in,out]scotchgraphThe SCOTCH_Dgraph structure that will be ordered.
Return values
Thereturn value of SCOTCH_graphDOrderList.

Definition at line 204 of file order_compute_ptscotch.c.

References pastix_order_s::cblknbr, pastix_data_s::ordemesh, pastix_order_s::peritab, pastix_order_s::permtab, pastix_data_s::procnum, pastix_order_s::rangtab, and pastix_order_s::treetab.

Referenced by orderComputePTScotch().

◆ orderComputePTScotch()

int orderComputePTScotch ( pastix_data_t pastix_data,
pastix_graph_t *  graph 
)

Compute the ordering of the graph given as parameter with PT-Scotch library.

This routine is affected by the following parameters: IPARM_VERBOSE, IPARM_ORDERING_DEFAULT, IPARM_SCOTCH_SWITCH_LEVEL, IPARM_SCOTCH_CMIN, IPARM_SCOTCH_CMAX, IPARM_SCOTCH_FRAT

Parameters
[in,out]pastix_dataThe pastix_data structure that describes the solver instance. On exit, the field ordemesh is initialized with the result of the ordering realized by PT-Scotch.
[in,out]graphThe graph prepared by graphPrepare function on which we want to perform the ordering. On exit, the graph might be rebased.
Return values
PASTIX_SUCCESSon successful exit,
PASTIX_ERR_BADPARAMETERif one parameter is incorrect,
PASTIX_ERR_OUTOFMEMORYif one allocation failed,
PASTIX_ERR_INTEGER_TYPEif Scotch integer type is not the same size as PaStiX ones,
PASTIX_ERR_INTERNALif an error occurs internally to Scotch.

Definition at line 304 of file order_compute_ptscotch.c.

References graphBase(), pastix_data_s::id, ocpts_compute_graph_ordering(), ocpts_graph_exit(), ocpts_graph_init(), pastix_data_s::ordemesh, order_scotch_reallocate_ordemesh(), pastix_data_s::pastix_comm, PASTIX_ERR_INTEGER_TYPE, PASTIX_ERR_INTERNAL, pastix_int_t, PASTIX_SUCCESS, pastixOrderAlloc(), and pastixOrderExit().

Referenced by pastix_subtask_order().

◆ ocs_graph_check()

static void ocs_graph_check ( const SCOTCH_Graph *  graph,
int  procnum 
)
inlinestatic

Check the generated Scotch graph.

Parameters
[in]graphPointer to the SCOTCH_Graph structure.
[in]procnumProcnum of the process. Output purpose.

Definition at line 45 of file order_compute_scotch.c.

Referenced by ocs_graph_init().

◆ ocs_graph_init()

static void ocs_graph_init ( SCOTCH_Graph *  scotchgraph,
pastix_graph_t *  graph 
)
inlinestatic

Build the Scotch graph.

Parameters
[in,out]scotchgraphThe SCOTCH_Graph structure that will be build.
[in,out]graphThe graph prepared by graphPrepare function on which we want to perform the ordering.

Definition at line 80 of file order_compute_scotch.c.

References graphBase(), graphGetWeights(), ocs_graph_check(), and pastix_int_t.

Referenced by orderComputeScotch().

◆ ocs_graph_exit()

static void ocs_graph_exit ( SCOTCH_Graph *  scotchgraph)
inlinestatic

Cleanup the Scotch graph structure and free the associated data.

Parameters
[in,out]scotchgraphThe Scotch graph structure that will be cleaned.

Definition at line 141 of file order_compute_scotch.c.

References pastix_int_t.

Referenced by orderComputeScotch().

◆ ocs_compute_graph_ordering()

static int ocs_compute_graph_ordering ( pastix_data_t pastix_data,
SCOTCH_Graph *  scotchgraph 
)
inlinestatic

Compute the graph ordering.

Parameters
[in,out]pastix_dataPointer to the pastix_data instance.
[in,out]scotchgraphThe SCOTCH_Graph structure that will be ordered.
Return values
Thereturn value of SCOTCH_graphOrderList.

Definition at line 190 of file order_compute_scotch.c.

References pastix_order_s::cblknbr, pastix_data_s::iparm, pastix_data_s::ordemesh, order_scotch_build_strategy(), pastix_order_s::peritab, pastix_order_s::permtab, pastix_data_s::procnum, pastix_order_s::rangtab, pastix_order_s::treetab, and pastix_order_s::vertnbr.

Referenced by orderComputeScotch().

◆ orderComputeScotch()

int orderComputeScotch ( pastix_data_t pastix_data,
pastix_graph_t *  graph 
)

Compute the ordering of the graph given as parameter with Scotch library.

This routine is affected by the following parameters: IPARM_VERBOSE, IPARM_ORDERING_DEFAULT, IPARM_SCOTCH_SWITCH_LEVEL, IPARM_SCOTCH_CMIN, IPARM_SCOTCH_CMAX, IPARM_SCOTCH_FRAT If PASTIX_ORDERING_SCOTCH_MT is enabled, we will compute the ordering in shared memory

Parameters
[in,out]pastix_dataThe pastix_data structure that describes the solver instance. On exit, the field ordemesh is initialized with the result of the ordering realized by Scotch.
[in,out]graphThe graph prepared by graphPrepare function on which we want to perform the ordering. On exit, the graph might be rebased.
Return values
PASTIX_SUCCESSon successful exit,
PASTIX_ERR_BADPARAMETERif one parameter is incorrect,
PASTIX_ERR_OUTOFMEMORYif one allocation failed,
PASTIX_ERR_INTEGER_TYPEif Scotch integer type is not the same size as PaStiX ones,
PASTIX_ERR_INTERNALif an error occurs internally to Scotch.

Definition at line 345 of file order_compute_scotch.c.

References pastix_data_s::id, pastix_data_s::iparm, IPARM_SCOTCH_MT, pastix_data_s::isched, ocs_compute_graph_ordering(), ocs_graph_exit(), ocs_graph_init(), pastix_data_s::ordemesh, order_scotch_reallocate_ordemesh(), PASTIX_ERR_INTEGER_TYPE, PASTIX_ERR_INTERNAL, pastix_int_t, PASTIX_SUCCESS, pastixOrderAlloc(), and pastixOrderExit().

Referenced by pastix_subtask_order().

◆ orderComputePersonal()

int orderComputePersonal ( pastix_data_t pastix_data,
pastix_graph_t *  graph,
pastix_order_t myorder 
)

Computes the personal ordering of the PaStiX instance.

Parameters
[in,out]pastix_dataThe pastix_data structure that describes the solver instance. On exit, the field ordemesh is initialized with the identity ordering if myorder is NULL, or with the provided ordering otherwise.
[in,out]graphThe graph prepared by graphPrepare function on which we want to perform the ordering. On exit, the graph might be rebased.
[in,out]myorderOn entry, the permutation provided by the user or NULL to get the identity ordering. On exit, if the permutation is not NULL, it contains the generated ordering permutation. Otherwise, it is not referenced.
Return values
PASTIX_SUCCESSon successful exit,
PASTIX_ERR_BADPARAMETERif one parameter is incorrect,
PASTIX_ERR_FILEif a problem occurs during the read in pastixOrderLoad

Definition at line 56 of file order_compute_personal.c.

References pastix_order_s::cblknbr, pastix_data_s::iparm, IPARM_IO_STRATEGY, IPARM_VERBOSE, pastix_data_s::ordemesh, pastix_int_t, PASTIX_SUCCESS, PastixIOLoad, pastixOrderAlloc(), pastixOrderBase(), pastixOrderLoad(), PastixVerboseNot, pastix_order_s::peritab, pastix_order_s::permtab, pastix_data_s::procnum, pastix_order_s::rangtab, pastix_order_s::treetab, and pastix_order_s::vertnbr.

Referenced by pastix_subtask_order().

◆ order_scotch_build_strategy()

char* order_scotch_build_strategy ( const pastix_int_t iparm,
pastix_int_t  procnum,
int  isPTscotch 
)

Generate the ordering strategy string based on the input parameters.

Parameters
[in]iparmPointer to the iparm array.
[in]procnumProcnum of the process. Output purpose.
[in]isPTscotchBoolean that indicates if we use Scotch or PT-Scotch for the order step.
Return values
Thestrategy string of the order step.

Definition at line 61 of file order_scotch_common.c.

References IPARM_INCOMPLETE, IPARM_ORDERING_DEFAULT, IPARM_SCOTCH_CMAX, IPARM_SCOTCH_CMIN, IPARM_SCOTCH_FRAT, IPARM_SCOTCH_SWITCH_LEVEL, IPARM_VERBOSE, and PastixVerboseNo.

Referenced by ocs_compute_graph_ordering().

◆ order_scotch_reallocate_ordemesh()

void order_scotch_reallocate_ordemesh ( pastix_order_t ordemesh)

Reallocate the ordering structure.

If we decide to drop the Scotch partition to recompute it later, then partition information is freed, otherwise its memory space is compressed.

Parameters
[in,out]ordemeshPointer to the ordemesh structure to reallocate.

Adapt size of rangtab and treetab to the new cblknbr WARNING: If no nodes in the graph, nothing has been initialized.

Definition at line 125 of file order_scotch_common.c.

References pastix_order_s::baseval, pastix_order_s::cblknbr, pastix_int_t, pastix_order_s::rangtab, and pastix_order_s::treetab.

Referenced by orderComputePTScotch(), and orderComputeScotch().

◆ orderSupernodes()

pastix_int_t orderSupernodes ( const pastix_graph_t *  graph,
pastix_order_t order,
EliminTree etree,
pastix_int_t iparm,
int  do_schur 
)

Order the supernodes with one of the clustering strategies.

Parameters
[in]graphThe graph that represents the sparse matrix.
[in,out]orderThe graph that represents the sparse matrix. On exit, this ordering is updated with the refined partition obtained thanks to one of the clustering strategies.
[in,out]etreeThe elimination tree. On exit it can be modified by eTreeComputeLevels().
[in]iparmThe integer array of parameters.
[in]do_schurIf do_schur is not zero, the last cblk represents the schur. Thus, neither k-way nor projection applied on it. If do_schur is zero, both k-way and projection can be performed everywhere.
Return values
PASTIX_SUCCESSon successful exit,
PASTIX_ERR_BADPARAMETERif one parameter is incorrect,

Extract the subgraph with unknowns of the supernode sn_id

1 is sufficient for the max_distance in most cases, but set to 2 for corner cases that need extra connexions.

Compute sets of preselected unknowns based on projections

Definition at line 59 of file order_supernodes.c.

References pastix_order_s::cblknbr, eTreeComputeLevels(), eTreeGetLevelMinIdx(), eTreeRoot(), extendint_Add(), extendint_Clear(), extendint_Exit(), extendint_Init(), extendint_Read(), extendint_Size(), graphComputeKway(), graphComputeProjection(), graphExit(), graphIsolateConnectedComponents(), graphIsolateRange(), IPARM_COMPRESS_MIN_WIDTH, IPARM_MAX_BLOCKSIZE, IPARM_MIN_BLOCKSIZE, IPARM_SPLITTING_LEVELS_KWAY, IPARM_SPLITTING_LEVELS_PROJECTIONS, IPARM_SPLITTING_PROJECTIONS_DEPTH, IPARM_SPLITTING_PROJECTIONS_DISTANCE, IPARM_SPLITTING_PROJECTIONS_WIDTH, IPARM_SPLITTING_STRATEGY, IPARM_VERBOSE, etree_node_s::ndlevel, etree_s::nodetab, PASTIX_ERR_BADPARAMETER, pastix_int_t, PASTIX_SUCCESS, pastixOrderAllocId(), pastixOrderBase(), pastixOrderCheck(), pastixOrderExit(), PastixSplitKway, PastixSplitKwayProjections, PastixSplitNot, pastix_order_s::peritab, pastix_order_s::permtab, pqueueExit(), pqueueInit(), pqueuePop(), pqueuePush1(), pqueueSize(), pastix_order_s::rangtab, pastix_order_s::selevtx, etree_node_s::sonsnbr, pastix_order_s::treetab, and pastix_order_s::vertnbr.

Referenced by pastix_subtask_order().