PaStiX Handbook: 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_t *	orderGetExpandedPeritab (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_t *	pastixOrderGet (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]	ordeptr	The 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]	baseval	The base value used in the given arrays. Usually 0 for C, 1 for Fortran. Must be >= 0.
[in]	vertnbr	The number of nodes, this is the size of the internal permtab and peritab arrays.
[in]	cblknbr	The number of supernodes. The internal rangtab and treetab arrays are of size cblknbr+1.
[in]	permtab	The permutation array which must be of size vertnbr, and based on baseval value. If NULL, the permtab field is not initialized.
[in]	peritab	The inverse permutation array which must be of size vertnbr, and based on baseval value. If NULL, the peritab field is not initialized.
[in]	rangtab	The 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]	treetab	The 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_SUCCESS	on successful exit
PASTIX_ERR_BADPARAMETER	if one parameter is incorrect.
PASTIX_ERR_OUTOFMEMORY	if 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]	ordeptr	The 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]	vertnbr	The number of nodes, this is the size of the internal permtab and peritab arrays. If vertnbr == 0, permtab and peritab are not allocated.
[in]	cblknbr	The 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_SUCCESS	on successful exit,
PASTIX_ERR_BADPARAMETER	if one parameter is incorrect,
PASTIX_ERR_OUTOFMEMORY	if 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]	ordeptr	The 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]	vertnbr	The 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_SUCCESS	on successful exit,
PASTIX_ERR_BADPARAMETER	if one parameter is incorrect,
PASTIX_ERR_OUTOFMEMORY	if 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] ordeptr The 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]	ordeptr	The ordering to rebase.
[in]	baseval	The 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] ordeptr The ordering structure to check.

Return values

PASTIX_SUCCESS	on successful exit,
PASTIX_ERR_BADPARAMETER	if the ordering structure is incorrect.

Definition at line 39 of file order_check.c.

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]	ordeptr	The 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]	spm	The 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]	ordedst	The destination ordering
[in]	ordesrc	The source ordering

Return values

PASTIX_SUCCESS	on successful exit
PASTIX_ERR_BADPARAMETER	if 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_data The 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]	ordemesh	The ordering structure of the problem.
[in]	root	The node that will broadcast its ordemesh.
[in]	pastix_comm	The 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]	myorder	Personal ordering for regular laplacians
[in]	nx	The number of vertices for the first dimension of the graph
[in]	ny	The number of vertices for the second dimension of the graph
[in]	nz	The number of vertices for the third dimension of the graph

Returns

Return values

PASTIX_SUCCESS on 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_data	The pointer to the solver instance to get options as rank, communicators, ...
[in,out]	ordemesh	The initialized ordering structure to fill in.

Return values

PASTIX_SUCCESS	on successful exit,
PASTIX_ERR_BADPARAMETER	if one parameter is incorrect,
PASTIX_ERR_FILE	if 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_data	The pointer to the solver instance to get options as rank, communicators, ...
[in]	ordemesh	The initialized ordering structure to save.

Return values

PASTIX_SUCCESS	on successful exit,
PASTIX_ERR_BADPARAMETER	if one parameter is incorrect,
PASTIX_ERR_FILE	if 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]	ordeptr	TODO
[in]	spm	The 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]	ordemesh	The ordering generated by the ordering tool.
[in]	new_n	The total number of vertices in the combined graph
[in]	perm	Array 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_SUCCESS	on successful exit,
PASTIX_ERR_BADPARAMETER	if one parameter is incorrect,
PASTIX_ERR_OUTOFMEMORY	if 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]	verbose	Adjust the level of verbosity of the function
[in]	ilu	1: incomplete factorization will be performed. 0: direct factorization will be performed.
[in]	levelk	Unused if ilu == 0. k >= 0: ordering for ILU(k) factorization will be generated. < 0: ordering for direct factorization will be generated.
[in]	rat_cblk	Must be >= 0. Fill ratio that limits the amalgamation process based on the graph structure.
[in]	rat_blas	Must 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]	csc	The original csc for which the symbol matrix needs to be generated. Rebase to C numbering on exit.
[in,out]	orderptr	The 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_comm	The PaStiX instance communicator.

Return values

PASTIX_SUCCESS	on success.
PASTIX_ERR_ALLOC	if allocation went wrong.
PASTIX_ERR_BADPARAMETER	if 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]	order	The ordering structure to reorder.
[in]	level_tasks2d	Define 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_tasks2d	Define the minimal width for the supernodes that are considered as 2D blocks if level_tasks2d < 0. Unused otherwise.

Return values

PASTIX_SUCCESS	on successful exit,
PASTIX_ERR_BADPARAMETER	if 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_data	The pastix data structure that holds the graph and the ordering. On exit the output directories may be initialized, if not previously.
[in]	extname	Filename extension to specify the .map file if multiple.
[in]	sndeidx	The index of the supernode to dump into file.
[in]	dump	Define 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]	graph	The graph associated with the order structuree on which we need to find the supernodes.
[in,out]	ordeptr	Pointer 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_data	The 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]	graph	The graph prepared by graphPrepare function on which we want to perform the ordering. On exit, the graph might be rebased.

Return values

PASTIX_SUCCESS	on successful exit,
PASTIX_ERR_BADPARAMETER	if one parameter is incorrect,
PASTIX_ERR_OUTOFMEMORY	if one allocation failed,
PASTIX_ERR_INTEGER_TYPE	if Metis integer type is not the same size as PaStiX ones,
PASTIX_ERR_INTERNAL	if 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]	graph	Pointer to the SCOTCH_Dgraph structure.
[in]	procnum	Procnum 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]	scotchgraph	The SCOTCH_Dgraph structure that will be build.
[in,out]	graph	The graph prepared by graphPrepare function on which we want to perform the ordering.
[in]	comm	PaStiX 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]	scotchgraph	The SCOTCH_Dgraph structure that will be clean.
[in,out]	comm	The 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_data	Pointer to the pastix_data instance.
[in,out]	scotchgraph	The SCOTCH_Dgraph structure that will be ordered.

Return values

The	return 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_data	The 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]	graph	The graph prepared by graphPrepare function on which we want to perform the ordering. On exit, the graph might be rebased.

Return values

PASTIX_SUCCESS	on successful exit,
PASTIX_ERR_BADPARAMETER	if one parameter is incorrect,
PASTIX_ERR_OUTOFMEMORY	if one allocation failed,
PASTIX_ERR_INTEGER_TYPE	if Scotch integer type is not the same size as PaStiX ones,
PASTIX_ERR_INTERNAL	if 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]	graph	Pointer to the SCOTCH_Graph structure.
[in]	procnum	Procnum 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]	scotchgraph	The SCOTCH_Graph structure that will be build.
[in,out]	graph	The 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] scotchgraph The 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_data	Pointer to the pastix_data instance.
[in,out]	scotchgraph	The SCOTCH_Graph structure that will be ordered.

Return values

The	return 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_data	The 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]	graph	The graph prepared by graphPrepare function on which we want to perform the ordering. On exit, the graph might be rebased.

Return values

PASTIX_SUCCESS	on successful exit,
PASTIX_ERR_BADPARAMETER	if one parameter is incorrect,
PASTIX_ERR_OUTOFMEMORY	if one allocation failed,
PASTIX_ERR_INTEGER_TYPE	if Scotch integer type is not the same size as PaStiX ones,
PASTIX_ERR_INTERNAL	if 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_data	The 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]	graph	The graph prepared by graphPrepare function on which we want to perform the ordering. On exit, the graph might be rebased.
[in,out]	myorder	On 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_SUCCESS	on successful exit,
PASTIX_ERR_BADPARAMETER	if one parameter is incorrect,
PASTIX_ERR_FILE	if 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]	iparm	Pointer to the iparm array.
[in]	procnum	Procnum of the process. Output purpose.
[in]	isPTscotch	Boolean that indicates if we use Scotch or PT-Scotch for the order step.

Return values

The	strategy 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] ordemesh Pointer 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]	graph	The graph that represents the sparse matrix.
[in,out]	order	The 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]	etree	The elimination tree. On exit it can be modified by eTreeComputeLevels().
[in]	iparm	The integer array of parameters.
[in]	do_schur	If 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_SUCCESS	on successful exit,
PASTIX_ERR_BADPARAMETER	if 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().

Modules

Data Structures

Typedefs

Functions

Order basic subroutines

Order IO subroutines

Detailed Description

Data Type Documentation

◆ pastix_order_s

Typedef Documentation

◆ pastix_order_t

Function Documentation

◆ pastixOrderInit()

◆ pastixOrderAlloc()

◆ pastixOrderAllocId()

◆ pastixOrderExit()

◆ pastixOrderBase()

◆ pastixOrderCheck()

◆ pastixOrderExpand()

◆ pastixOrderCopy()

◆ pastixOrderGet()

◆ pastixOrderBcast()

◆ pastixOrderGrid()

◆ pastixOrderLoad()

◆ pastixOrderSave()

◆ orderGetExpandedPeritab()

◆ orderAddIsolate()

◆ orderAmalgamate()

◆ orderApplyLevelOrder()

◆ orderDraw()

◆ orderFindSupernodes()

◆ orderComputeMetis()

◆ ocpts_graph_check()

◆ ocpts_graph_init()

◆ ocpts_graph_exit()

◆ ocpts_compute_graph_ordering()

◆ orderComputePTScotch()

◆ ocs_graph_check()

◆ ocs_graph_init()

◆ ocs_graph_exit()

◆ ocs_compute_graph_ordering()

◆ orderComputeScotch()

◆ orderComputePersonal()

◆ order_scotch_build_strategy()

◆ order_scotch_reallocate_ordemesh()

◆ orderSupernodes()