Skip to content
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

[Feature Request] Low Rank Dispatch rules (Woodbury identity, Trace rules, etc) #48

Open
mfinzi opened this issue Sep 7, 2023 · 0 comments · May be fixed by #57
Open

[Feature Request] Low Rank Dispatch rules (Woodbury identity, Trace rules, etc) #48

mfinzi opened this issue Sep 7, 2023 · 0 comments · May be fixed by #57
Labels
enhancement New feature or request good first issue Good for newcomers

Comments

@mfinzi
Copy link
Collaborator

mfinzi commented Sep 7, 2023

🚀 Feature Request

Dispatch rules for Product[Dense,Dense] or Sum[Product[Dense,Dense], Diagonal].

Examples:

Woodbury identity

Let the Woodbury matrix identity be given by:
$(D + UV)^{-1} = D^{-1} - D^{-1}U(I + VD^{-1}U)^{-1}VD^{-1}$

Cyclic trace property:

Given the cyclic trace property:
$\text{Tr}(UV) = \text{Tr}(VU)$
The idea is that for a generic Product[LinearOperator,LinearOperator] where $U$ and $V$ are not square, we can rearrange to reduce the dimensionality. If dense, we can further accelerate by performing the elementwise multiplication of $U$ and $V$ summing only over one axis.

Pitch

Introduce rules such as:

@dispatch
def inv(A: Sum[Product[Dense,Dense], Diagonal], **kwargs):
    ...

@dispatch(cond=product_faster_if_rearranged)
def trace(A: Product):
    ...

Additional context

Plum-dispatch can work a little different than one would expect for parametric types.
Some things need to be spelled out more explicitly (and possibly even changes may need to be made to cola-plum-dispatch)

@mfinzi mfinzi added enhancement New feature or request good first issue Good for newcomers labels Sep 7, 2023
This was referenced Sep 10, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request good first issue Good for newcomers
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant