lilc_matrix< el_type > Class Template Reference

A list-of-lists (LIL) matrix in column oriented format. More...

#include <lilc_matrix_declarations.h>

Inheritance diagram for lilc_matrix< el_type >:

Collaboration diagram for lilc_matrix< el_type >:

Classes
struct	pivot_type

Public Types
typedef lil_sparse_matrix< el_type >::idx_vector_type	idx_vector_type
typedef lil_sparse_matrix< el_type >::elt_vector_type	elt_vector_type
typedef idx_vector_type::iterator	idx_it
typedef elt_vector_type::iterator	elt_it
Public Types inherited from lil_sparse_matrix< el_type >
typedef vector< int >	idx_vector_type
typedef vector< el_type >	elt_vector_type

Public Member Functions
	lilc_matrix (int n_rows=0, int n_cols=0)
	Constructor for a column oriented list-of-lists (LIL) matrix. Space for both the values list and the indices list of the matrix is allocated here.
virtual el_type	coeff (const int &i, const int &j, int offset=0) const
	Finds the (i,j)th coefficient of the matrix. More...
bool	coeffRef (const int &i, const int &j, std::pair< idx_it, elt_it > &its)
	Finds the index/value pointers to (i,j)th coefficient of the matrix. More...
void	resize (int n_rows, int n_cols)
	Resizes the matrix. For use in preallocating space before factorization begins. More...
void	find_root (int &s)
	Returns a pseudo-peripheral root of A. This is essentially many chained breadth-first searchs across the graph of A (where A is viewed as an adjacency matrix). More...
bool	find_level_set (vector< int > &lvl_set, vector< bool > &visited)
	Returns the next level set given the current level set of A. This is essentially all neighbours of the currently enqueued nodes in breath-first search. More...
void	sym_rcm (vector< int > &perm)
	Returns a Reverse Cuthill-McKee ordering of the matrix A (stored in perm). More...
void	sym_amd (vector< int > &perm)
	Returns a Approximate Minimum Degree ordering of the matrix A (stored in perm). More...
void	sym_perm (vector< int > &perm)
	Given a permutation vector perm, A is permuted to P'AP, where P is the permutation matrix associated with perm. More...
void	sym_equil ()
	The symmetric matrix A is equilibrated and the symmetric equilibrated matrix SAS is stored in A, where S is a diagonal scaling matrix. More...
void	ildl (lilc_matrix< el_type > &L, block_diag_matrix< el_type > &D, idx_vector_type &perm, const double &fill_factor, const double &tol, const double &pp_tol, int piv_type=pivot_type::BKP)
	Performs an LDL' factorization of this matrix. More...
void	ildl_inplace (block_diag_matrix< el_type > &D, idx_vector_type &perm, const double &fill_factor, const double &tol, const double &pp_tol, int piv_type=pivot_type::BKP)
	Performs an inplace LDL' factorization of this matrix. More...
void	backsolve (const elt_vector_type &b, elt_vector_type &x)
	Performs a back solve of this matrix, assuming that it is lower triangular (stored column major). More...
void	forwardsolve (const elt_vector_type &b, elt_vector_type &x)
	Performs a forward solve of this matrix, assuming that it is upper triangular (stored row major). More...
void	multiply (const elt_vector_type &x, elt_vector_type &y, bool full_mult=true)
	Performs a matrix-vector product with this matrix. More...
void	pivot (swap_struct< el_type > &s, vector< bool > &in_set, lilc_matrix< el_type > &L, const int &k, const int &r)
	Performs a symmetric permutation between row/col k & r of A. More...
void	pivotA (swap_struct< el_type > &s, vector< bool > &in_set, const int &k, const int &r)
	The inplace version of the function above. More...
template<class Container >
void	ensure_invariant (const int &j, const int &k, Container &con, bool update_list=false)
	Ensures two the invariants observed by A.first and A.list are held. More...
void	advance_first (const int &k)
	Updates A.first for iteration k. More...
