matrices< D, mode, backend, RIT, CIT, NIT > Class Template Reference

Factories for creating ALP/GraphBLAS matrices with standard patterns such as identity matrices. More...

Static Public Member Functions
static MatrixType	dense (const size_t m, const size_t n, const D value)
	Builds a dense matrix filled with a given value. More...
template<typename Semiring = grb::Semiring< grb::operators::add< D >, grb::operators::mul< D >, grb::identities::zero, grb::identities::one >>
static MatrixType	dense (const MatrixType &A, const Semiring &ring=Semiring())
	Builds a dense matrix from a given matrix. More...
template<class ValueIterator >
static MatrixType	diag (const size_t m, const size_t n, const ValueIterator values, const ValueIterator valEnd, const long k=static_cast< long >(0))
	Builds a diagonal matrix with the given values. More...
static MatrixType	empty (const size_t m, const size_t n)
	Builds an empty matrix, without any values. More...
static MatrixType	eye (const size_t m, const size_t n, const D value=static_cast< D >(1), const long k=static_cast< long >(0))
	Builds a diagonal matrix. More...
static MatrixType	eye (const size_t n)
	Builds a diagonal matrix. More...
static MatrixType	full (const size_t m, const size_t n, const D value)
	Builds a dense matrix filled with a given value. More...
template<typename Semiring = grb::Semiring< grb::operators::add< D >, grb::operators::mul< D >, grb::identities::zero, grb::identities::one >>
static MatrixType	identity (const size_t n, const Semiring &ring=Semiring())
	Builds an identity matrix. More...
template<typename Semiring = grb::Semiring< grb::operators::add< D >, grb::operators::mul< D >, grb::identities::zero, grb::identities::one >>
static MatrixType	ones (const size_t m, const size_t n, const Semiring &ring=Semiring())
	Builds a matrix filled with ones. More...
template<typename Semiring = grb::Semiring< grb::operators::add< D >, grb::operators::mul< D >, grb::identities::zero, grb::identities::one >>
static MatrixType	zeros (const size_t m, const size_t n, const Semiring &ring=Semiring())
	Builds a matrix filled with zeros. More...

Detailed Description

template<typename D, grb::IOMode mode = grb::PARALLEL, grb::Backend backend = grb::config::default_backend, typename RIT = grb::config::RowIndexType, typename CIT = grb::config::ColIndexType, typename NIT = grb::config::NonzeroIndexType>
class grb::algorithms::matrices< D, mode, backend, RIT, CIT, NIT >

Factories for creating ALP/GraphBLAS matrices with standard patterns such as identity matrices.

Just as with constructing any ALP container, the use of factory functions, when an error is encountered, results in C++ exceptions being thrown.

The capacity of returned matrices is requested at the exact minimum that is required. As per the core ALP/GraphBLAS specification, this means that the returned matrices have a capacity of at least the minimum required; i.e., assert( grb::nnz(R) <= grb::capacity(R) ); holds, with R the returned matrix.

In the case of an ALP process with multiple user processes, calling any factory method is a collective call. ALP guarantees that if a call fails at one user process, the call also fails at all other user processes, with matching exceptions. The matrix factory is scalable in the number of threads as well as the number of user processes.

The following matrix factory methods are supported:

1. diag,
2. empty,
3. eye,
4. identity,
5. full,
6. dense,
7. ones, and
8. zeros.

All these methods are implemented on top of core ALP primitives.

Template Parameters

D	The type of a non-zero element of the returned matrices.

When passing void to D, the returned matrices will be pattern matrices.

Template Parameters

mode	The I/O mode to be used when constructing matrices. Optional; default is grb::PARALLEL.

Warning

At present, diag for non-pattern matrices is only supported for sequential I/O. Please append to GitHub issue #238 if you require this functionality so that we may prioritise it higher.

The remainder template parameters are automatically inferred and should only be overridden by an expert user:

Template Parameters

backend	The selected backend.
RIT	The type used for row indices.
CIT	The type used for column indices.
NIT	The type used for non-zero indices.

Performance semantics

While the implementation of all factory methods guarantee their construction within \( \Theta(1) \) work-space, the involved work and data movement are \( \mathcal{O}(n+m) \) instead, where \( n \) is the maximum matrix dimension and \( m \) the number of nonzeroes in the produced matrix.

