AA << op.plus_times(P.T @ A @ P) ?

@eriknw

Oops! I stretched the infix notation a bit too far by testing the following line, which is an expression one would often encounter when transforming matrix-quantities (like graph adjacency-matrices, for example):

AA << op.plus_times(P.T @ A @ P)

where A, AA and P are all matrices. (That is, A is transformed by P into AA. P could be a permutation matrix, for example.)

The expression was executed without throwing an exception, but the result was incorrect. To be precise, the structure of the answer was correct but the values were all 0 (which was incorrect).

Of course, the right way to do it was this:

AA << op.plus_times(P.T @ op.plus_times(A @ P))

which gave the right answer.

But it would be great if the former notation was also possible. What do you think?

@eriknw

@eriknw

Sorry, I made a mistake. Both expressions work as expected. I was using the wrong semiring. It should have been op.plus_times not op.plus_minus. Obviously!

Surprisingly, it works! Did you expect that it would?

Good question. Yes, I expect this to work only for the plus_times semiring.

AA << A @ P is equivalent to AA << op.plus_times(A @ P).
C << A | B is equivalent to C << op.lor(A | B) only if A and B are BOOL (otherwise, this raises).
C << A & B is equivalent to C << op.land(A & B) only if A and B are BOOL (otherwise, this raises).

Although I generally prefer to be explicit, we think these are convenient enough to be special. The above behavior can be disabled via grblas.config.set(autocompute=False) (which may also require you to call .new() more often).

Hence, AA << P.T @ A @ P is equivalent to AA << op.plus_times(op.plus_times(P.T @ A).new() @ P).

Note that this doesn't extend to other semirings. For example, AA << op.min_plus(P.T @ A @ P) is equivalent to AA << op.min_plus(op.plus_times(P.T @ A).new() @ P).

Makes sense.

So op.plus_times is the default semiring for the @ operator.
And similarly for the other semirings and operators you mentioned.

Then your last line:

Note that this doesn't extend to other semirings. For example, AA << op.min_plus(P.T @ A @ P) is equivalent to AA << op.min_plus(op.plus_times(P.T @ A).new() @ P)

is perfectly understandable, though counter-intuitive especially if one is unaware of the default semiring behaviour.

@eriknw

@eriknw

Thanks for the explanation.

@ParticularMiner

You bet! Thanks for raising the issue. I'm always happy to discuss usability issues.

As you pointed out, the current behavior of op.min_plus(P.T @ A @ P) is understandable, although perhaps counter-intuitive. I actually haven't given this much consideration before. It may actually be straightforward-ish to apply the min_plus semiring to both matrix multiplies here. @ParticularMiner and @jim22k do you agree that doing so would be the preferred behavior?

Doing the same for e.g. op.times(A & B & C) should also be doable.

I'd need to think about it a bit some more to decide which should be preferred. But currently I'm leaning towards applying the specified semiring to all operators in its scope.

Perhaps there's a PEP specification somewhere that would be the deciding factor?

@eriknw

Hi @eriknw

Thinking about this a bit further, I'm now in agreement with your preference, as it is consistent with standard associativity rules.

But there is one feature I think would be quite useful if it was made available, namely, the ability to change the default semiring or binary operation associated with an operator.

Is that an idea that appeals to you?

Thanks for the feedback, and interesting idea.

We could do something like the following:

# Change it until we change it again
>>> gb.config.set(matmul_default=op.min_plus)
>>> C << A @ B

# or only change within the context
>>> with gb.config.set(matmul_default=op.min_plus):
...     C << A @ B

How would you like to spell this? Would you use it?

@eriknw

Nice @eriknw ! Both options would do the job. Perhaps the second option is safer and less verbose, as it automatically reverts back to the prior default semiring when the context is exited, right?

I would certainly use either of them. Then more readable mathematical expressions, such as

F << A @ B @ C @ D @ E

could be possible for any semiring while also avoiding possible confusion.

Or is this perhaps going too far beyond what GraphBLAS is intended to make possible? But I believe that transforming an adjacency matrix by a permutation transformation, for example, should be on the TODO list of GraphBLAS maintainers if it isn't already.

Thanks for this!

@jim22k

grblas.config already works like I described above (with or without context manager).

We could forego using the config altogether and do something like this:

with op.min_times:
    C << A @ B

and

with op.plus:
    D << A | B & C

Here, a BinaryOp or Monoid used as a context manager sets the default for both ewise_add and ewise_mult.

This would actually be a lot easier to make work than e.g. op.min_plus(A @ B @ C).

@jim22k what are your thoughts? We've bounced around a few ideas that essentially do the same thing:

D << op.min_plus(A @ B @ C)
gb.config.set(matmul=op.min_plus) or as a context manager
with op.min_plus: D << A @ B @ C

Cool!

One question:

What then would be the difference between

with op.plus:
    D << A | B & C

and

with op.plus:
    D << A | B | C

or

with op.plus:
    D << A & B & C

?

Order of expression evaluation only?

A | B performs ewise_add (i.e., like a union), and A & B performs ewise_mult (i.e., like an intersection), so that's the main difference.

| and & have different precedents (see https://docs.python.org/3/reference/expressions.html#operator-precedence), which could lead to surprising behavior. For example, A | B & C is the same as A | (B & C), whereas A | B | C is equivalent to (A | B) | C. I think this is an argument against having with op.plus:, but isn't necessarily a deal breaker. I think this syntax can be nice with semirings, with op.min_plus:

Interesting. I certainly have no objections to it. I just found your last example a mathematical curiosity since, coming from a physics background, I normally wouldn't craft such an expression myself — I mean one where multiple operators map onto the same underlying monoid and thus, effectively, only their order of precedence dictates the path taken during expression evaluation.

Perhaps you have seen applications where such functionality is useful?

Sorry I'm late to the party.

I like this style because it is explicit.

>>> with gb.config.set(matmul_default=op.min_plus):
...     C << A @ B

I could live with this approach, although I feel it lacks the self-explanatory nature of explicitly calling out matmul_default to hint and what it is actually doing. This would also get closer to merging syntax styles with pygraphblas.

>>> with op.min_plus:
...     D << A @ B @ C

I don't like this approach -- feels too magical. And there are likely some edge cases which could lead to surprising results:

D << op.min_plus(A @ B @ C)

Navigation Menu

Repository navigation

`AA << op.plus_times(P.T @ A @ P)` ? #132

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

AA << op.plus_times(P.T @ A @ P) ? #132

Description

Activity

ParticularMiner commented on Dec 1, 2021

ParticularMiner commented on Dec 1, 2021

eriknw commented on Dec 1, 2021

ParticularMiner commented on Dec 1, 2021

ParticularMiner commented on Dec 1, 2021

eriknw commented on Dec 1, 2021

ParticularMiner commented on Dec 1, 2021

ParticularMiner commented on Dec 2, 2021

eriknw commented on Dec 2, 2021

ParticularMiner commented on Dec 2, 2021

eriknw commented on Dec 2, 2021

ParticularMiner commented on Dec 2, 2021

eriknw commented on Dec 2, 2021

ParticularMiner commented on Dec 3, 2021

jim22k commented on Jan 21, 2022

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

`AA << op.plus_times(P.T @ A @ P)` ? #132