get_perm_c.c File Reference

Matrix permutation operations. More...

#include "slu_ddefs.h"
#include "colamd.h"

Include dependency graph for get_perm_c.c:

Macros
#define	METISOPTIONS   40

Functions
int	genmmd_ (int *neqns, int_t *xadj, int_t *adjncy, int *invp, int *perm, int_t *delta, int_t *dhead, int_t *qsize, int_t *llist, int_t *marker, int_t *maxint, int_t *nofsub)
void	get_colamd (const int m, const int n, const int_t nnz, int_t *colptr, int_t *rowind, int *perm_c)
	Get COLAMD's permutation for matrix A. More...
void	get_metis (int n, int_t bnz, int_t *b_colptr, int_t *b_rowind, int *perm_c)
	Get METIS' permutation for matrix B. More...
void	getata (const int m, const int n, const int_t nz, int_t *colptr, int_t *rowind, int_t *atanz, int_t **ata_colptr, int_t **ata_rowind)
	Form the structure of A'*A. More...
void	at_plus_a (const int n, const int_t nz, int_t *colptr, int_t *rowind, int_t *bnz, int_t **b_colptr, int_t **b_rowind)
	Form the structure of A'+A. More...
void	get_perm_c (int ispec, SuperMatrix *A, int *perm_c)
	Obtains a permutation matrix by applying the multiple minimum degree ordering code. More...

Macro Definition Documentation

METISOPTIONS

#define METISOPTIONS   40

Function Documentation

at_plus_a()

void at_plus_a	(	const int	n,
		const int_t	nz,
		int_t *	colptr,
		int_t *	rowind,
		int_t *	bnz,
		int_t **	b_colptr,
		int_t **	b_rowind
	)

A is an n-by-n matrix in column oriented format represented by (colptr, rowind). The output A'+A is in column oriented format (symmetrically, also row oriented), represented by (b_colptr, b_rowind).

Parameters

[in]	n	number of columns in matrix A.
[in]	nz	number of nonzeros in matrix A
[in]	colptr	column pointer of size n+1 for matrix A.
[in]	rowind	row indices of size nz for matrix A.
[out]	bnz	on exit, returns the actual number of nonzeros in matrix A'*A.
[out]	b_colptr	column pointer of size n+1 for matrix A'+A.
[out]	b_rowind	row indices of size bnz for matrix A'+A.

genmmd_()

int genmmd_	(	int *	neqns,
		int_t *	xadj,
		int_t *	adjncy,
		int *	invp,
		int *	perm,
		int_t *	delta,
		int_t *	dhead,
		int_t *	qsize,
		int_t *	llist,
		int_t *	marker,
		int_t *	maxint,
		int_t *	nofsub
	)

Here is the call graph for this function:

get_colamd()

void get_colamd	(	const int	m,
		const int	n,
		const int_t	nnz,
		int_t *	colptr,
		int_t *	rowind,
		int *	perm_c
	)

Parameters

[in]	m	Number of rows in matrix A.
[in]	n	Number of columns in matrix A.
[in]	nnz	Number of nonzeros in matrix A.
[in]	colptr	Column pointer of size n+1 for matrix A.
[in]	rowind	Row indices of size nnz for matrix A.
[out]	perm_c	Column permutation vector.

Here is the call graph for this function:

get_metis()

void get_metis	(	int	n,
		int_t	bnz,
		int_t *	b_colptr,
		int_t *	b_rowind,
		int *	perm_c
	)

Parameters

[in]	n	Number of columns in matrix B.
[in]	bnz	Number of nonzeros in matrix B.
[in]	b_colptr	Column pointer of size n+1 for matrix B.
[in]	b_rowind	Row indices of size bnz for matrix B.
[out]	perm_c	Column permutation vector.

Here is the call graph for this function:

get_perm_c()

void get_perm_c	(	int	ispec,
		SuperMatrix *	A,
		int *	perm_c
	)

Obtains a permutation matrix Pc by applying the multiple minimum degree ordering code by Joseph Liu to matrix A'*A or A+A' or using approximate minimum degree column ordering by Davis et. al. The LU factorization of A*Pc tends to have less fill than the LU factorization of A.

Parameters

[in]	ispec	Specifies the type of column ordering to reduce fill: = 1: minimum degree on the structure of A^T * A = 2: minimum degree on the structure of A^T + A = 3: approximate minimum degree for unsymmetric matrices If ispec == 0, the natural ordering (i.e., Pc = I) is returned.
[in]	A	Matrix A in A*X=B, of dimension (A->nrow, A->ncol). The number of the linear equations is A->nrow. Currently, the type of A can be: Stype = NC; Dtype = _D; Mtype = GE. In the future, more general A can be handled.
[out]	perm_c	Column permutation vector of size A->ncol, which defines the permutation matrix Pc; perm_c[i] = j means column i of A is in position j in A*Pc.

Here is the call graph for this function:

getata()

void getata	(	const int	m,
		const int	n,
		const int_t	nz,
		int_t *	colptr,
		int_t *	rowind,
		int_t *	atanz,
		int_t **	ata_colptr,
		int_t **	ata_rowind
	)

A is an m-by-n matrix in column oriented format represented by (colptr, rowind). The output A'*A is in column oriented format (symmetrically, also row oriented), represented by (ata_colptr, ata_rowind).

This routine is modified from GETATA routine by Tim Davis. The complexity of this algorithm is: SUM_{i=1,m} r(i)^2, i.e., the sum of the square of the row counts.

Questions

• Do I need to withhold the dense rows?
• How do I know the number of nonzeros in A'*A?

Parameters

[in]	m	number of rows in matrix A.
[in]	n	number of columns in matrix A.
[in]	nz	number of nonzeros in matrix A
[in]	colptr	column pointer of size n+1 for matrix A.
[in]	rowind	row indices of size nz for matrix A.
[out]	atanz	on exit, returns the actual number of nonzeros in matrix A'*A.
[out]	ata_colptr	column pointer of size n+1 for matrix A'*A.
[out]	ata_rowind	row indices of size atanz for matrix A'*A.