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

Pre-multiplying Matrices #93

Closed
lukem12345 opened this issue Jan 25, 2023 · 1 comment
Closed

Pre-multiplying Matrices #93

lukem12345 opened this issue Jan 25, 2023 · 1 comment
Assignees

Comments

@lukem12345
Copy link
Member

Currently, given a decapode like: * -f-> * -g-> * -h-> *, where each arrow f,g,h multiplies by a matrix A,B,C, respectively, the generated function will perform three matrix-vector multiplications.

We would like to pre-multiply these matrices into D=CBA, so the generated function will perform only one matrix-vector multiplication.

A working example of this optimization should focus on editing the combinatorial data structure of the decapode. This will require a function that is the inverse of expand_operators.

@lukem12345 lukem12345 self-assigned this Jan 25, 2023
@lukem12345
Copy link
Member Author

We note that we can take this idea of contracting chains further by eliminating branches.

In other words, a binary tree of depth 2, (with update steps at the leaves) requires (assuming all functions on edges are unique) 6 matrices, 2 intermediary vectors, and performs 6 matrix-vector multiplications. This could be re-written as an equivalent 1-deep 4-ary tree which requires just 4 matrices, 0 intermediary vectors, and performs 4 matrix-vector multiplications. This result cannot be improved upon, unless edge pruning of duplicate operations is performed.

This speed-up and memory improvement of an entire decapode in this fashion is unlikely to occur, since Op2s are likely to break this downwards tree-like property.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants