ALP User Documentation 0.7.0
Algebraic Programming User Documentation

A generalised semiring. More...
#include <semiring.hpp>
Public Types  
typedef Monoid< _OP1, _ID1 >  AdditiveMonoid 
The additive monoid type.  
typedef _OP1  AdditiveOperator 
The additive operator type.  
typedef _OP2::D1  D1 
The first input domain of the multiplicative operator.  
typedef _OP2::D2  D2 
The second input domain of the multiplicative operator.  
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.  
typedef _OP2  MultiplicativeOperator 
The multiplicative operator type.  
template<typename OneType >  
using  One = _ID2< OneType > 
The identity under multiplication.  
template<typename ZeroType >  
using  Zero = _ID1< ZeroType > 
The identity under addition.  
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 >  
constexpr D  getOne () const 
Sets the given value equal to one, corresponding to this semiring. More...  
template<typename D >  
constexpr D  getZero () const 
Retrieves the zero corresponding to this semiring. More...  
Static Public Attributes  
static constexpr size_t  blocksize = blocksize_mul < blocksize_add ? blocksize_mul : blocksize_add 
Blocksize for elementwise multiplyadds.  
static constexpr size_t  blocksize_add = D3_bsz < D4_bsz ? D3_bsz : D4_bsz 
Blocksize for elementwise addition.  
static constexpr size_t  blocksize_mul = mul_input_bsz < D3_bsz ? mul_input_bsz : D3_bsz 
Blocksize for elementwise multiplication.  
A generalised semiring.
This semiring works with the standard operators provided in grb::operators as well as with standard identities provided in grb::identities.
An operator OP here is of the form \( f:\ D_1 \times D_2 \to D_3 \); i.e., it has a fixed lefthand input domain, a fixed righthand input domain, and a fixed output domain.
A generalised semiring must include two operators; an additive operator, and a multiplicative one:
By convention, primitives such as grb::mxv will feed the output of the multiplicative operation to the additive operator as lefthand side input; hence, a valid semiring must have \( D_6 = D_1 \). Should the additive operator reduce several multiplicative outputs, the thusfar accumulated value will thus be passed as righthand 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:
There are two identities that make up a generalised semiring: the zero identity and the oneidentity. These identities must be able to instantiate values for different domains, should indeed the four domains a generalised semiring operates on differ.
Specifically, the zeroidentity may be required for any of the domains the additive and multiplicative operators employ, whereas the oneidentity may only be required for the domains the multiplicative operator employs.
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 minplus algebras. These may be used, for example, for deriving shortest paths through an edgeweighted graph: grb::Semiring< grb::operators::min< unsigned int >, grb::operators::add< unsigned int >, grb::identities::negative_infinity, grb::identities::zero
minPlus;
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 CMonoidcategories, i.e. categories enriched in commutative monoids. Such CMonoidcategories are specified by some data, and are required to satisfy certain algebraic (equational) laws, thus being wellspecified mathematical objects.
Additionally, such CMonoidcategories encapsulate the definition of semirings, vector spaces, left modules and right modules.
The full structure of a CMonoidcategory C is specified by the data:
This data is then required to specify a list of algebraic laws that essentially capture:
The current notion of generalised semiring is specified by the following data:
The four domains correspond to the choice of a CMonoidcategory with two objects; e.g., \( ob(C)=\{a,b\} \). This gives rise to four possible pairings of the objects, including selfpairs, that correspond to the four different domains.
CMonoidcategories 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.
CMonoidcategories 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
_OP1  The addition operator. 
_OP2  The multiplication operator. 
_ID1  The identity under addition (the ‘0’). 
_ID2  The identity under multiplication (the ‘1’). 
typedef _OP2::D3 D3 
The output domain of the multiplicative operator.
The first input domain of the additive operator.
typedef _OP1::D2 D4 
The second input domain of the additive operator.
The output domain of the additive operator.

inline 
Retrieves the underlying additive monoid.

inline 
Retrieves the underlying additive operator.

inline 
Retrieves the underlying multiplicative monoid.

inline 
Retrieves the underlying multiplicative operator.

inlineconstexpr 
Sets the given value equal to one, corresponding to this semiring.
The identity value will be cast to the requested domain.
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(). 

inlineconstexpr 
Retrieves the zero corresponding to this semiring.
The zero value will be cast to the requested domain.
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. 