void	advance_list (const int &k)
	Updates A.list for iteration k. More...
std::string	to_string () const
	Returns a string representation of A, with each column and its corresponding indices & non-zero values printed. More...
bool	load (std::string filename)
	Loads a matrix in matrix market format. More...
bool	load (const std::vector< int > &ptr, const std::vector< int > &row, const std::vector< el_type > &val)
	Loads a matrix in CSC format. More...
bool	load (const int *ptr, const int *row, const el_type *val, int dim)
	Loads a matrix in CSC format. Does no error checking on the input vectors. More...
bool	save (std::string filename, bool sym=false)
	Saves a matrix in matrix market format. More...
Public Member Functions inherited from lil_sparse_matrix< el_type >
	lil_sparse_matrix (int n_rows, int n_cols)
	Default constructor for an abstract matrix. This constructor will be extended by base classes depending on the representation of the matrix (LIL-C or LIL-R).
int	n_rows () const
int	n_cols () const
int	nnz () const
virtual	~lil_sparse_matrix ()

Public Attributes
std::vector< std::vector< int > >	list
	A list of linked lists that gives the non-zero elements in each row of A. Since at any time we may swap between two rows, we require linked lists for each row of A.
std::vector< int >	row_first
	On iteration k, first[i] gives the number of non-zero elements on row i of A before A(i, k).
std::vector< int >	col_first
	On iteration k, first[i] gives the number of non-zero elements on col i of A before A(i, k).
block_diag_matrix< el_type >	S
	A diagonal scaling matrix S such that SAS will be equilibriated in the max-norm (i.e. every row/column has norm 1). S is constructed after running the sym_equil() function, after which SAS will be stored in place of A.
Public Attributes inherited from lil_sparse_matrix< el_type >
int	m_n_rows
	Number of rows in the matrix.
int	m_n_cols
	Number of cols in the matrix.
int	nnz_count
	Number of nonzeros in the matrix.
el_type	eps
	Machine epsilon for el_type.
vector< idx_vector_type >	m_idx
	The row/col indices. The way m_idx is used depends on whether the matrix is in LIL-C or LIL-R.
vector< elt_vector_type >	m_x
	The values of the nonzeros in the matrix.

Detailed Description

template<class el_type>
class lilc_matrix< el_type >

A list-of-lists (LIL) matrix in column oriented format.

For convience, the matrix this class represents will be refered to as matrix A. In LIL-C format, each column of A (an n*n matrix) is stored as a separate vector. The nonzeros are stored in m_idx while the non-zeros are stored in m_x. Both m_x and m_idx are initialized to a list of n lists. m_idx and m_x are ordered dependent on each other, in that A(m_idx[k][j], k) = m_x[k][j].

Member Function Documentation

template<class el_type>

void lilc_matrix< el_type >::advance_first ( const int &  k )

inline

Updates A.first for iteration k.

Parameters

k	current iteration index.

template<class el_type>

void lilc_matrix< el_type >::advance_list ( const int &  k )

inline

Updates A.list for iteration k.

Parameters

k	current iteration index.

template<class el_type>

void lilc_matrix< el_type >::backsolve ( const elt_vector_type &  b, elt_vector_type &  x  )

inline

Performs a back solve of this matrix, assuming that it is lower triangular (stored column major).

Parameters

b	the right hand side.
x	a storage vector for the solution (must be same size as b).

template<class el_type>

virtual el_type lilc_matrix< el_type >::coeff ( const int &  i, const int &  j, int  offset = 0  ) const

inlinevirtual

Finds the (i,j)th coefficient of the matrix.

Parameters

i	the row of the (i,j)th element (zero-indexed).
j	the col of the (i,j)th element (zero-indexed).
offset	an optional search offset for use in linear search (start at offset instead of 0).

Returns

The (i,j)th element of the matrix.

Implements lil_sparse_matrix< el_type >.

template<class el_type>

bool lilc_matrix< el_type >::coeffRef ( const int &  i, const int &  j, std::pair< idx_it, elt_it > &  its  )

inline

Finds the index/value pointers to (i,j)th coefficient of the matrix.

Parameters

i	the row of the (i,j)th element (zero-indexed).
j	the col of the (i,j)th element (zero-indexed).
its	a pair of pointers, one for the index of the found element, and the other for the value of the element. If the element is not found, the pointers point to the end of column j.

Returns

True if (i,j)th element is nonzero, false otherwise.

template<class el_type>

template<class Container >

void lilc_matrix< el_type >::ensure_invariant ( const int &  j, const int &  k, Container &  con, bool  update_list = false  )

inline

Ensures two the invariants observed by A.first and A.list are held.

Invariant

If this matrix is a lower triangular factor of another matrix:

1. On iteration k, first[i] will give the number of non-zero elements on col i of A before A(k, i).
2. On iteration k, list[i][ first[i] ] will contain the first element below or on index k of column i of A.

If this matrix is the matrix to be factored:

1. On iteration k, first[i] will give the number of non-zero elements on row i of A before A(i, k).
2. On iteration k, list[i][ first[i] ] will contain the first element right of or on index k of row i of A.

Parameters

j	the column of con.
k	the iteration number.
con	the container to be swapped.
update_list	boolean indicating whether list or m_x/m_idx should be updated.

template<class el_type>

bool lilc_matrix< el_type >::find_level_set ( vector< int > &  lvl_set, vector< bool > &  visited  )

inline

Returns the next level set given the current level set of A. This is essentially all neighbours of the currently enqueued nodes in breath-first search.

Parameters

lvl_set	the current level set (a list of nodes).
visited	all previously visited nodes.

template<class el_type >

void lilc_matrix< el_type >::find_root ( int &  s )

inline

Returns a pseudo-peripheral root of A. This is essentially many chained breadth-first searchs across the graph of A (where A is viewed as an adjacency matrix).

Parameters

s	contains the initial node to seed the algorithm. A pseudo-peripheral root of A is stored in s at the end of the algorithm.

template<class el_type>

void lilc_matrix< el_type >::forwardsolve ( const elt_vector_type &  b, elt_vector_type &  x  )

inline

Performs a forward solve of this matrix, assuming that it is upper triangular (stored row major).

Parameters

b	the right hand side.
x	a storage vector for the solution (must be same size as b).

template<class el_type >

void lilc_matrix< el_type >::ildl	(	lilc_matrix< el_type > &	L,
		block_diag_matrix< el_type > &	D,
		idx_vector_type &	perm,
		const double &	fill_factor,
		const double &	tol,
		const double &	pp_tol,
		int	piv_type = pivot_type::BKP
	)

Performs an LDL' factorization of this matrix.

The pivoted matrix P'AP will be stored in place of A. In addition, the L and D factors of P'AP will be stored in L and D (so that P'AP = LDL'). The factorization is performed in crout order and follows the algorithm outlined in "Crout versions of the ILU factorization with pivoting for sparse symmetric matrices" by Li and Saad (2005).

Parameters

L	the L factor of this matrix.
D	the D factor of this matrix.
perm	the current permutation of A.
fill_factor	a parameter to control memory usage. Each column is guaranteed to have fewer than fill_factor*(nnz(A)/n_col(A)) elements.
tol	a parameter to control agressiveness of dropping. In each column, elements less than tol*norm(column) are dropped.
pp_tol	a parameter to control aggresiveness of pivoting. Allowable ranges are [0,inf). If the parameter is >= 1, Bunch-Kaufman pivoting will be done in full. If the parameter is 0, partial pivoting will be turned off and the first non-zero pivot under the diagonal will be used. Choices close to 0 increase locality in pivoting (pivots closer to the diagonal are used) while choices closer to 1 increase the stability of pivoting. Useful for situations where you care more about preserving the structure of the matrix rather than bounding the size of its elements.
pivot_type	chooses the type of pivoting procedure used: threshold Bunch-Kaufman, or rook pivoting. If rook pivoting is chosen, pp_tol is ignored.

