Sparse matrix with customizable parallelization. More...

#include <sparse.hpp>

Inheritance diagram for irlba::ParallelSparseMatrix< EigenVector_, EigenMatrix_, ValueArray_, IndexArray_, PointerArray_ >:

[legend]

Collaboration diagram for irlba::ParallelSparseMatrix< EigenVector_, EigenMatrix_, ValueArray_, IndexArray_, PointerArray_ >:

[legend]

Public Types
typedef I< decltype(std::declval< PointerArray_ >()[0])>	PointerType

Public Member Functions
	ParallelSparseMatrix ()

	ParallelSparseMatrix (Eigen::Index nrow, Eigen::Index ncol, ValueArray_ x, IndexArray_ i, PointerArray_ p, bool column_major, int num_threads)

Eigen::Index	rows () const

Eigen::Index	cols () const

const ValueArray_ &	get_values () const

const IndexArray_ &	get_indices () const

const PointerArray_ &	get_pointers () const

const std::vector< Eigen::Index > &	get_primary_boundaries () const

const std::vector< Eigen::Index > &	get_secondary_boundaries () const

const std::vector< std::vector< PointerType > > &	get_secondary_nonzero_boundaries () const

std::unique_ptr< Workspace< EigenVector_ > >	new_workspace () const

std::unique_ptr< AdjointWorkspace< EigenVector_ > >	new_adjoint_workspace () const

std::unique_ptr< RealizeWorkspace< EigenMatrix_ > >	new_realize_workspace () const

auto	new_known_workspace () const

auto	new_known_adjoint_workspace () const

auto	new_known_realize_workspace () const

Public Member Functions inherited from irlba::Matrix< EigenVector_, EigenMatrix_ >
std::unique_ptr< Workspace< EigenVector_ > >	new_known_workspace () const

std::unique_ptr< AdjointWorkspace< EigenVector_ > >	new_known_adjoint_workspace () const

std::unique_ptr< RealizeWorkspace< EigenMatrix_ > >	new_known_realize_workspace () const

Detailed Description

template<class EigenVector_, class EigenMatrix_, class ValueArray_, class IndexArray_, class PointerArray_>
class irlba::ParallelSparseMatrix< EigenVector_, EigenMatrix_, ValueArray_, IndexArray_, PointerArray_ >

Sparse matrix with customizable parallelization.

This provides an alternative to Eigen::SparseMatrix for parallelized multiplication of compressed sparse matrices. Unlike Eigen's sparse matrix, this implementation is able to parallelize when the multiplication does not align well with the storage layout, e.g., multiplication of a compressed sparse column matrix by a dense vector on the right hand side. On construction, it also pre-allocates the rows and/or columns to each thread, aiming to balance the number of non-zero elements that each thread needs to process. All subsequent multiplications can then use these allocations, which is useful for compute() where the cost of pre-allocation is abrogated by repeated multiplication calls.

Some cursory testing indicates that the performance of this implementation is comparable to Eigen for OpenMP-based parallelization. However, the real purpose of this class is to support custom parallelization schemes in cases where OpenMP is not available. This is achieved by defining IRLBA_CUSTOM_PARALLEL macro to the name of a function implementing a custom scheme. Such a function should accept two arguments - an integer specifying the number of threads, and a lambda that accepts a thread number. It should then loop over the number of threads and launch one job for each thread via the lambda. Once all threads are complete, the function should return.

Template Parameters

EigenVector_	A floating-point `Eigen::Vector` to be used as input/output of multiplication operations.
EigenMatrix_	A dense floating-point `Eigen::Matrix` in which to store the realized matrix. Typically of the same scalar type as `EigenVector_`.
ValueArray_	Array class containing numeric values for the non-zero values. Should support a read-only `[]` operator.
IndexArray_	Array class containing integer values for the indices of the non-zero values. Should support a read-only `[]` operator.
PointerArray_	Array class containing integer values for the pointers to the row/column boundaries. Should support a read-only `[]` operator.

Member Typedef Documentation

◆ PointerType

template<class EigenVector_ , class EigenMatrix_ , class ValueArray_ , class IndexArray_ , class PointerArray_ >

I<decltype(std::declval<PointerArray_>()[0])> irlba::ParallelSparseMatrix< EigenVector_, EigenMatrix_, ValueArray_, IndexArray_, PointerArray_ >::PointerType

Type of the elements inside a PointerArray_.

Constructor & Destructor Documentation

◆ ParallelSparseMatrix() [1/2]

template<class EigenVector_ , class EigenMatrix_ , class ValueArray_ , class IndexArray_ , class PointerArray_ >

irlba::ParallelSparseMatrix< EigenVector_, EigenMatrix_, ValueArray_, IndexArray_, PointerArray_ >::ParallelSparseMatrix ( )

inline

Default constructor. This object cannot be used for any operations.

