Semiring< _OP1, _OP2, _ID1, _ID2 > Class Template Reference

A generalised semiring. More...

Public Types
typedef Monoid< _OP1, _ID1 >	AdditiveMonoid
	The additive monoid type. More...
typedef _OP1	AdditiveOperator
	The additive operator type. More...
typedef _OP2::D1	D1
	The first input domain of the multiplicative operator. More...
typedef _OP2::D2	D2
	The second input domain of the multiplicative operator. More...
typedef _OP2::D3	D3
	The output domain of the multiplicative operator. More...
typedef _OP1::D2	D4
	The second input domain of the additive operator. More...
typedef Monoid< _OP2, _ID2 >	MultiplicativeMonoid
	The multiplicative monoid type. More...
typedef _OP2	MultiplicativeOperator
	The multiplicative operator type. More...
template<typename OneType >
using	One = _ID2< OneType >
	The identity under multiplication. More...
template<typename ZeroType >
using	Zero = _ID1< ZeroType >
	The identity under addition. More...

Public Member Functions
AdditiveMonoid	getAdditiveMonoid () const
	Retrieves the underlying additive monoid. More...
AdditiveOperator	getAdditiveOperator () const
	Retrieves the underlying additive operator. More...
MultiplicativeMonoid	getMultiplicativeMonoid () const
	Retrieves the underlying multiplicative monoid. More...
MultiplicativeOperator	getMultiplicativeOperator () const
	Retrieves the underlying multiplicative operator. More...
template<typename D >
D	getOne () const
	Sets the given value equal to one, corresponding to this semiring. More...
template<typename D >
D	getZero () const
	Retrieves the zero corresponding to this semiring. More...

Static Public Attributes
static constexpr size_t	blocksize
	Blocksize for element-wise multiply-adds. More...
static constexpr size_t	blocksize_add
	Blocksize for element-wise addition. More...
static constexpr size_t	blocksize_mul
	Blocksize for element-wise multiplication. More...

Detailed Description

template<class _OP1, class _OP2, template< typename > class _ID1, template< typename > class _ID2>
class grb::Semiring< _OP1, _OP2, _ID1, _ID2 >

A generalised semiring.

This semiring works with the standard operators provided in grb::operators as well as with standard identities provided in grb::identities.

Operators

An operator OP here is of the form \( f:\ D_1 \times D_2 \to D_3 \); i.e., it has a fixed left-hand input domain, a fixed right-hand input domain, and a fixed output domain.

A generalised semiring must include two operators; an additive operator, and a multiplicative one:

1. \( \oplus: \ D_1 \times D_2 \to D_3 \), and
2. \( \otimes:\ D_4 \times D_5 \to D_6 \).

By convention, primitives such as grb::mxv will feed the output of the multiplicative operation to the additive operator as left-hand side input; hence, a valid semiring must have \( D_6 = D_1 \). Should the additive operator reduce several multiplicative outputs, the thus-far accumulated value will thus be passed as right-hand input to the additive operator; hence, a valid semiring must also have \( D_2 = D_3 \).

If these constraints on the domains do not hold, attempted compilation will result in a clear error message.

A semiring, in our definition here, thus in fact only defines four domains. We may thus rewrite the above definitions of the additive and multiplicative operators as:

1. \( \otimes:\ D_1 \times D_2 \to D_3 \), and
2. \( \oplus: \ D_3 \times D_4 \to D_4 \).

Identities

There are two identities that make up a generalised semiring: the zero- identity and the one-identity. These identities must be able to instantiate values for different domains, should indeed the four domains a generalised semiring operates on differ.

Specifically, the zero-identity may be required for any of the domains the additive and multiplicative operators employ, whereas the one-identity may only be required for the domains the multiplicative operator employs.

Standard examples

An example of the standard semiring would be: grb::Semiring< grb::operators::add< double, double, double >, grb::operators::mul< double, double, double >, grb::identities::zero, grb::identitites::one

realSemiring;

In this standard case, all domains the operators the semiring comprises are equal to one another. GraphBLAS supports the following shorthand for this special case: grb::Semiring< grb::operators::add< double >, grb::operators::mul< double >, grb::identities::zero, grb::identities::one

realSemiring;

As another example, consider min-plus algebras. These may be used, for example, for deriving shortest paths through an edge-weighted graph: grb::Semiring< grb::operators::min< unsigned int >, grb::operators::add< unsigned int >, grb::identities::negative_infinity, grb::identities::zero

minPlus;

CMonoid-categories

While in these standard examples the relation to standard semirings as defined in mathematics apply, the possiblity of having differing domains that may not even be subsets of one another makes the above sketch generalisation incompatible with the standard notion of semirings.

Our notion of a generalised semiring indeed is closer to what one might call CMonoid-categories, i.e. categories enriched in commutative monoids. Such CMonoid-categories are specified by some data, and are required to satisfy certain algebraic (equational) laws, thus being well-specified mathematical objects.

Additionally, such CMonoid-categories encapsulate the definition of semirings, vector spaces, left modules and right modules.

The full structure of a CMonoid-category C is specified by the data:

