Skip to content

Conversation

@eriknw
Copy link
Member

@eriknw eriknw commented Jul 16, 2023

This uses #481 (and is actually why I made #481).

I still need to write the docstring.

I tried to make this efficient by performing repeated squaring. For example, for A.power(8), this will compute:

cur = op(A @ A).new()
cur << op(cur @ cur)
updater << op(cur @ cur)

This makes the implementation a little... uh... not obvious, but it works well.

A.power(n) returns an expression so mask can be applied. Even if a mask is used, an intermediate result A.power(n // 2) can still be pretty large--we only apply the mask on the very last matrix multiply.

I decided to require n to be a positive integer. n == 0 could return "the" identity, but what would be the identity for different semirings?

This method will let us easily and efficiently implement number_of_walks in graphblas_algorithms.

@eriknw eriknw added the feature Something is missing label Jul 16, 2023
@coveralls
Copy link

coveralls commented Jul 16, 2023

Coverage Status

coverage: 99.414% (+0.2%) from 99.206% when pulling 60a1d44 on eriknw:power into 3476731 on python-graphblas:main.

@eriknw eriknw merged commit 8e42ded into python-graphblas:main Jul 26, 2023
@eriknw eriknw mentioned this pull request Nov 4, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

feature Something is missing

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants