Great question, thanks for asking!

You are correct that GraphBLAS or any implementations do not yet support this natively. I asked@DrTimothyAldenDavis a while ago about the feasibility of implementing this, and as I recall he said it would be a non-trivial amount of work, so we would really like to see and understand compelling use cases.

pydata/sparse does support a data model where you can set the value of the missing elements and can generally treat its data structures like numpy arrays. We can convert to and from it (see docs), but I don't know many people who have done this or how the performance will be.

For this particular problem, since we're only dealing with boolean values, we may be able to find another solution. If I understand correctly, you want to compute this but using union instead of intersection, right?

C=gb.semiring.lor_lor(A @B).new()

Perhaps this (or something like it) could work:

C=gb.semiring.lor_lor(A @B).new()a=A.reduce_rowwise("lor").new()b=B.reduce_columnwise("lor").new()C("lor")<<a.outer(b,"lor")

I'm not entirely confident I understand your specific question, so in case I didn't and this above doesn't work, can you provide example inputs and output that we can play around with? Also, what operations would you want to do if mxmdid support union of elements instead of intersection?

For instance, I need to compute the boolean value of A[i,j] -> B[j,k] for (i,j) in A or (j,k) in B (for all entries in A and B, only A and only B). The "->" means logical implication. The mxm function does not support this since it uses the intersection.

I don't follow your description. Can you be more specific? Like C(i,j) = some formula? Even a brute force triply nested O(n^3) for loop description would be helpful:

for i = 0 to n-1   for j = 0 to n-1      for k = 0 to n-1          aik = (A(i,k) present) ? A(i,k) : whatever ;          bkj = etc          C(i,j)  = C(i,j) OR (whatever)

because I'm confused with your notation of A(i,j), since I like to think of C(i,j) = sum_(k in intersection of A(i,:) and B(:,j)) of A(i,k)*B(k,j), and you're using the indices in a different way.

It might be possible to work on the intersection, and compute the results on the union after that. The output C(i,j) be a tuple that contains (value,count), where value is the result over the intersection and count is the size of the intersection. Then multiplying C on left and right by diagonal matrices (containing the row degree of A and column degree of B) could then be used to compute the result on the union. But I don't yet know what is being computed outside the intersection so I'm unsure.

In the sparse matrix A, what are the values of the entries present? What is the implied value of the entry not present? And likewise for B and C?

Thanks for the suggestions@DrTimothyAldenDavis@eriknw. To clarify, consider two matrices A and B (T, F and True and False, E is empty):

A = [   T T   E T  T E  E E]

B = [   T T E E  T E E E]

I am looking for C = gb.semiring.land_lor(A @ B) where lor is applied to the union of elements.

C = [  T   F  T  E]

Pseudo code description:

for i = 0 to n-1   for j = 0 to n-1      or = True      for k = 0 to n-1          # lor should be for the elements union          or_k = Empty if A[i,k] is Empty and B[k,j] is Empty else A[i,k] OR B[k,j]          # land reduce the vector to a binary value          or  = Empty if or_k is Empty else or AND or_k      C(i,j)  = or

I have a solution which negated A so I could do A @ B with the intersection and then negated the result back. I used iso to do the negation so the overall time should be less than O(n^2). But I wonder if the negations could be avoided.

The computation of or_k is also a bit unclear.

or_k = Empty if A[i,k] is Empty and B[k,j] is Empty else A[i,k] OR B[k,j]

So if both A(i,k) and B(k,j) are empty, then or_k is empty.

Otherwise, you do a logical or ... but that doesn't mean anything if one of the inputs is not present. What is "empty OR true"? The operators in GraphBLAS are never given empty inputs.

And I don't think you mean this:

or = Empty if or_k is Empty else or AND or_k
the variable "or" would become empty as soon as a single pair of A(i,k) and B(k,,j) appear that are both not present, discarding all prior comptuations.

also, your example for A and B just show two kinds of entries: True and Empty. Can they be False? Or are both A and B iso-valued (where all entries present are equal to the same value, True in this case)?

I'm trying to understand what you want to compute so I can suggest an alternative. Matrix-matrix multiply will never be able to work on this set union approach, but there could likely be an alternative method where you use matrix-matrix multiply to operate on the set intersection, and then another step to account for entries outside that intersection.