◆ ParallelSparseMatrix() [2/2]

template<class EigenVector_ , class EigenMatrix_ , class ValueArray_ , class IndexArray_ , class PointerArray_ >

irlba::ParallelSparseMatrix< EigenVector_, EigenMatrix_, ValueArray_, IndexArray_, PointerArray_ >::ParallelSparseMatrix	(	Eigen::Index	nrow,
		Eigen::Index	ncol,
		ValueArray_	x,
		IndexArray_	i,
		PointerArray_	p,
		bool	column_major,
		int	num_threads )

inline

Parameters

nrow	Number of rows.
ncol	Number of columns.
x	Values of non-zero elements.
i	Indices of non-zero elements. Each entry corresponds to a value in `x`, so `i` should be an array of length equal to `x`. If `column_major = true`, `i` should contain row indices; otherwise it should contain column indices.
p	Pointers to the start of each column (if `column_major = true`) or row (otherwise). This should be an ordered array of length equal to the number of columns or rows plus 1.
column_major	Whether the matrix should be in compressed sparse column format. If `false`, this is assumed to be in row-major format.
num_threads	Number of threads to be used for multiplication.

x, i and p represent the typical components of a compressed sparse column/row matrix. Thus, entries in i should be sorted within each column/row, where the boundaries between columns/rows are defined by p.

Member Function Documentation

◆ cols()

template<class EigenVector_ , class EigenMatrix_ , class ValueArray_ , class IndexArray_ , class PointerArray_ >

Eigen::Index irlba::ParallelSparseMatrix< EigenVector_, EigenMatrix_, ValueArray_, IndexArray_, PointerArray_ >::cols ( ) const

inlinevirtual

Returns: Number of columns in the matrix.

Implements irlba::Matrix< EigenVector_, EigenMatrix_ >.

◆ get_indices()

template<class EigenVector_ , class EigenMatrix_ , class ValueArray_ , class IndexArray_ , class PointerArray_ >

const IndexArray_ & irlba::ParallelSparseMatrix< EigenVector_, EigenMatrix_, ValueArray_, IndexArray_, PointerArray_ >::get_indices ( ) const

inline

Returns: Indices of non-zero elements, equivalent to i in the constructor. These are row or column indices for compressed sparse row or column format, respectively, depending on column_major.

◆ get_pointers()

template<class EigenVector_ , class EigenMatrix_ , class ValueArray_ , class IndexArray_ , class PointerArray_ >

const PointerArray_ & irlba::ParallelSparseMatrix< EigenVector_, EigenMatrix_, ValueArray_, IndexArray_, PointerArray_ >::get_pointers ( ) const

inline

Returns: Pointers to the start of each row or column, equivalent to p in the constructor.

◆ get_primary_boundaries()

template<class EigenVector_ , class EigenMatrix_ , class ValueArray_ , class IndexArray_ , class PointerArray_ >

const std::vector< Eigen::Index > & irlba::ParallelSparseMatrix< EigenVector_, EigenMatrix_, ValueArray_, IndexArray_, PointerArray_ >::get_primary_boundaries ( ) const

inline

This should only be called if num_threads > 1 in the constructor, otherwise it will not be initialized.

Returns: Vector of length equal to the number of threads plus one. The t-th and t + 1-th entries specifies the first and one-past-the-last elements along the primary dimension (e.g., column for column_major = true) that each thread operates on.

◆ get_secondary_boundaries()

template<class EigenVector_ , class EigenMatrix_ , class ValueArray_ , class IndexArray_ , class PointerArray_ >

const std::vector< Eigen::Index > & irlba::ParallelSparseMatrix< EigenVector_, EigenMatrix_, ValueArray_, IndexArray_, PointerArray_ >::get_secondary_boundaries ( ) const

inline

This should only be called if num_threads > 1 in the constructor, otherwise it will not be initialized.

Returns: Vector of length equal to the number of threads plus one. The t-th and t + 1-th entries specifies the first and one-past-the-last elements along the secondary dimension (e.g., row for column_major = true) that each thread operates on.

◆ get_secondary_nonzero_boundaries()

template<class EigenVector_ , class EigenMatrix_ , class ValueArray_ , class IndexArray_ , class PointerArray_ >

const std::vector< std::vector< PointerType > > & irlba::ParallelSparseMatrix< EigenVector_, EigenMatrix_, ValueArray_, IndexArray_, PointerArray_ >::get_secondary_nonzero_boundaries ( ) const

inline

This should only be called if num_threads > 1 in the constructor, otherwise it will not be initialized.

Returns: Vector of length equal to the number of threads plus one. Each inner vector is of length equal to the extent of the primary dimension (e.g., number of columns for column_major = true). For thread t, secondary_nonzero_boundaries[t][i] is the first non-zero element to be processed by this thread in the primary dimension element i, while boundaries[t + 1][i] is one-past-the-last non-zero element to be processed. This is guaranteed to contain all and only non-zero elements with indices i where secondary_boundaries[t] <= i < secondary_boundaries[t + 1].