In case of a shared-memory parallel backend with \( T \) threads, the thread-local work and data movement become \( \mathcal{O}((n+m)/T+T) \). System-wide compute costs thus are proportional to \( \mathcal{O}(m+n)/T+T \) while system-wide data movement costs remain proportional to \( \mathcal{O}(m+n+T) \), with usually \( m+n \gg T \). The work-space cost remains \( \Theta(1) \).

In case of a distributed-memory parallel backend and use of this factory class in grb::PARALLEL I/O mode over \( P \) user processes with \( T_s \) threads at user process \( s \), thread-local work and data movement become \( \mathcal{O}((n+m)/(T_sP)+T_s+P) \). System-wide compute costs thus are proportional to \( \mathcal{O}(\min_s (m+n)/(T_sP) + \max_s T_s + P), \) while system-wide data movement costs are proportional to \( \mathcal{O}((m+n)/P + \max_s T_s + P). \) The work-space costs are \( \Theta( P ) \).

In sequential I/O mode, we give only the system-wide costing for brevity:

1. \( \mathcal{O}( \min m+n / T_s + \max T_s + P ) \) work;
2. \( \mathcal{O}( m + n + \max T_s + P ) \) data movement;
3. \( \Theta( P ) \) work-space.

Warning

Thus, the use of the sequential I/O mode is never scalable in \( P \) and discouraged always.

See also

grb::IOMode for a more in-depth description of sequential (versus parallel) I/O semantics.

Note

This analysis assumes bandwidth is shared amongst all threads in a shared-memory system, whereas each user process has exclusive use of its memory controllers. These assumptions require properly configured execution environments.

A note on aliases

Different from core primitives, the goal for this factory class is to provide productive tools. This goal differs from the core primitives which aim to provide some minimal set of primitives that allow efficient implementation of the widest possible range of algorithms.

Given this difference in end-goal, maintaining multiple aliases for this factory class – or indeed for algorithms in general – are hence encouraged, as long as they indeed increase productivity.

Member Function Documentation

dense() [1/2]

static MatrixType dense ( const size_t  m, const size_t  n, const D  value  )

inlinestatic

Builds a dense matrix filled with a given value.

Note

This is an alias for full – see that function for complete documentation.

Parameters

[in]	m	The number of rows of the matrix.
[in]	n	The number of columns of the matrix.
[in]	value	The value of each non-zero element.

Returns

The requested dense matrix.

dense() [2/2]

static MatrixType dense ( const MatrixType &  A, const Semiring &  ring = Semiring()  )

inlinestatic

Builds a dense matrix from a given matrix.

Indended for converting sparse input matrices to a dense format. Assumes numerical data types, and that entries previously not set by the input matrix, will equal zero in the returned matrix.

While not strictly a factory constructor, the definition of the above dense function does most likely raise the user expectation that the functionality provided by this method is available.

Parameters

[in]	A	The (sparse) input matrix.
[in]	ring	The semiring in case 'zero' is not intended to be the standard numerical zero. This argument is optional; by default, the numerical zero will be used.

Note

In case of non-numerical D, ring becomes a mandatory argument.

Returns

The matrix A converted to a dense format. More precisely, entries \( a_{ij} \in A \) will equal that of the returned matrix at position \( (i, j) \). Coordinates $(k, l)$ for which no entry \( a_{kl} \) existed in \( A \) will have value 0 in the returned matrix.

diag()

static MatrixType diag ( const size_t  m, const size_t  n, const ValueIterator  values, const ValueIterator  valEnd, const long  k = static_cast< long >( 0 )  )

inlinestatic

Builds a diagonal matrix with the given values.

This function takes as input an iterator-pair over any STL-style container of diagonal values.

Template Parameters

ValueIterator

The type of the iterator used to provide the values. This iterator must be a forward iterator.

Warning

If ValueIterator is not also a random access iterator, then construction of the requested matrix cannot be parallelised.

The output matrix will contain \( q = \min\{ m, n \} \) non-zeroes or less if k is not zero.

Parameters

[in]	m	The number of rows of the matrix.
[in]	n	The number of columns of the matrix.
[in]	values	The iterator over the diagonal values.
[in]	valEnd	Iterator in end-position matching values.
[in]	k	The diagonal offset (default = 0). A positive value indicates an offset above the main diagonal, while a negative value indicates an offset below the main diagonal.

