Skip to content

Add matrix.power to compute e.g. A @ A @ A @ ... #483

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

Merged
merged 8 commits into from
Jul 26, 2023

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