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:

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)
void	get_metis (int n, int_t bnz, int_t *b_colptr, int_t *b_rowind, int *perm_c)
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)
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)
void	get_perm_c (int ispec, SuperMatrix *A, int *perm_c)

Detailed Description

Copyright (c) 2003, The Regents of the University of California, through Lawrence Berkeley National Laboratory (subject to receipt of any required approvals from U.S. Dept. of Energy)

All rights reserved.

The source code is distributed under BSD license, see the file License.txt at the top-level directory.

-- SuperLU routine (version 3.1) --
Univ. of California Berkeley, Xerox Palo Alto Research Center,
and Lawrence Berkeley National Lab.
August 1, 2008
March 25, 2023  add METIS option

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
	)

Purpose
=======

Form the structure of A'+A. 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).

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
	)

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
	)

Here is the call graph for this function:

get_perm_c()

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

Purpose
=======

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

Arguments
=========

ispec   (input) int
        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.

A       (input) SuperMatrix*
        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.

perm_c  (output) int*
        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
	)

Purpose
=======

Form the structure of A'*A. 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
=========
    o  Do I need to withhold the *dense* rows?
    o  How do I know the number of nonzeros in A'*A?