#include "amesos_ccolamd.h"
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <stdio.h>
#include "amesos_UFconfig.h"

Include dependency graph for amesos_ccolamd.c:

Go to the source code of this file.

Classes
struct	CColamd_Col_struct

struct	CColamd_Row_struct

Macros
#define	NDEBUG

#define	NULL ((void *) 0)

#define	Int int

#define	ID "%d"

#define	Int_MAX INT_MAX

#define	CCOLAMD_recommended amesos_ccolamd_recommended

#define	CCOLAMD_set_defaults amesos_ccolamd_set_defaults

#define	CCOLAMD_2 amesos_ccolamd2

#define	CCOLAMD_MAIN amesos_ccolamd

#define	CCOLAMD_apply_order amesos_ccolamd_apply_order

#define	CCOLAMD_postorder amesos_ccolamd_postorder

#define	CCOLAMD_post_tree amesos_ccolamd_post_tree

#define	CCOLAMD_fsize amesos_ccolamd_fsize

#define	CSYMAMD_MAIN amesos_csymamd

#define	CCOLAMD_report amesos_ccolamd_report

#define	CSYMAMD_report amesos_csymamd_report

#define	EMPTY (-1)

#define	MAX(a, b) (((a) > (b)) ? (a) : (b))

#define	MIN(a, b) (((a) < (b)) ? (a) : (b))

#define	GLOBAL

#define	PUBLIC

#define	PRIVATE static

#define	DENSE_DEGREE(alpha, n) ((Int) MAX (16.0, (alpha) * sqrt ((double) (n))))

#define	CMEMBER(c) ((cmember == (Int *) NULL) ? (0) : (cmember [c]))

#define	SCALAR_IS_NAN(x) ((x) != (x))

#define	INT_OVERFLOW(x)

#define	ONES_COMPLEMENT(r) (-(r)-1)

#define	TRUE (1)

#define	FALSE (0)

#define	ALIVE (0)

#define	DEAD (-1)

#define	DEAD_PRINCIPAL (-1)

#define	DEAD_NON_PRINCIPAL (-2)

#define	ROW_IS_DEAD(r) ROW_IS_MARKED_DEAD (Row[r].shared2.mark)

#define	ROW_IS_MARKED_DEAD(row_mark) (row_mark < ALIVE)

#define	ROW_IS_ALIVE(r) (Row [r].shared2.mark >= ALIVE)

#define	COL_IS_DEAD(c) (Col [c].start < ALIVE)

#define	COL_IS_ALIVE(c) (Col [c].start >= ALIVE)

#define	COL_IS_DEAD_PRINCIPAL(c) (Col [c].start == DEAD_PRINCIPAL)

#define	KILL_ROW(r) { Row [r].shared2.mark = DEAD ; }

#define	KILL_PRINCIPAL_COL(c) { Col [c].start = DEAD_PRINCIPAL ; }

#define	KILL_NON_PRINCIPAL_COL(c) { Col [c].start = DEAD_NON_PRINCIPAL ; }

#define	INDEX(i) (i)

#define	PRINTF(params) { if (amesos_ccolamd_printf != NULL) (void) amesos_ccolamd_printf params ; }

#define	DEBUG0(params) ;

#define	DEBUG1(params) ;

#define	DEBUG2(params) ;

#define	DEBUG3(params) ;

#define	DEBUG4(params) ;

#define	ASSERT(expression)

#define	CCOLAMD_C(n_col, ok) ((t_mult (t_add (n_col, 1, ok), sizeof (CColamd_Col), ok) / sizeof (Int)))

#define	CCOLAMD_R(n_row, ok) ((t_mult (t_add (n_row, 1, ok), sizeof (CColamd_Row), ok) / sizeof (Int)))

Typedefs
typedef struct CColamd_Col_struct	CColamd_Col

typedef struct CColamd_Row_struct	CColamd_Row

Functions
PRIVATE Int	init_rows_cols (Int n_row, Int n_col, CColamd_Row Row[], CColamd_Col Col[], Int A[], Int p[], Int stats[CCOLAMD_STATS])

