get_perm_c.c File Reference
Common

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.