The distance between values and valEnd must be at least \( q \), or less if k is not zero.

If mode is grb::PARALLEL, then the union of elements spanned by values and valEnd across all user processes making a collective call to this function, comprises the set of all input values. If mode is grb::SEQUENTIAL, then the elements spanned at each user process comprises the set of all input values, and the complete set of inputs must match over all user processes. See also grb::IOMode.

Returns

The requested diagonal matrix.

Warning

This function is currently only implemented for sequential I/O.

empty()

static MatrixType empty ( const size_t  m, const size_t  n  )

inlinestatic

Builds an empty matrix, without any values.

Parameters

[in]	m	The requested number of rows of the returned matrix.
[in]	n	The requested number of columns of the returned matrix.

Returns

An empty matrix of the requested type.

eye() [1/2]

static MatrixType eye ( const size_t  m, const size_t  n, const D  value = static_cast< D >( 1 ), const long  k = static_cast< long >( 0 )  )

inlinestatic

Builds a diagonal matrix.

The output matrix will contain \( \min\{ m, n \} \) non-zero elements or less, if k is not zero.

Parameters

[in]	m	The number of rows of the matrix.
[in]	n	The number of columns of the matrix.
[in]	value	The value of each non-zero element.
[in]	k	The diagonal offset. A positive value indicates an offset above the main diagonal, while a negative value indicates an offset below the main diagonal.

Providing value equal to one, k equal to zero, and n equal to m, is equivalent to a default call to identity. Therefore, value, k, and n are defined as optional arguments to this function as well, with defaults one and zero, respectively.

Returns

The requested diagonal matrix.

eye() [2/2]

static MatrixType eye ( const size_t  n )

inlinestatic

Builds a diagonal matrix.

This provides the variant where all optional arguments are defaulted.

Parameters

[in]

n

The size of the output square diagonal matrix.

Returns

The requested square diagonal matrix.

full()

static MatrixType full ( const size_t  m, const size_t  n, const D  value  )

inlinestatic

Builds a dense matrix filled with a given value.

Note

ALP/GraphBLAS does not have efficient support for dense matrices– the dense data will be stored in a sparse format, which will not lead to efficient computations. See ALP/Dense for efficient dense linear algebra support.

Output matrix will contain \( mn \) non-zero elements.

Parameters

[in]	m	The number of rows of the matrix.
[in]	n	The number of columns of the matrix.
[in]	value	The value of each non-zero element.

Returns

The requested full matrix.

identity()

static MatrixType identity ( const size_t  n, const Semiring &  ring = Semiring()  )

inlinestatic

Builds an identity matrix.

Note

This is an alias for eye. It differs only in that this function does not allow for rectangular output, nor for non-identity values on the diagonal, nor for diagonal offsets.

See eye for detailed documentation.

Parameters

[in]	n	The size of the identity matrix to be returned.
[in]	ring	The semiring under which an identity matrix should be formed (optional – the default simply puts ones on the diagonal).

Note

For non-numerical D, the semiring default cannot be applied and ring becomes a mandatory argument.

Returns

The requested identity matrix.

ones()

static MatrixType ones ( const size_t  m, const size_t  n, const Semiring &  ring = Semiring()  )

inlinestatic

Builds a matrix filled with ones.

Note

This is an alias for full( m, n, 1 ).

See also

full for complete documentation.

Parameters

[in]	m	The number of rows of the matrix.
[in]	n	The number of columns of the matrix.
[in]	ring	The semiring under which a matrix of ones should be formed (optional – the default simply produces a matrix of numerical ones).

Note

For non-numerical D, the semiring default cannot be applied and ring becomes a mandatory argument.

Returns

Returns a dense matrix with entries one.

zeros()

static MatrixType zeros ( const size_t  m, const size_t  n, const Semiring &  ring = Semiring()  )

inlinestatic

Builds a matrix filled with zeros.

Note

This is an alias for factory::full( m, n, 0 )

See also

full for complete documentation.

Parameters

[in]	m	The number of rows of the matrix.
[in]	n	The number of columns of the matrix.
[in]	ring	The semiring under which a matrix of zeroes should be formed (optional – the default simply produces a matrix of numerical zeroes).

Note

For non-numerical D, the semiring default cannot be applied and ring becomes a mandatory argument.

Returns

A dense matrix of zeroes.

---

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

• matrix_factory.hpp