# Collecting algebraic performance tricks

**URL:** <https://discourse.julialang.org/t/collecting-algebraic-performance-tricks/22992>\
**Category:** Performance\
**Created:** [April 10, 2019, 10:26am UTC](https://discourse.julialang.org/t/collecting-algebraic-performance-tricks/22992 "2019-04-10T10:26:16Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![theogf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/theogf/32/1987_2.png) [@theogf](https://discourse.julialang.org/u/theogf)\
**Post date:** [April 10, 2019, 10:26am UTC](https://discourse.julialang.org/t/collecting-algebraic-performance-tricks/22992/1 "2019-04-10T10:26:16Z")

</div>

There are many ways to dramatically improve performance by using some algebraic equivalencies, for example :

```julia
tr(A*B) == dot(A,B') 
diag(A*B) == vec(sum(A.*B',dims=2))

```

Do you know if there are ressources listing this kind of useful equivalencies?  
And if not how about starting an organized collaborative document where everyone can share his knowledge?

Edit : corrected formula for diag

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [April 10, 2019, 10:28am UTC](https://discourse.julialang.org/t/collecting-algebraic-performance-tricks/22992/2 "2019-04-10T10:28:09Z")

</div>

```nohighlight
@article{petersen2008matrix,
  title={The matrix cookbook},
  author={Petersen, Kaare Brandt and Pedersen, Michael Syskind and others},
  journal={Technical University of Denmark},
  volume={7},
  number={15},
  pages={510},
  year={2008}
}

```

You can find some updates online up to 2012 I think.

---

<div class="post-metadata">

**Author:** ![theogf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/theogf/32/1987_2.png) [@theogf](https://discourse.julialang.org/u/theogf)\
**Post date:** [April 10, 2019, 10:32am UTC](https://discourse.julialang.org/t/collecting-algebraic-performance-tricks/22992/3 "2019-04-10T10:32:30Z")

</div>

The Matrix Cookbook is indeed the most lifesaving ressource for matrix calculus!  
However when it comes to implementation it does not help so much. I was thinking of something more concrete and code oriented.

---

<div class="post-metadata">

**Author:** ![chakravala](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chakravala/32/6832_2.png) [@chakravala](https://discourse.julialang.org/u/chakravala)\
**Post date:** [April 10, 2019, 10:44am UTC](https://discourse.julialang.org/t/collecting-algebraic-performance-tricks/22992/4 "2019-04-10T10:44:33Z")

</div>

> [@theogf](#):
>
> Do you know if there are ressources listing this kind of useful equivalencies?

Math textbooks? Typically, this is the job of mathematicians, so the language for identities is usually in written in pure math, and not a specific programming language. This is why you won’t find many textbooks that give identities in a specific computer programming language.

However, you should also be able to find a whole bunch of identities like this in any sort of computer algebra term rewrite system.

> <https://github.com/fredrik-johansson/fungrim/issues/2>
>
> There are about 300,000 identities, expansions, special values, etc. at http://f…unctions.wolfram.com/, in a structured computer-readable format ("Wolfram langauge"). It would be nice to populate the grimoire with as many of these as possible rather than manually entering them all.
> 
> The ones at https://dlmf.nist.gov would be more difficult to import because they are not in a structured machine-readable format.

---

<div class="post-metadata">

**Author:** ![mohamed82008](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mohamed82008/32/18171_2.png) [@mohamed82008](https://discourse.julialang.org/u/mohamed82008)\
**Post date:** [April 10, 2019, 11:30am UTC](https://discourse.julialang.org/t/collecting-algebraic-performance-tricks/22992/5 "2019-04-10T11:30:06Z")

</div>

> [@theogf](#):
>
> sum(A,B’,dims=2)

`sum(A .* B', dims = 2)`

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [April 10, 2019, 11:39am UTC](https://discourse.julialang.org/t/collecting-algebraic-performance-tricks/22992/6 "2019-04-10T11:39:10Z")

</div>

> [@theogf](#):
>
> I was thinking of something more concrete and code oriented.

I think that in the context of Julia the best approach is to define methods to _do what you mean_, without worrying about the implementation details, and then depending on the details, define optimized methods when it makes sense.

This approach establishes a clean separation between intent and implementation, and you can also use the generic method to test the specific one.

Regarding matrix indentities: the optimal approach can depend on structure (sense, n-diagonal, triangular, sparse, block, …). Also, sometimes the a highly optimized generic BLAS approach will beat a theoretically superior native one — one should always benchmark.

---

<div class="post-metadata">

**Author:** ![antoine-levitt](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/antoine-levitt/32/4008_2.png) [@antoine-levitt](https://discourse.julialang.org/u/antoine-levitt)\
**Post date:** [April 10, 2019, 11:43am UTC](https://discourse.julialang.org/t/collecting-algebraic-performance-tricks/22992/7 "2019-04-10T11:43:07Z")

</div>

```julia
tr(A*B) == dot(A,B') 
diag(A*B) == vec(sum(A,B',dims=2))

```

This sort of matlab-style trickery might not be that useful in Julia where you can just write loops. Exceptions are when you can recognize a BLAS2 or BLAS3 operation.

---

<div class="post-metadata">

**Author:** ![pkofod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pkofod/32/2179_2.png) [@pkofod](https://discourse.julialang.org/u/pkofod)\
**Post date:** [April 10, 2019, 1:13pm UTC](https://discourse.julialang.org/t/collecting-algebraic-performance-tricks/22992/8 "2019-04-10T13:13:39Z")

</div>

> [@Tamas\_Papp](#):
>
> You can find some updates online up to 2012 I think.

> **[imm3274.pdf](https://www2.imm.dtu.dk/pubdb/edoc/imm3274.pdf)**
>
> 676.45 KB

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [April 10, 2019, 1:31pm UTC](https://discourse.julialang.org/t/collecting-algebraic-performance-tricks/22992/9 "2019-04-10T13:31:42Z")

</div>

I get a “not found” for this.

---

<div class="post-metadata">

**Author:** ![pkofod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pkofod/32/2179_2.png) [@pkofod](https://discourse.julialang.org/u/pkofod)\
**Post date:** [April 10, 2019, 1:56pm UTC](https://discourse.julialang.org/t/collecting-algebraic-performance-tricks/22992/10 "2019-04-10T13:56:50Z")

</div>

what if you click the pdf link here ? [The Matrix Cookbook](http://www2.imm.dtu.dk/pubdb/views/publication_details.php?id=3274)

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [April 10, 2019, 2:04pm UTC](https://discourse.julialang.org/t/collecting-algebraic-performance-tricks/22992/11 "2019-04-10T14:04:09Z")

</div>

Yes, this one works, thanks.

This is the version I had, and the latest I know of. It is a pity that they did not upload the source to a repo somewhere with an open license.