PRIVATE void	init_scoring (Int n_row, Int n_col, CColamd_Row Row[], CColamd_Col Col[], Int A[], Int head[], double knobs[CCOLAMD_KNOBS], Int p_n_row2, Int p_n_col2, Int p_max_deg, Int cmember[], Int n_cset, Int cset_start[], Int dead_cols[], Int p_ndense_row, Int p_nempty_row, Int p_nnewlyempty_row, Int p_ndense_col, Int p_nempty_col, Int *p_nnewlyempty_col)

PRIVATE Int	find_ordering (Int n_row, Int n_col, Int Alen, CColamd_Row Row[], CColamd_Col Col[], Int A[], Int head[], Int max_deg, Int pfree, Int cset[], Int cset_start[], Int cmember[], Int Front_npivcol[], Int Front_nrows[], Int Front_ncols[], Int Front_parent[], Int Front_cols[], Int *p_nfr, Int aggressive, Int InFront[], Int order_for_lu)

PRIVATE void	detect_super_cols (CColamd_Col Col[], Int A[], Int head[], Int row_start, Int row_length, Int in_set[])

PRIVATE Int	garbage_collection (Int n_row, Int n_col, CColamd_Row Row[], CColamd_Col Col[], Int A[], Int *pfree)

PRIVATE Int	clear_mark (Int tag_mark, Int max_mark, Int n_row, CColamd_Row Row[])

PRIVATE void	print_report (char *method, Int stats[CCOLAMD_STATS])

static size_t	t_add (size_t a, size_t b, int *ok)

static size_t	t_mult (size_t a, size_t k, int *ok)

static size_t	ccolamd_need (Int nnz, Int n_row, Int n_col, int *ok)

PUBLIC size_t	CCOLAMD_recommended (Int nnz, Int n_row, Int n_col)

PUBLIC void	CCOLAMD_set_defaults (double knobs[CCOLAMD_KNOBS])

PUBLIC Int	CSYMAMD_MAIN (Int n, Int A[], Int p[], Int perm[], double knobs[CCOLAMD_KNOBS], Int stats[CCOLAMD_STATS], void (allocate)(size_t, size_t), void(release)(void ), Int cmember[], Int stype)

PUBLIC Int	CCOLAMD_MAIN (Int n_row, Int n_col, Int Alen, Int A[], Int p[], double knobs[CCOLAMD_KNOBS], Int stats[CCOLAMD_STATS], Int cmember[])

PUBLIC Int	CCOLAMD_2 (Int n_row, Int n_col, Int Alen, Int A[], Int p[], double knobs[CCOLAMD_KNOBS], Int stats[CCOLAMD_STATS], Int Front_npivcol[], Int Front_nrows[], Int Front_ncols[], Int Front_parent[], Int Front_cols[], Int *p_nfr, Int InFront[], Int cmember[])

PUBLIC void	CCOLAMD_report (Int stats[CCOLAMD_STATS])

PUBLIC void	CSYMAMD_report (Int stats[CCOLAMD_STATS])

GLOBAL void	CCOLAMD_apply_order (Int Front[], const Int Order[], Int Temp[], Int nn, Int nfr)

GLOBAL void	CCOLAMD_fsize (Int nn, Int Fsize[], Int Fnrows[], Int Fncols[], Int Parent[], Int Npiv[])

GLOBAL void	CCOLAMD_postorder (Int nn, Int Parent[], Int Nv[], Int Fsize[], Int Order[], Int Child[], Int Sibling[], Int Stack[], Int Front_cols[], Int cmember[])

GLOBAL Int	CCOLAMD_post_tree (Int root, Int k, Int Child[], const Int Sibling[], Int Order[], Int Stack[])

Macro Definition Documentation

#define NDEBUG

Definition at line 607 of file amesos_ccolamd.c.

#define NULL ((void *) 0)

Definition at line 634 of file amesos_ccolamd.c.

#define Int int

Definition at line 664 of file amesos_ccolamd.c.

#define ID "%d"

Definition at line 665 of file amesos_ccolamd.c.

#define Int_MAX INT_MAX

Definition at line 666 of file amesos_ccolamd.c.

#define CCOLAMD_recommended amesos_ccolamd_recommended

Definition at line 668 of file amesos_ccolamd.c.

#define CCOLAMD_set_defaults amesos_ccolamd_set_defaults

Definition at line 669 of file amesos_ccolamd.c.

