do we REQUIRE that multiplication distributes over addition?

[tgmattso]

In our definition of semiring (on line 455) we state that multiplication distributes over addition. But we do not enforce this. And with strange operators such as first and second, is distribution really supported?

[tgmattso]

Oh wait a minute ... I guess we deal with this by distinguishing between a mathematical semiring and a graphBLAS semiring.

[mcmillan03]

Summary: the property means that f1 = 2 x (4+3) is equal to f2 = 2 x 4 + 2 x 3. Also note that multiplication is not required to be commutative but the property should still hold (but order needs to be maintained):

If the semiring is Min-First (a GraphBLAS semiring) then: f1 = first(2, min(4, 3)) should equal f2 = min(first(2,4), first(2,3)). Both evaluate to 2. It seems like at least one GraphBLAS semiring adheres to the property, and that those using Second should also satisfy the property

What would it take for an operator to not adhere? If the multiply introduced a constant offset (like +1)?

For example, multiply op is f(a, b) = a x b + 1, and addition is f(a, b) = a + b then the above example evaluates as follows: f1 = 2 x (4+3) + 1 = 15 f2 = (2 x 4 + 1) + (2 x 3 + 1) = 16

Having said all that, how can this property be used within GraphBLAS methods and operations for advantage? I.e., when can one reduce the number of multiplies by applying this property? I would imagine it is only when you know you have a matrix or vector that only stores one value (an iso-matrix in Suitesparse lingo) and you can do the reduction on the other operand and apply the multiplication afterward. Are there other cases?

[DrTimothyAldenDavis]

I don't exploit this property. I exploit the iso case in other ways, but not this one.

Looking over all possible semirings that could be built from built-in operators, there are many for which multiplication does not distribute over the monoid. For example, the cases where the monoid is boolean but the inputs to the multiplicative op differ. Like the OR_LT_FP32 semiring for instance.

For some built-in semirings like PLUS_TIMES, there might be cases where I could consider this, when I know that semiring is a true mathematical semiring as compared to a more general GraphBLAS semiring, but I don't see much use for it.

[mcmillan03]

less_than(2, OR(4,3)) = false OR(less_than(2, 4), less_than(2, 3)) = true

[DrTimothyAldenDavis]

Right. This also changes typecasting (the input to OR(4,3) is not boolean), and typecasting doesn't distribute at all.

[mcmillan03]

Duplicate of previous issue. Reopening to resolve during meeting

[mcmillan03]

Duplicate of #27