search

DrTimothyAldenDavis / GraphBLAS

SuiteSparse:GraphBLAS: graph algorithms in the language of linear algebra. For production: (default) STABLE branch. Code development: ask me for the right branch before submitting a PR. video intro: https://youtu.be/Tj5y6d7FegI .
http://faculty.cse.tamu.edu/davis/GraphBLAS.html
Other
364 stars 63 forks source link

findmax and findmin built-ins #62

Open rayegun opened 3 years ago

rayegun commented 3 years ago

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?

DrTimothyAldenDavis commented 3 years ago

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.

rayegun commented 2 years ago

Closing since this will be taken care of eventually by JIT and possibly Enzyme.

DrTimothyAldenDavis commented 2 years ago

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.