Another example of extremal monoid is greatest common divisor, or gcd, which has a terminal value of 1.

I don't understand the difference between extremal and terminal.

They look the same to me from your description

How about times on int8? The identity value is 1 and the 'terminal value' (my terminology) is zero. Isn't that also an extremal monoid?

Your definition of extremal:

Suppose we reduce a set of values S = {s_0, s_1, ...} with a monoid op and get the result x. x is "extremal" if op(x, s_i) == x for all s_i in S.

is the same as my definition of a terminal monoid, whose terminal value is x.

Perhaps. My definition isn't strict/complete yet (note I didn't say iff). I want to exclude nan for e.g. times on FP. nan as a terminal value satisfies the definition above if nan is in the set of values S.

Maybe I should change my definition of extremal to say that that property should hold for all possible sets S.

Having a terminal value seems weaker--what if there is a sentinel value like nan, or a terminal value such as 0 for times like you mentioned?

But for all possible sets, the terminal value x has that same property as your extremal value.

Technically, the PLUS monoid on FP32 is terminal, with the terminal value of NAN, but it's not worth exploiting since it would be rare in practice, so I ignore it.

Are you wanting to place all the elements in the domain in some kind of order? First, second 3rd, ....last, where " < " can be applied, first < 2nd < 3rd < ... < last, and where "first" is the identity and "last" is the terminal value? Or visa versa?

That would be fine for some data types but not all (complex numbers cannot be ordered).

For the NAN terminal value of PLUS on FP32, you cannot say that NAN appears anywhere in the order of all possible 2^32 floating point values: -INF, -INF+eps, ..., 0, eps, .... , +INF.

But for all possible sets, the terminal value x has that same property as your extremal value.

No it doesn't. By my construction, x is the result of reducing a set S with a monoid. This is not necessarily the terminal value, which we can call t. If t is contained within the set S, then x will be t.

Are you wanting to place all the elements in the domain in some kind of order?

No, that shouldn't be necessary.

Here's an example of what I want: when reducing a symmetric matrix, I want to know if I can get the same result by e.g. reducing just the lower triangle. This is coming up a fair amount for computing and caching properties in graphblas-algorithms (so this may someday be useful for LAGraph too).

Oh, I see. Then you want to know if a monoid has the form "given a set S, pick one of the items, and that's the result of applying the monoid to reduce that set S to a scalar"?

So the PLUS or TIMES monoid would not have that property. MIN and MAX would. I guess boolean AND and OR would too. The bitwise BAND and BOR would not have this property.

I don't understand why "extremal" is the word to use since to me that implies something else.

Is that the property you're looking for?

I think that's close. I would like to include BAND and BOR though, which means the result x does not need to appear in the set S.

heh, okay, so maybe this isn't the most intuitive property. I'll just special-case what I want in graphblas-algorithms for now, and we'll see how that goes.

Thanks for chiming in @DrTimothyAldenDavis.

Let me try a different explanation that is closer to what I actually want this for.

A monoid op is "foo" (the property I want to name) if reducing any nonempty set S with unique values gives the same result as reducing a multiset that contains the same elements as S but with arbitrary multiplicity. For example, S = {a, b, c}, MS = {a, a, b, b, b, c}, and op.reduce(S) == op.reduce(MS).

I see. Then it would hold for the MAX, MIN, LAND, LOR, BAND, BOR, moniods, and ANY if you like (why not ... the definition of ANY would be fine with that since the set of choices are the same).

It would not hold for PLUS, TIMES, LXOR, BXOR, LXNOR, BXNOR monoids.

I don't know what the name "foo" would be, but "extremal" would be confusing.

This categorization seems most useful on your side, not inside GraphBLAS, since I can't detect this condition (that I'm reducing a set with duplicates in it). I don't keep track of whether or not my matrices are symmetric for example.

I DO keep track of the iso property, and exploit it heavily for all monoids, semirings, and binary ops. In particular, reducing a matrix with N entries to a scalar takes O(log N) time, for any monoid (with "foo" property or not):
https://github.com/DrTimothyAldenDavis/GraphBLAS/blob/stable/Source/GB_iso_reduce_worker.c

That's a very special set where all the values are identical (n copies of the value a). Some monoids (those that are "foo") could do that in O(1) time, but O(log(N)) is fast enough, and the method works for all monoids, even user-defined ones.

Yeah, I agree "extremal" is a terrible name.

I believe is_idempotent is the property I'm looking for. An idempotent monoid is one for which op(x, x) == x for all possible x. This is related to the common meaning of idempotency, which is f(f(x)) == f(x): we can define f(x) := op(x, x), so f(f(x)) == f(x) is indeed true when op is an idempotent monoid.