template<class el_type >

void lilc_matrix< el_type >::ildl_inplace	(	block_diag_matrix< el_type > &	D,
		idx_vector_type &	perm,
		const double &	fill_factor,
		const double &	tol,
		const double &	pp_tol,
		int	piv_type = pivot_type::BKP
	)

Performs an inplace LDL' factorization of this matrix.

The pivoted matrix P'AP will be stored in place of A. In addition, the L and D factors of P'AP will be stored in L and D (so that P'AP = LDL'). The factorization is performed in crout order and follows the algorithm outlined in "Crout versions of the ILU factorization with pivoting for sparse symmetric matrices" by Li and Saad (2005).

Parameters

D	the D factor of this matrix.
perm	the current permutation of A.
fill_factor	a parameter to control memory usage. Each column is guaranteed to have fewer than fill_factor*(nnz(A)/n_col(A)) elements.
tol	a parameter to control agressiveness of dropping. In each column, elements less than tol*norm(column) are dropped.
pp_tol	a parameter to control aggresiveness of pivoting. Allowable ranges are [0,inf). If the parameter is >= 1, Bunch-Kaufman pivoting will be done in full. If the parameter is 0, partial pivoting will be turned off and the first non-zero pivot under the diagonal will be used. Choices close to 0 increase locality in pivoting (pivots closer to the diagonal are used) while choices closer to 1 increase the stability of pivoting. Useful for situations where you care more about preserving the structure of the matrix rather than bounding the size of its elements.

template<class el_type >

bool lilc_matrix< el_type >::load

(

std::string

filename

)

Loads a matrix in matrix market format.

Parameters

filename

the filename of the matrix to be loaded. Must be in matrix market format (.mtx).

template<class el_type >

bool lilc_matrix< el_type >::load	(	const std::vector< int > &	ptr,
		const std::vector< int > &	row,
		const std::vector< el_type > &	val
	)

Loads a matrix in CSC format.

Parameters

ptr	A vector containing the ranges of indices in each col.
row	A vector containing the row indices of the nnz.
val	A vector containing the values of the non-zeros.

template<class el_type >

bool lilc_matrix< el_type >::load	(	const int *	ptr,
		const int *	row,
		const el_type *	val,
		int	dim
	)

Loads a matrix in CSC format. Does no error checking on the input vectors.

Parameters

row	A vector containing the row indices of the nnz.
ptr	A vector containing the ranges of indices in each col.
val	A vector containing the values of the non-zeros.
dim	The dimension of the matrix.

template<class el_type>

void lilc_matrix< el_type >::multiply ( const elt_vector_type &  x, elt_vector_type &  y, bool  full_mult = true  )

inline

Performs a matrix-vector product with this matrix.

Parameters

x	the vector to be multiplied.
y	a storage vector for the result (must be same size as x).
full_mult	if true, we assume that only half the matrix is stored and do do operations per element of the matrix to account for the unstored other half.

template<class el_type>

void lilc_matrix< el_type >::pivot ( swap_struct< el_type > &  s, vector< bool > &  in_set, lilc_matrix< el_type > &  L, const int &  k, const int &  r  )

inline

Performs a symmetric permutation between row/col k & r of A.

Parameters

s	a struct containing temporary variables needed during pivoting.
in_set	a bitset needed for unordered unions during pivoting.
L	the lower triangular factor of A.
k	index of row/col k.
r	index of row/col r.

There are four parts to this pivoting algorithm. For A, due to storing only the lower half, there are three steps to performing a symmetric permutation:

1. A(k, 1:k) must be swapped with A(r, 1:k) (row-row swap).
2. A(k:r, k) must be swapped with A(r, k:r) (row-column swap).
3. A(k:r, k) must be swapped with A(k:r, r) (column-column swap). The steps above are implemented in the pivotA function.

