GraphBLAS
GraphBLAS copied to clipboard
DrTimothyAldenDavis
findmax and findmin built-ins
I'd like to request the addition of two(+) binary operators/monoids, findmax and findmin which act like min and max but return the position of the max and min values. While argmin/argmax exist in the MATLAB library, this is slightly different.
My use case is something like FINDMAXJ_PLUS. The typical MAX_PLUS semiring results in C_ij = max_k(A_ik + B_kj). FINDMAXJ_PLUS would return set C_ij to be the k which is provided the result of max_k (hopefully that's clear).
This should be done for MIN and I (FINDMAXI) as well.
As far as I can tell this cannot be constructed as a user defined operator as of now. Do internal positional binary ops have access to the values as well? Or is there a different set of algorithms for positional and value based which makes this difficult?
It's currently not possible to create a user-defined positional binary op. Internally, built-in ops "can do anything" ... I just have to write the code to do it, and none of my specialized positional binary ops can do this. There is no function signature that handles this; my positional binary ops are GrB_BinaryOp objects.
There is a new GrB_IndexUnaryOp in the spec, which computes z = f (aij, i, j, thunk). It's like a selectop, but it can be used in more than just GrB_select. It can be used in GrB_apply as well.
It would be possible to consider an extension to this idea, a GxB_IndexBinaryOp, which would compute z = f (a_ia_ja, ia, ja, b_ib_jb, ib,jb, thunk), where A(ia,ja) is one entry and B(ib,jb) is another. This function signature could be used to return z as a pair of entries: (value,k) where you'd use k = ja or k = ib. Then a user-defined max monoid could be considered that operated on the user-data type (value,int64 k).
The GrB_Semiring would have to be extended so it can handle this GxB_BinaryIndexOp as the multiplicative operator.
This would be quite a lot of work to implement, however. All my extensive AxB kernels would have to change to accomodate this new kind of op, and the change is substantial.
Closing since this will be taken care of eventually by JIT and possibly Enzyme.
Let's keep this open so I don't forget. Creating semirings based on an index-binary operator (which would have access to the values aik, bkj, and the indices i,k,j) is very important. It will be a lot of work, but it would not require a JIT to get important cases to work with high performance.