#define CCOLAMD_2 amesos_ccolamd2

Definition at line 670 of file amesos_ccolamd.c.

#define CCOLAMD_MAIN amesos_ccolamd

Definition at line 671 of file amesos_ccolamd.c.

#define CCOLAMD_apply_order amesos_ccolamd_apply_order

Definition at line 672 of file amesos_ccolamd.c.

#define CCOLAMD_postorder amesos_ccolamd_postorder

Definition at line 673 of file amesos_ccolamd.c.

#define CCOLAMD_post_tree amesos_ccolamd_post_tree

Definition at line 674 of file amesos_ccolamd.c.

#define CCOLAMD_fsize amesos_ccolamd_fsize

Definition at line 675 of file amesos_ccolamd.c.

#define CSYMAMD_MAIN amesos_csymamd

Definition at line 676 of file amesos_ccolamd.c.

#define CCOLAMD_report amesos_ccolamd_report

Definition at line 677 of file amesos_ccolamd.c.

#define CSYMAMD_report amesos_csymamd_report

Definition at line 678 of file amesos_ccolamd.c.

#define EMPTY (-1)

Definition at line 754 of file amesos_ccolamd.c.

#define MAX	(	a,
		b
	)	(((a) > (b)) ? (a) : (b))

Definition at line 755 of file amesos_ccolamd.c.

#define MIN	(	a,
		b
	)	(((a) < (b)) ? (a) : (b))

Definition at line 756 of file amesos_ccolamd.c.

#define GLOBAL

Definition at line 759 of file amesos_ccolamd.c.

#define PUBLIC

Definition at line 760 of file amesos_ccolamd.c.

#define PRIVATE static

Definition at line 761 of file amesos_ccolamd.c.

#define DENSE_DEGREE	(	alpha,
		n
	)	((Int) MAX (16.0, (alpha) * sqrt ((double) (n))))

Definition at line 763 of file amesos_ccolamd.c.

#define CMEMBER ( c ) ((cmember == (Int *) NULL) ? (0) : (cmember [c]))

Definition at line 766 of file amesos_ccolamd.c.

#define SCALAR_IS_NAN ( x ) ((x) != (x))

Definition at line 769 of file amesos_ccolamd.c.

#define INT_OVERFLOW ( x )

Value:

((!((x) * (1.0+1e-8) <= (double) Int_MAX)) \

|| SCALAR_IS_NAN (x))

SCALAR_IS_NAN

#define SCALAR_IS_NAN(x)

Definition: amesos_ccolamd.c:769

Int_MAX

#define Int_MAX

Definition: amesos_ccolamd.c:666

Definition at line 772 of file amesos_ccolamd.c.

#define ONES_COMPLEMENT ( r ) (-(r)-1)

Definition at line 775 of file amesos_ccolamd.c.

#define TRUE (1)

Definition at line 778 of file amesos_ccolamd.c.

#define FALSE (0)

Definition at line 779 of file amesos_ccolamd.c.

#define ALIVE (0)

Definition at line 782 of file amesos_ccolamd.c.

#define DEAD (-1)

Definition at line 783 of file amesos_ccolamd.c.

#define DEAD_PRINCIPAL (-1)

Definition at line 786 of file amesos_ccolamd.c.

#define DEAD_NON_PRINCIPAL (-2)

Definition at line 787 of file amesos_ccolamd.c.

#define ROW_IS_DEAD ( r ) ROW_IS_MARKED_DEAD (Row[r].shared2.mark)

Definition at line 790 of file amesos_ccolamd.c.

#define ROW_IS_MARKED_DEAD ( row_mark ) (row_mark < ALIVE)

Definition at line 791 of file amesos_ccolamd.c.

#define ROW_IS_ALIVE ( r ) (Row [r].shared2.mark >= ALIVE)

Definition at line 792 of file amesos_ccolamd.c.

#define COL_IS_DEAD ( c ) (Col [c].start < ALIVE)

Definition at line 793 of file amesos_ccolamd.c.

#define COL_IS_ALIVE ( c ) (Col [c].start >= ALIVE)

Definition at line 794 of file amesos_ccolamd.c.

#define COL_IS_DEAD_PRINCIPAL ( c ) (Col [c].start == DEAD_PRINCIPAL)

