Skip to content

Correctness Bug: wrong semiring used in functional-style triple product #498

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
alugowski opened this issue Aug 30, 2023 · 6 comments
Closed

Comments

@alugowski
Copy link
Contributor

The functional style multiply, i.e. gb.semiring.plus_plus(A @ B) , appears to not respect the semiring choice when doing a triple product A @ B @ C.

Let:

A = gb.Matrix.from_coo([0, 0, 1], [0, 1, 1], [11, 22, 33], nrows=2, ncols=2)

left = gb.Matrix.from_coo([0, 0], [0, 1], [1, 1], nrows=1, ncols=2)
right = gb.Matrix.from_coo([0, 1], [0, 0], [1, 1], nrows=2, ncols=1)

A triple product using the plus_first semiring returns a 1x1 matrix with a count of nonzeros in A, which is 3. Indeed that is what the method style triple product returns:

left.mxm(A, op="plus_first").mxm(right, op="plus_first")
# returns `[[3]]` (correct)

However the functional-style triple product,

gb.semiring.plus_first(left @ A @ right)
# returns `[[66]]` (incorrect)

It appears that the plus_first semiring is only used for one of the multiplications, and plus_times for the other.

Application is to implement a triple product that creates a low resolution spy plot, like this:

triple_product

See MatSpy.

@eriknw
Copy link
Member

eriknw commented Sep 5, 2023

Hey @alugowski, thanks for raising this usability issue! I hope you raise more suggestions :)

I'm sorry for my delay--I was traveling and largely AFK last week.

This issue has come up before, and you can see our previous discussion in #132.

I'm open to adding this functionality, but I want us to think hard about it. Please be patient as we seek consensus (including yours!) and explore options and implementations.

I think the behavior you expect for matrix multiply is very reasonable, and is a pattern I expect to occur semi-regularly (you're not the first to encounter this). Our current behavior may be surprising and counterintuitive--especially for users coming from pygraphblas.

I have begun an implemention in #501.

@alugowski
Copy link
Contributor Author

No worries!

I see a lot of potential syntax options in that discussion. I don't have a strong opinion about those options, and what you have now works for me. The thing that confused me is that the brackets in plus_first(...) imply that plus_firstapplies to everything within those brackets, hence the surprise that led to this issue.

To me left.mxm(right, op="plus_first") is busy but also the most clear. The only feedback I can think of is to change op from a string to an object to enable static analysis.

@eriknw
Copy link
Member

eriknw commented Sep 7, 2023

Yeah, it's a reasonable expectation, and the implementation in #501 actually isn't as bad as I was expecting. I wonder about the other infix operations, such as:

gb.binary.min(A | B | C)  # ewise_add
gb.binary.max(A & B & C)  # ewise_mult
gb.binary.plus(A | B | C, left_default=0, right_default=0)  # ewise_union

The above are probably okay, b/c the infix operators are the same and there are no surprises from operator precedence.

I would probably have the below raise, b/c they're getting kinda complicated for sugar, and operator precedence (& comes before |) is weird:

gb.binary.max(A | B & C)  # mix of ewise_add and ewise_mult
gb.binary.plus(A | B & C, left_default=0, right_default=0)  # mix with ewise_union??? Probably raise

The only feedback I can think of is to change op from a string to an object to enable static analysis.

You mean like op=gb.semiring.plus_first or op=gb.op.plus_first? This works fine.

@alugowski
Copy link
Contributor Author

I agree to raise for gb.binary.max(A | B & C). Though I gotta say, I don't know how I feel about allowing arbitrary binops for any basic operator. All those statements mean something else than they would in any other package.

You mean like op=gb.semiring.plus_first or op=gb.op.plus_first? This works fine.

Ah, so it does. I copied the pattern from the docs and didn't realize there are more options :)

@eriknw
Copy link
Member

eriknw commented Sep 8, 2023

Thanks again for sharing your thoughts @alugowski.

I'm pushing ahead in #501 for chaining like expressions together, such as semiring(A @ B @ C), binop(A | B | C), and binop(A & B & C). Doing so actually makes our expression system more strict, which I think is good, helps us provide useful error messages, and prevents users from being surprised. To me, it's a small bonus to me that the above expressions work as they appear they should (i.e., being strict around these edges is more important to me). It's mostly implemented, but I still have a lot of error messages and tests to write.

@eriknw
Copy link
Member

eriknw commented Dec 13, 2023

Closed via #501; releasing soon.

@eriknw eriknw closed this as completed Dec 13, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants