PaStiX Handbook  6.2.1
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 struct etree_s EliminTree
 
typedef struct pastix_order_s pastix_order_t
 Order structure. More...
 

Functions

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...
 
static pastix_int_t * ocs_build_weights (const pastix_graph_t *graph)
 Build the vertex weight array out of the dof array. More...
 
static void ocs_graphcheck (const SCOTCH_Graph *graph, pastix_int_t procnum)
 Check the generated Scotch graph. More...
 
static void ocs_scotchgraph_init (SCOTCH_Graph *scotchgraph, pastix_graph_t *graph)
 Build the Scotch graph. More...
 
static void ocs_scotchgraph_exit (SCOTCH_Graph *scotchgraph, pastix_int_t baseval)
 Cleanup the Scotch graph structure and free the associated data. More...
 
static void ocs_build_strategy (char *strat, const pastix_int_t *iparm, pastix_int_t procnum)
 Generate the ordering strategy string based on the input parameters. More...
 
static void ocs_reallocate_ordemesh (pastix_order_t *ordemesh)
 Reallocate the ordering structure. More...
 
static int ocs_compute_graph_ordering (pastix_data_t *pastix_data, SCOTCH_Graph *scotchgraph)
 Compute the graph ordering. 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 *const ordeptr, spmatrix_t *const 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...
 
const 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...
 

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

Order compute subroutines

int pastixOrderComputeScotch (pastix_data_t *pastix_data, pastix_graph_t *graph)
 Compute the ordering of the graph given as parameter with Scotch library. More...
 
int pastixOrderComputePTScotch (pastix_data_t *pastix_data, pastix_graph_t *graph)
 Compute the ordering of the graph given as parameter with PT-Scotch library. More...
 
int pastixOrderComputeMetis (pastix_data_t *pastix_data, pastix_graph_t *graph)
 Compute the ordering of the graph given as parameter with Metis library. More...
 
int pastixOrderComputeParMetis (pastix_data_t *pastix_data, pastix_graph_t *graph)
 
int pastixOrderGrid (pastix_order_t **myorder, pastix_int_t nx, pastix_int_t ny, pastix_int_t nz)
 

Order manipulation subroutines

void pastixOrderFindSupernodes (const pastix_graph_t *graph, pastix_order_t *const ordeptr)
 Computes the set of supernodes for a given permutation. More...
 
int pastixOrderAmalgamate (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 pastixOrderApplyLevelOrder (pastix_order_t *order, pastix_int_t level_tasks2d, pastix_int_t width_tasks2d)
 This routine reorder the elimination tree nodes per level. More...
 
int pastixOrderAddIsolate (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...
 

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 45 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]

Typedef Documentation

◆ 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_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 pastixOrderComputePTScotch().

◆ 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_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 ordering_load(), pastix(), pastixOrderAddIsolate(), pastixOrderAllocId(), pastixOrderApplyLevelOrder(), pastixOrderComputeMetis(), pastixOrderComputeScotch(), 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_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::permtab, pastix_order_s::rangtab, pastix_order_s::selevtx, pastix_order_s::sndetab, and pastix_order_s::treetab.

Referenced by ordering_load(), pastix(), pastixFinalize(), pastixOrderAddIsolate(), pastixOrderApplyLevelOrder(), pastixOrderBcast(), and pastixOrderComputeScotch().

◆ 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 319 of file order.c.

References pastix_order_s::baseval, pastix_order_s::cblknbr, 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 orderSupernodes(), pastixOrderAmalgamate(), pastixOrderComputePTScotch(), 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_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(), and pastix_subtask_reordering().

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

Parameters
[in,out]ordeptrThe ordering to expand. On entry, the order of the compressed unknown. On exit, the ordering is 0-based and contains the permutation for the expanded matrix.
[in,out]spmThe sparse matrix structure providing dof information. On exit, the spm is rebased to 0, if it is not the case on entry.

Definition at line 393 of file order.c.

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

◆ 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 496 of file order.c.

References pastix_order_s::baseval, pastix_order_s::cblknbr, PASTIX_ERR_BADPARAMETER, 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.

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

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 575 of file order.c.

◆ 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]commThe MPI communicator of the problem.

Definition at line 605 of file order.c.

References pastix_order_s::cblknbr, pastixOrderExit(), pastix_order_s::peritab, pastix_order_s::permtab, pastix_order_s::rangtab, pastix_order_s::selevtx, pastix_order_s::sndenbr, pastix_order_s::sndetab, pastix_order_s::treetab, and pastix_order_s::vertnbr.

◆ 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_ERR_INTERNAL, pastix_fopen(), and PASTIX_SUCCESS.

◆ 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 294 of file order_io.c.

References ordering_save(), PASTIX_ERR_BADPARAMETER, pastix_fopenw(), pastix_gendirectories(), and PASTIX_SUCCESS.

Referenced by pastix_subtask_reordering().

◆ pastixOrderComputeScotch()