Definition at line 795 of file amesos_ccolamd.c.

#define KILL_ROW ( r ) { Row [r].shared2.mark = DEAD ; }

Definition at line 796 of file amesos_ccolamd.c.

#define KILL_PRINCIPAL_COL ( c ) { Col [c].start = DEAD_PRINCIPAL ; }

Definition at line 797 of file amesos_ccolamd.c.

#define KILL_NON_PRINCIPAL_COL ( c ) { Col [c].start = DEAD_NON_PRINCIPAL ; }

Definition at line 798 of file amesos_ccolamd.c.

#define INDEX ( i ) (i)

Definition at line 810 of file amesos_ccolamd.c.

#define PRINTF ( params ) { if (amesos_ccolamd_printf != NULL) (void) amesos_ccolamd_printf params ; }

Definition at line 814 of file amesos_ccolamd.c.

#define DEBUG0 ( params ) ;

Definition at line 897 of file amesos_ccolamd.c.

#define DEBUG1 ( params ) ;

Definition at line 898 of file amesos_ccolamd.c.

#define DEBUG2 ( params ) ;

Definition at line 899 of file amesos_ccolamd.c.

#define DEBUG3 ( params ) ;

Definition at line 900 of file amesos_ccolamd.c.

#define DEBUG4 ( params ) ;

Definition at line 901 of file amesos_ccolamd.c.

#define ASSERT ( expression )

Definition at line 903 of file amesos_ccolamd.c.

#define CCOLAMD_C	(	n_col,
		ok
	)	((t_mult (t_add (n_col, 1, ok), sizeof (CColamd_Col), ok) / sizeof (Int)))

Definition at line 1065 of file amesos_ccolamd.c.

#define CCOLAMD_R	(	n_row,
		ok
	)	((t_mult (t_add (n_row, 1, ok), sizeof (CColamd_Row), ok) / sizeof (Int)))

Definition at line 1068 of file amesos_ccolamd.c.

Typedef Documentation

typedef struct CColamd_Col_struct CColamd_Col

typedef struct CColamd_Row_struct CColamd_Row

Function Documentation

PRIVATE Int init_rows_cols	(	Int	n_row,
		Int	n_col,
		CColamd_Row	Row[],
		CColamd_Col	Col[],
		Int	A[],
		Int	p[],
		Int	stats[CCOLAMD_STATS]
	)

Definition at line 2045 of file amesos_ccolamd.c.

PRIVATE void init_scoring	(	Int	n_row,
		Int	n_col,
		CColamd_Row	Row[],
		CColamd_Col	Col[],
		Int	A[],
		Int	head[],
		double	knobs[CCOLAMD_KNOBS],
		Int *	p_n_row2,
		Int *	p_n_col2,
		Int *	p_max_deg,
		Int	cmember[],
		Int	n_cset,
		Int	cset_start[],
		Int	dead_cols[],
		Int *	p_ndense_row,
		Int *	p_nempty_row,
		Int *	p_nnewlyempty_row,
		Int *	p_ndense_col,
		Int *	p_nempty_col,
		Int *	p_nnewlyempty_col
	)

Definition at line 2290 of file amesos_ccolamd.c.

PRIVATE Int find_ordering	(	Int	n_row,
		Int	n_col,
		Int	Alen,
		CColamd_Row	Row[],
		CColamd_Col	Col[],
		Int	A[],
		Int	head[],
		Int	max_deg,
		Int	pfree,
		Int	cset[],
		Int	cset_start[],
		Int	cmember[],
		Int	Front_npivcol[],
		Int	Front_nrows[],
		Int	Front_ncols[],
		Int	Front_parent[],
		Int	Front_cols[],
		Int *	p_nfr,
		Int	aggressive,
		Int	InFront[],
		Int	order_for_lu
	)

Definition at line 2576 of file amesos_ccolamd.c.

PRIVATE void detect_super_cols	(	CColamd_Col	Col[],
		Int	A[],
		Int	head[],
		Int	row_start,
		Int	row_length,
		Int	in_set[]
	)

Definition at line 3404 of file amesos_ccolamd.c.

PRIVATE Int garbage_collection	(	Int	n_row,
		Int	n_col,
		CColamd_Row	Row[],
		CColamd_Col	Col[],
		Int	A[],
		Int *	pfree
	)