◆ get_values()

template<class EigenVector_ , class EigenMatrix_ , class ValueArray_ , class IndexArray_ , class PointerArray_ >

const ValueArray_ & irlba::ParallelSparseMatrix< EigenVector_, EigenMatrix_, ValueArray_, IndexArray_, PointerArray_ >::get_values ( ) const

inline

Returns: Non-zero elements in compressed sparse row/column format. This is equivalent to x in the constructor.

◆ new_adjoint_workspace()

template<class EigenVector_ , class EigenMatrix_ , class ValueArray_ , class IndexArray_ , class PointerArray_ >

std::unique_ptr< AdjointWorkspace< EigenVector_ > > irlba::ParallelSparseMatrix< EigenVector_, EigenMatrix_, ValueArray_, IndexArray_, PointerArray_ >::new_adjoint_workspace ( ) const

inlinevirtual

Returns: Pointer to a new workspace for adjoint matrix multiplication. The lifetime of this object should not exceed that of its parent Matrix.

Implements irlba::Matrix< EigenVector_, EigenMatrix_ >.

◆ new_known_adjoint_workspace()

template<class EigenVector_ , class EigenMatrix_ , class ValueArray_ , class IndexArray_ , class PointerArray_ >

auto irlba::ParallelSparseMatrix< EigenVector_, EigenMatrix_, ValueArray_, IndexArray_, PointerArray_ >::new_known_adjoint_workspace ( ) const

inline

Overrides Matrix::new_adjoint_workspace() to enable devirtualization.

◆ new_known_realize_workspace()

template<class EigenVector_ , class EigenMatrix_ , class ValueArray_ , class IndexArray_ , class PointerArray_ >

auto irlba::ParallelSparseMatrix< EigenVector_, EigenMatrix_, ValueArray_, IndexArray_, PointerArray_ >::new_known_realize_workspace ( ) const

inline

Overrides Matrix::new_realize_workspace() to enable devirtualization.

◆ new_known_workspace()

template<class EigenVector_ , class EigenMatrix_ , class ValueArray_ , class IndexArray_ , class PointerArray_ >

auto irlba::ParallelSparseMatrix< EigenVector_, EigenMatrix_, ValueArray_, IndexArray_, PointerArray_ >::new_known_workspace ( ) const

inline

Overrides Matrix::new_workspace() to enable devirtualization.

◆ new_realize_workspace()

template<class EigenVector_ , class EigenMatrix_ , class ValueArray_ , class IndexArray_ , class PointerArray_ >

std::unique_ptr< RealizeWorkspace< EigenMatrix_ > > irlba::ParallelSparseMatrix< EigenVector_, EigenMatrix_, ValueArray_, IndexArray_, PointerArray_ >::new_realize_workspace ( ) const

inlinevirtual

Returns: Pointer to a new workspace for matrix realization. The lifetime of this object should not exceed that of its parent Matrix.

Implements irlba::Matrix< EigenVector_, EigenMatrix_ >.

◆ new_workspace()

template<class EigenVector_ , class EigenMatrix_ , class ValueArray_ , class IndexArray_ , class PointerArray_ >

std::unique_ptr< Workspace< EigenVector_ > > irlba::ParallelSparseMatrix< EigenVector_, EigenMatrix_, ValueArray_, IndexArray_, PointerArray_ >::new_workspace ( ) const

inlinevirtual

Returns: Pointer to a new workspace for matrix multiplication. The lifetime of this object should not exceed that of its parent Matrix.

Implements irlba::Matrix< EigenVector_, EigenMatrix_ >.

◆ rows()

template<class EigenVector_ , class EigenMatrix_ , class ValueArray_ , class IndexArray_ , class PointerArray_ >

Eigen::Index irlba::ParallelSparseMatrix< EigenVector_, EigenMatrix_, ValueArray_, IndexArray_, PointerArray_ >::rows ( ) const

inlinevirtual

Returns: Number of rows in the matrix.

Implements irlba::Matrix< EigenVector_, EigenMatrix_ >.

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

irlba/Matrix/sparse.hpp

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ PointerType

Constructor & Destructor Documentation

◆ ParallelSparseMatrix() [1/2]

◆ ParallelSparseMatrix() [2/2]

Member Function Documentation

◆ cols()

◆ get_indices()

◆ get_pointers()

◆ get_primary_boundaries()

◆ get_secondary_boundaries()

◆ get_secondary_nonzero_boundaries()

◆ get_values()

◆ new_adjoint_workspace()

◆ new_known_adjoint_workspace()

◆ new_known_realize_workspace()

◆ new_known_workspace()

◆ new_realize_workspace()

◆ new_workspace()

◆ rows()