int pastixOrderComputeScotch ( 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 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 Scotch integer type is not the same size as PaStiX ones,
PASTIX_ERR_INTERNALif an error occurs internally to Scotch.

Definition at line 537 of file order_compute_scotch.c.

References IPARM_SCOTCH_MT, ocs_compute_graph_ordering(), ocs_reallocate_ordemesh(), ocs_scotchgraph_exit(), ocs_scotchgraph_init(), PASTIX_ERR_INTEGER_TYPE, PASTIX_ERR_INTERNAL, PASTIX_SUCCESS, pastixOrderAlloc(), and pastixOrderExit().

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

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 oerdemesh is initialize with the result of the ordering realized by Scotch.
[in,out]graphThe graph prepared by graphPrepare function on which wwe 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 60 of file order_compute_ptscotch.c.

References pastix_order_s::baseval, pastix_order_s::cblknbr, IPARM_INCOMPLETE, IPARM_ORDERING_DEFAULT, IPARM_SCOTCH_CMAX, IPARM_SCOTCH_CMIN, IPARM_SCOTCH_FRAT, IPARM_SCOTCH_SWITCH_LEVEL, IPARM_VERBOSE, PASTIX_ERR_INTEGER_TYPE, PASTIX_SUCCESS, pastixOrderBase(), pastixOrderInit(), PastixVerboseNo, PastixVerboseNot, PastixVerboseYes, pastix_order_s::peritab, pastix_order_s::permtab, and pastix_order_s::rangtab.

◆ pastixOrderComputeMetis()

int pastixOrderComputeMetis ( 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 wwe 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, 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_ERR_INTEGER_TYPE, PASTIX_ERR_INTERNAL, PASTIX_SUCCESS, pastixOrderAlloc(), pastix_order_s::peritab, and pastix_order_s::permtab.

◆ 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_SUCCESS, pastixOrderAlloc(), pastix_order_s::peritab, pastix_order_s::permtab, pastix_order_s::rangtab, and pastix_order_s::treetab.

◆ pastixOrderFindSupernodes()

void pastixOrderFindSupernodes ( 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_order_s::peritab, pastix_order_s::permtab, pastix_order_s::rangtab, and pastix_order_s::treetab.

◆ pastixOrderAmalgamate()

int pastixOrderAmalgamate ( 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]symbmtxThe symbol matrix structure to construct. On entry, the initialized structure (see pastixSymbolInit()). On exit, the symbol matrix generated after the amalgamation process.
[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 82 of file order_amalgamate.c.

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

◆ pastixOrderApplyLevelOrder()

int pastixOrderApplyLevelOrder ( 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, PASTIX_ERR_BADPARAMETER, PASTIX_SUCCESS, pastixOrderAlloc(), pastixOrderBuildEtree(), 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.

◆ pastixOrderAddIsolate()

int pastixOrderAddIsolate ( 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_SUCCESS, pastixOrderAlloc(), pastixOrderExit(), pastix_order_s::peritab, pastix_order_s::permtab, pastix_order_s::rangtab, pastix_order_s::treetab, and pastix_order_s::vertnbr.

◆ 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 50 of file order_draw.c.

References pastix_order_s::baseval, pastix_order_s::cblknbr, graphIsolateRange(), pastix_fopenw(), pastix_gendirectories(), pastix_order_s::permtab, pastix_order_s::rangtab, pastix_order_s::sndetab, and pastix_order_s::vertnbr.

◆ ocs_build_weights()

static pastix_int_t* ocs_build_weights ( const pastix_graph_t *  graph)
inlinestatic

Build the vertex weight array out of the dof array.

Parameters
[in]graphPointer to the graph structure.
Return values
Thevertex weight array if graph->dof != 1, NULL otherwise.

Definition at line 49 of file order_compute_scotch.c.

Referenced by ocs_scotchgraph_init().

◆ ocs_graphcheck()

static void ocs_graphcheck ( const SCOTCH_Graph *  graph,
pastix_int_t  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 97 of file order_compute_scotch.c.

Referenced by ocs_scotchgraph_init().

◆ ocs_scotchgraph_init()

static void ocs_scotchgraph_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 133 of file order_compute_scotch.c.

References ocs_build_weights(), ocs_graphcheck(), and PASTIX_ERR_INTERNAL.

Referenced by pastixOrderComputeScotch().

◆ ocs_scotchgraph_exit()

static void ocs_scotchgraph_exit ( SCOTCH_Graph *  scotchgraph,
pastix_int_t  baseval 
)
inlinestatic

Cleanup the Scotch graph structure and free the associated data.

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

Definition at line 214 of file order_compute_scotch.c.

Referenced by pastixOrderComputeScotch().

◆ ocs_build_strategy()

static void ocs_build_strategy ( char *  strat,
const pastix_int_t *  iparm,
pastix_int_t  procnum 
)
inlinestatic

Generate the ordering strategy string based on the input parameters.

Parameters
[in,out]stratThe preallocated ordering strategy string to initialize.
[in]iparmPointer to the iparm array.
[in]procnumProcnum of the process. Output purpose.

Definition at line 276 of file order_compute_scotch.c.

References IPARM_INCOMPLETE, IPARM_ORDERING_DEFAULT, IPARM_VERBOSE, and PastixVerboseNo.

◆ ocs_reallocate_ordemesh()

static void ocs_reallocate_ordemesh ( pastix_order_t ordemesh)
inlinestatic

Reallocate the ordering structure.

If we decide to drop the Scothc 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 339 of file order_compute_scotch.c.

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

Referenced by pastixOrderComputeScotch().

◆ 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 387 of file order_compute_scotch.c.

Referenced by pastixOrderComputeScotch().

◆ 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_Clear(), extendint_Init(), graphIsolateRange(), IPARM_MAX_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_SUCCESS, pastixOrderAllocId(), pastixOrderBase(), PastixSplitKwayProjections, PastixSplitNot, pastix_order_s::peritab, pastix_order_s::permtab, pastix_order_s::rangtab, etree_node_s::sonsnbr, pastix_order_s::treetab, and pastix_order_s::vertnbr.