Definition at line 3576 of file amesos_ccolamd.c.

PRIVATE Int clear_mark	(	Int	tag_mark,
		Int	max_mark,
		Int	n_row,
		CColamd_Row	Row[]
	)

Definition at line 3708 of file amesos_ccolamd.c.

PRIVATE void print_report	(	char *	method,
		Int	stats[CCOLAMD_STATS]
	)

Definition at line 3745 of file amesos_ccolamd.c.

static size_t t_add	(	size_t	a,
		size_t	b,
		int *	ok
	)

static

Definition at line 1047 of file amesos_ccolamd.c.

static size_t t_mult	(	size_t	a,
		size_t	k,
		int *	ok
	)

static

Definition at line 1054 of file amesos_ccolamd.c.

static size_t ccolamd_need	(	Int	nnz,
		Int	n_row,
		Int	n_col,
		int *	ok
	)

static

Definition at line 1078 of file amesos_ccolamd.c.

PUBLIC size_t CCOLAMD_recommended	(	Int	nnz,
		Int	n_row,
		Int	n_col
	)

Definition at line 1115 of file amesos_ccolamd.c.

PUBLIC void CCOLAMD_set_defaults ( double knobs[CCOLAMD_KNOBS] )

Definition at line 1146 of file amesos_ccolamd.c.

PUBLIC Int CSYMAMD_MAIN	(	Int	n,
		Int	A[],
		Int	p[],
		Int	perm[],
		double	knobs[CCOLAMD_KNOBS],
		Int	stats[CCOLAMD_STATS],
		void ()(size_t, size_t)	allocate,
		void()(void )	release,
		Int	cmember[],
		Int	stype
	)

Definition at line 1176 of file amesos_ccolamd.c.

PUBLIC Int CCOLAMD_MAIN	(	Int	n_row,
		Int	n_col,
		Int	Alen,
		Int	A[],
		Int	p[],
		double	knobs[CCOLAMD_KNOBS],
		Int	stats[CCOLAMD_STATS],
		Int	cmember[]
	)

Definition at line 1507 of file amesos_ccolamd.c.

PUBLIC Int CCOLAMD_2	(	Int	n_row,
		Int	n_col,
		Int	Alen,
		Int	A[],
		Int	p[],
		double	knobs[CCOLAMD_KNOBS],
		Int	stats[CCOLAMD_STATS],
		Int	Front_npivcol[],
		Int	Front_nrows[],
		Int	Front_ncols[],
		Int	Front_parent[],
		Int	Front_cols[],
		Int *	p_nfr,
		Int	InFront[],
		Int	cmember[]
	)

Definition at line 1536 of file amesos_ccolamd.c.

PUBLIC void CCOLAMD_report ( Int stats[CCOLAMD_STATS] )

Definition at line 2003 of file amesos_ccolamd.c.

PUBLIC void CSYMAMD_report ( Int stats[CCOLAMD_STATS] )

Definition at line 2016 of file amesos_ccolamd.c.

GLOBAL void CCOLAMD_apply_order	(	Int	Front[],
		const Int	Order[],
		Int	Temp[],
		Int	nn,
		Int	nfr
	)

Definition at line 3889 of file amesos_ccolamd.c.

GLOBAL void CCOLAMD_fsize	(	Int	nn,
		Int	Fsize[],
		Int	Fnrows[],
		Int	Fncols[],
		Int	Parent[],
		Int	Npiv[]
	)

Definition at line 3926 of file amesos_ccolamd.c.

GLOBAL void CCOLAMD_postorder	(	Int	nn,
		Int	Parent[],
		Int	Nv[],
		Int	Fsize[],
		Int	Order[],
		Int	Child[],
		Int	Sibling[],
		Int	Stack[],
		Int	Front_cols[],
		Int	cmember[]
	)

Definition at line 3986 of file amesos_ccolamd.c.

GLOBAL Int CCOLAMD_post_tree	(	Int	root,
		Int	k,
		Int	Child[],
		const Int	Sibling[],
		Int	Order[],
		Int	Stack[]
	)

Definition at line 4173 of file amesos_ccolamd.c.

Classes

Macros

Typedefs

Functions

Macro Definition Documentation

Typedef Documentation

Function Documentation