"ZEROB" Binary Operator

[eriknw]

I think it would be useful to have a "pair"-like binary operator that returns 0 instead of 1. The C spec uses "ONEB" instead of "PAIR", so perhaps "ZEROB" is an okay name.

This is known to be missing in this table:

GraphBLAS/Include/GraphBLAS.h

Lines 1442 to 1468 in 502e16a

	// is complete. Below is a list of all operators and their equivalents.
	// x: 0 0 1 1
	// y: 0 1 0 1
	// z: see below
	//
	// z = 0 0 0 0 0 (zero function, not predefined)
	// z = (x && y) 0 0 0 1 AND, MIN, TIMES
	// z = (x > y) 0 0 1 0 GT, ISGT, and set diff (x\y)
	// z = x 0 0 1 1 FIRST, DIV
	//
	// z = (x < y) 0 1 0 0 LT, ISLT, and set diff (y\x)
	// z = y 0 1 0 1 SECOND, RDIV
	// z = (x != y) 0 1 1 0 XOR, MINUS, RMINUS, NE, ISNE
	// z = (x || y) 0 1 1 1 OR, MAX, PLUS
	//
	// z = ~(x || y) 1 0 0 0 (nor(x,y) function, not predefined)
	// z = (x == y) 1 0 0 1 LXNOR, EQ, ISEQ
	// z = ~y 1 0 1 0 (not(y), not predefined)
	// z = (x >= y) 1 0 1 1 GE, ISGE, POW, and "x implies y"
	//
	// z = ~x 1 1 0 0 (not(x), not predefined)
	// z = (x <= y) 1 1 0 1 LE, ISLE, and "y implies x"
	// z = ~(x && y) 1 1 1 0 (nand(x,y) function, not predefined)
	// z = 1 1 1 1 1 PAIR, ONEB
	//
	// z = any(x,y) 0 . . 1 ANY (pick x or y arbitrarily)

"Why?", you ask? I want to use GxB_Vector_sort and GxB_Matrix_sort to "compactify" the values to the left or top. When using GxB_PAIR_BOOL, the values are reversed. The values would not be reversed with GxB_ZEROB_BOOL. Is this abusing the sort functions? Maybe :-P

I don't see any reason for building predefined semirings with ZEROB instead of PAIR.

[DrTimothyAldenDavis]

I hadn't thought of what happens when GrB_ONEB_* or GxB_PAIR_* is used as a comparator. I think the current behavior with GrB_ONEB_BOOL (aka GxB_PAIR_BOOL) is just an accident. This is because !(a < b) is not the same as (a >= b) for this ZERO_BOOL operator. I kind of assume the comparator "works", and that the values being sorted have a global ordering.

In other words, if op(x,y) is the comparator, I could assume that if x is not equal to y, that op(x,y) should be the same as !op(y,x). I don't use that condition, but I think the sort would only be defined if that condition is always true for the given op and the data types that are being sorted.

That's why I don't have a sort for complex values, for example. It's possible to define a total ordering of complex numbers, like MATLAB does, but that's not conventional and I think it's a mistake for MATLAB to do that.

In any case, using GxB_PAIR_BOOL doesn't trigger a "built-in" sort, but treats the operator as if it were user-defined anyway, and calls the "generic" method to sort a matrix or vector where the function pointer from the op is used.

So it would be just as fast if you were to create your own user-defined ZERO_BOOL operator. And just as undefined as the current behavior with GrB_ONEB_BOOL.

I do like the idea of fleshing out the table of all-possible binary boolean operators (adding ZERO, NOR, NOT(y), NOT(x), and NAND). But adding them (and ZERO in particular) wouldn't help with the sort. The sort would still be relying on undefined behavior.

For the "compactify" behavior, it might make more sense to have this as an entirely different function, or to have a comparator function that is a GrB_IndexBinaryOp. All the op would do is to say that the comparison of A(i1,j1) and A(i2,j2) is the test "j1 < j2". That would give you "compactify" by column. Now all we need are GrB_IndexBinaryOps.

[eriknw]

Thanks for the reply.

Heh, yeah, I thought this might be abusing GxB_sort. Good to know this is undefined behavior.

I really like your idea of using a IndexBinaryOp to do what I want. +1 for IndexBinaryOp.

And I agree that you don't want to sort complex with e.g. LT. Python doesn't allow this either. I think it's best to require a user-defined function if users want to sort complex.

[DrTimothyAldenDavis]

I should mention the undefined behavior in the user guide. I don't plan on changing GxB_sort to modify this behavior though, so your use of GxB_sort to do the compactify will work just fine, for a long time. It might always work, even after I add GrB_IndexBinaryOps.