Add support for GrB_select #147

Activity

1. eriknw commented on Jan 21, 2022

   

   eriknw

   on Jan 21, 2022

   Last edited by eriknw

   Member

   More actions

   Yes! This is the main missing piece in grblas.

   Primary usage of select:

   • grblas.selectop.tril
     • or grblas.indexunary
   • A.select(selectop, k)
   • Auto-convert op.gt to selectop.gt where appropriate
     • This means allowing A[op.gt(A, 1)] and A[1 > A]
   • A[A < 1]
   • op.tril(A, 1)
   • A[op.tril(A, 1)]
   • User-defined select ops

   Also support:

   • A[B < 1]
   • A[(A > 1) & (A < 10)]
   • A(B.S & C.S | D.V) # set logic for masks
     • Don't support B.V - C.V yet--need to work through
   • Need to explore:
     • A[A > 1] = x
     • A(M.S)[A > 1] = x
     • Adding a "strict" config to not include recipes such as these
   • Support masks as values
     • C << A.S | B
   • Similarly, perhaps support bool dtype as value masks
     • C(B) << expr
     • More generally, allow masks and bool matrices to be used interchangeably

   SelectOps:

   • tril
   • triu
   • diag
   • offdiag
   • eq
   • ne
   • lt
   • gt
   • ge
   • row_index
   • col_index
   • diag_index
   • col_le
   • col_gt
   • row_le
   • row_gt

   Additional GxB SelectOps:

   • nonzero
   • eq0
   • gt0
   • ge0
   • lt0
   • le0
   • Should we expose these?
   • Should we use them when the scalar thunk is 0?

   This is just a plan/sketch. I wouldn't be surprised if we're missing edge cases and need to do some things a little differently.
2. eriknw

   added

   featureSomething is missingSomething is missing

   on Mar 17, 2022
3. jim22k commented on Apr 5, 2022

   

   jim22k

   on Apr 5, 2022

   MemberAuthor

   More actions

   Lots of thoughts after spending half a day thinking about this. I'll try to break my ideas into logical sections.

   Two different kinds of IndexUnaryOps

   Some of the predefined IndexUnaryOps (row_index, col_index, diag_index) only make sense in the context of apply because they do not return bool.

   Let's separate these 3 to live in grblas.unary and all others live in grblas.select.

   grblas.select namespace

   This will function both as a namespace for ops and as a pseudo-function call.

   Rather than calling

   A.select(gb.op.tril)

   We will instead call

   gb.select.tril(A)

   This makes it behave like many of our other ops where the specific function is front-and-center to the call.

   However, while our other ops have symbols to help distinguish them (@ for mxm, & for ewise_mult, | for ewise_add), it could be difficult to quickly distinguish an apply from select. By not including selectops in the main ops namespace, it encourages users to call them as gb.select.<opname>, making it more apparent what is actually happening.

   gb.select.triu(A, 1)  # TRIL with thunk=1
   gb.select.diag(A)  # DIAG with thunk=0
   gb.select.offdiag(A)  # OFFDIAG with thunk=0

   The row, column, and value ops can be made more elegant by accepting delayed comparators.

   gb.select.value(A<=5)  # VALUELE with thunk=5
   gb.select.row(A>3)  #ROWGT with thunk=3
   gb.select.col(A<2)  #COLLE with thunk=1 (because only COLLE and COLGT exist)

   What about A[A<1]?

   I went back and forth on this and decided that it causes too much confusion with extract. Both select and extract have obvious similarities, but one key difference is that indices are reindexed when doing extract, but not when doing select.

   So I am voting against using [] for select to avoid any confusion. Square brackets are only for extract and assign.

   And while A[A<1] is very elegant, it requires stating A twice. We would run into the same issue if we did something like A.select(A<1). But select.value(A<1) reads nicely and doesn't require any repeat.

   What about using B.S in select?

   A[B<1] or A[B.S] are both elegant, but they are ultimately a mask operation, not a select operation. I tried to fit this usage into my propsal -- something like A.select(B.S) or A.select(B<1), but it feels like it would complicate things. After all, A.select(B<1) and A.select(A<1) look similar, but would be rewritten as totally different operations. The former is a two-step masked assignment while the latter is a select.

   I ultimately decided it's not worth the complication. Instead, I propose upgrading masks in general to be more flexible.

   More flexible masks

   Let's allow this:

   A(A<0) << 0

   This requires two changes to masks:

   1. Allowing delayed objects as masks, assuming they resolve to boolean type.
   2. Allow boolean objects without requiring the .V suffix

   Note that we still won't allow A[A<0] << 0. That would be assignment with a boolean. We can give a nice error message in this case, suggesting they put the boolean expression as the mask rather than the assignment parameter.

   Let's wait on set operations for .S and .V

   (A < 5) & (A > 1) feels useful. So does A.S & B.S or even A.V - B.S.

   However, we don't need to bite off everything at first. Getting select into grblas has already taken too long. These set operations can come later without impacting existing code.

   User-defined IndexUnaryOps

   I'm punting on this for now (again, this proposal has already taken too long and we need select quickly).

   User-defined selectops will likely not be able to take advantage of something like select.custom_op(A<5). Instead, they will need to function like tril and diag, passing the thunk as a separate parameter: select.custom_op(A, 5).

   Using all available IndexUnaryOps in Apply

   Technically, the spec allows the boolean IndexUnaryOps to be used by apply. I don't think we need to support this use case.

   For values, users can already do A == 1 and get a value comparison. If they need a row comparison, they could do it in two steps:

   1. A_rows = unary.row_index(A)
   2. A_rows <= 2

   A similar set of steps could recreate TRIL, TRIU, DIAG, and OFFDIAG comparisons.
4. jim22k commented on Apr 6, 2022

   

   jim22k

   on Apr 6, 2022

   Last edited by jim22k

   MemberAuthor

   More actions

   @eriknw @ParticularMiner and I had a meeting today to discuss this proposal. Here are take-aways I captured about the priority order of things to implement:

   1. [PR#207] Implement the Minimum Viable Product first
      • Put the IndexUnaryOps which return bool into the grblas.select namespace
      • Allow these to be called directly (gb.select.tril(A)) to perform a select operation
      • Include the "special" versions (select.row, select.column, select.value), but also include the "raw" versions (select.rowle, etc)
      • Add a select method (e.g. A.select("tril"), A.select("<", 1), A.select(gb.select.diag, 1), A.select("row<=", 1))
   2. [PR#229]Implement IndexUnaryOps to work with apply (including bool and non-bool IndexUnaryOps).
   3. [PR#233]Implement user-defined IndexUnaryOps
   4. Implement more flexible masks
      • Main need is allowing boolean objects as masks without explict .V suffix
   5. Revisit A[A<1] notation
   6. Revisit complex set expressions ((A > 1) & (A < 7), A.S | B.S, etc)
   7. Revisit using masks in select (as a convenience recipe) (e.g. A.select(B.S))
5. eriknw commented on Apr 7, 2022

   

   eriknw

   on Apr 7, 2022

   Member

   More actions

   Woo! This will be so great to get in.
6. jim22k

   closed this as completedon May 17, 2022