1. a set ob(C) of so-called objects,
2. for each pair of objects a,b in ob(C), a commutative monoid (C(a,b), 0_{a,b}, +_{a,b}),
3. for each triple of objects a,b,c in ob(C), a multiplication operation ._{a,b,c} : C(b,c) x C(a,b) -> C(a,c), and
4. for each object a in ob(C), a multiplicative identity 1_a in C(a,a).

This data is then required to specify a list of algebraic laws that essentially capture:

1. (that the (C(a,b), 0_{a,b}, +_{a,b}) are commutative monoids)
2. joint associativity of the family of multiplication operators,
3. that the multiplicative identities 1_a are multiplicative identities,
4. that the family of multiplication operators ._{a,b,c} distributes over the family of addition operators +_{a,b} on the left and on the right in an appropriate sense, and
5. left and right annihilativity of the family of additive zeros 0_{a,b}.

Generalised semirings in terms of CMonoid-categories

The current notion of generalised semiring is specified by the following data:

1. operators OP1, OP2,
2. the four domains those operators are defined on,
3. an additive identity ID1, and
4. a multiplicative identity ID2.

The four domains correspond to the choice of a CMonoid-category with two objects; e.g., \( ob(C)=\{a,b\} \). This gives rise to four possible pairings of the objects, including self-pairs, that correspond to the four different domains.

CMonoid-categories then demand an additive operator must exist that operates purely within each of the four domains, when combined with a zero identity that likewise must exist in each of the four domains. None of these additive operators in fact matches with the generalised semiring's additive operator.

CMonoid-categories also demand the existance of six different multiplicative operators that operate on three different domains each, that the composition of these operators is associative, that these operators distribute over the appropriate additive operators, and that there exists an multiplicative identity over at least one of the input domains.

One of these six multiplicative operators is what appears in our generalised semiring. We seem to select exactly that multiplicative operator for which both input domains have an multiplicative identity.

Finally, the identities corresponding to additive operators must act as annihilators over the matching multiplicative operators.

Full details can be found in the git repository located here: https://gitlab.huaweirc.ch/abooij/semirings

Template Parameters

_OP1	The addition operator.
_OP2	The multiplication operator.
_ID1	The identity under addition (the ‘0’).
_ID2	The identity under multiplication (the ‘1’).

Member Typedef Documentation

AdditiveMonoid

typedef Monoid< _OP1, _ID1 > AdditiveMonoid

The additive monoid type.

AdditiveOperator

typedef _OP1 AdditiveOperator

The additive operator type.

D1

typedef _OP2::D1 D1

The first input domain of the multiplicative operator.

D2

typedef _OP2::D2 D2

The second input domain of the multiplicative operator.

D3

typedef _OP2::D3 D3

The output domain of the multiplicative operator.

The first input domain of the additive operator.

D4

typedef _OP1::D2 D4

The second input domain of the additive operator.

The output domain of the additive operator.

MultiplicativeMonoid

typedef Monoid< _OP2, _ID2 > MultiplicativeMonoid

The multiplicative monoid type.

MultiplicativeOperator

typedef _OP2 MultiplicativeOperator

The multiplicative operator type.

One

using One = _ID2< OneType >

The identity under multiplication.

Zero

using Zero = _ID1< ZeroType >

The identity under addition.

Member Function Documentation

getAdditiveMonoid()

AdditiveMonoid getAdditiveMonoid ( ) const

inline

Retrieves the underlying additive monoid.

Returns

The underlying monoid. Any state is copied.

getAdditiveOperator()

AdditiveOperator getAdditiveOperator ( ) const

inline

Retrieves the underlying additive operator.

Returns

The underlying operator. Any state is copied.

getMultiplicativeMonoid()

MultiplicativeMonoid getMultiplicativeMonoid ( ) const

inline

Retrieves the underlying multiplicative monoid.

Returns

The underlying monoid. Any state is copied.

getMultiplicativeOperator()

MultiplicativeOperator getMultiplicativeOperator ( ) const

inline

Retrieves the underlying multiplicative operator.

Returns

The underlying operator. Any state is copied.

getOne()

D getOne ( ) const

inline

Sets the given value equal to one, corresponding to this semiring.

The identity value will be cast to the requested domain.

Template Parameters

D	The requested domain of the one. The arbitrary choice for the default return type is D1– the reasoning being to simply have the same default type as getZero().

Returns

The one corresponding to this semiring, cast to the requested domain.

getZero()

D getZero ( ) const

inline

Retrieves the zero corresponding to this semiring.

The zero value will be cast to the requested domain.

Template Parameters

D	The requested domain of the zero. The arbitrary choice for the default return type is D1– inspired by the regularly occurring expression \( a_{ij}x_j \) where often the left- hand side is zero.

Returns

The zero corresponding to this semiring, cast to the requested domain.

Member Data Documentation

blocksize

constexpr size_t blocksize

static

Initial value:

= blocksize_mul < blocksize_add
            ? blocksize_mul
            : blocksize_add

Blocksize for element-wise multiply-adds.

blocksize_add

constexpr size_t blocksize_add

static

Initial value:

= D3_bsz < D4_bsz
            ? D3_bsz
            : D4_bsz

Blocksize for element-wise addition.

blocksize_mul

constexpr size_t blocksize_mul

static

Initial value:

= mul_input_bsz < D3_bsz
            ? mul_input_bsz
            : D3_bsz

Blocksize for element-wise multiplication.

---

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

• semiring.hpp