For L, since column k and r are not yet formed, there is only one step (a row permutation):

1. L(k, 1:k) must be swapped with L(r, 1:k) (row-row swap).

template<class el_type>

void lilc_matrix< el_type >::pivotA ( swap_struct< el_type > &  s, vector< bool > &  in_set, const int &  k, const int &  r  )

inline

The inplace version of the function above.

Parameters

s	a struct containing temporary variables needed during pivoting.
in_set	a bitset needed for unordered unions during pivoting.
k	index of row/col k.
r	index of row/col r.

There are three parts to this pivoting algorithm. For A, due to storing only the lower half, there are three steps to performing a symmetric permutation:

1. A(k, 1:k) must be swapped with A(r, 1:k) (row-row swap).
2. A(k:r, k) must be swapped with A(r, k:r) (row-column swap).
3. A(k:r, k) must be swapped with A(k:r, r) (column-column swap).

template<class el_type>

void lilc_matrix< el_type >::resize ( int  n_rows, int  n_cols  )

inline

Resizes the matrix. For use in preallocating space before factorization begins.

Parameters

n_rows	the number of rows in the resized matrix.
n_cols	the number of cols in the resized matrix.

template<class el_type >

bool lilc_matrix< el_type >::save	(	std::string	filename,
		bool	sym = false
	)

Saves a matrix in matrix market format.

Parameters

filename	the filename of the matrix to be saved. All matrices saved are in matrix market format (.mtx).
sym	flags whether the matrix is symmetric or not.

template<class el_type >

void lilc_matrix< el_type >::sym_amd ( vector< int > &  perm )

inline

Returns a Approximate Minimum Degree ordering of the matrix A (stored in perm).

A detailed description of this function as well as all its subfunctions can be found in "An Approximate Minimum Dgree Algorithm" by Davis, Amestoy, and Duff (1981).

Parameters

perm	An empty permutation vector (filled on function completion).

template<class el_type >

void lilc_matrix< el_type >::sym_equil

(

)

The symmetric matrix A is equilibrated and the symmetric equilibrated matrix SAS is stored in A, where S is a diagonal scaling matrix.

This algorithm is based on the one outlined in "Equilibration of Symmetric Matrices in the Max-Norm" by Bunch (1971).

template<class el_type >

void lilc_matrix< el_type >::sym_perm

(

std::vector< int > &

perm

)

Given a permutation vector perm, A is permuted to P'AP, where P is the permutation matrix associated with perm.

Parameters

perm	the permutation vector.

template<class el_type >

void lilc_matrix< el_type >::sym_rcm ( vector< int > &  perm )

inline

Returns a Reverse Cuthill-McKee ordering of the matrix A (stored in perm).

A detailed description of this function as well as all its subfunctions can be found in "Computer Solution of Large Sparse Positive Definite Systems" by George and Liu (1981).

Parameters

perm	An empty permutation vector (filled on function completion).

template<class el_type >

std::string lilc_matrix< el_type >::to_string ( ) const

virtual

Returns a string representation of A, with each column and its corresponding indices & non-zero values printed.

Returns

A string representation of this matrix.

Implements lil_sparse_matrix< el_type >.

---

The documentation for this class was generated from the following files:

• source/lilc_matrix.h
• source/lilc_matrix_declarations.h
• source/lilc_matrix_find_level_set.h
• source/lilc_matrix_find_root.h
• source/lilc_matrix_ildl.h
• source/lilc_matrix_ildl_inplace.h
• source/lilc_matrix_load.h
• source/lilc_matrix_pivot.h
• source/lilc_matrix_save.h
• source/lilc_matrix_sym_amd.h
• source/lilc_matrix_sym_equil.h
• source/lilc_matrix_sym_perm.h
• source/lilc_matrix_sym_rcm.h
• source/lilc_matrix_to_string.h