4 ms·

Kronecker products have tricky properties and I was struggling to implement a linear algebra algorithm using some of those properties in a way that would be bot

Kronecker products have tricky properties and I was struggling to implement a linear algebra algorithm using some of those properties in a way that would be both correct and efficient. Using the notations from the paper "On Kronecker Products, Tensor Products and Matrix Differential Calculus" [0], I was able to (trivially!) rederive an algorithm called algorithm 993 [1] and then specialize it for our use case [2]. In particular, it let me show that, knowing the layout of the data in memory, some operations could be replaced by carefully placed implicit reshaping of the matrix (telling the linear algebra kernels that it has a number of rows/columns different from the actual one) which are no-ops. The notation used is extremely specialized and thus useless to most people / for most problems but it turned a complex problem into a trivial one in a way that felt properly magical. [0]: https://www.le.ac.uk/economics/research/RePEc/lec/leecon/dp14-02.pdf https://www.le.ac.uk/economics/research/RePEc/lec/leecon/dp1... [1]: https://dl.acm.org/doi/abs/10.1145/3291041 https://dl.acm.org/doi/abs/10.1145/3291041 [2]: https://github.com/project-asgard/kronmult993 https://github.com/project-asgard/kronmult993

kurthr 5y ago
This above is exactly the example I would give. Raising and lowering operators and Christoffel Symbols are critical to having an ability to talk about Reimann Curvature (General Relativity). However, there are many abstract concepts (zero, I, infinity, pi, e) where notation and symbolism can dramatically improve intuition. Similarly, there are notations for different groups, or simply types number systems, N J R C. Hey, why not floats and strings too? In addition, there are also many functions that we use/define (sin, cosh, B, P Y), which are basis sets for the solution of various differential and partial differential equations. Failure to use some of these notations makes explaining oneself (even to yourself) almost impossible and using a different notation will frustrate others.
- jka 5y ago
  Refactoring other people's messages into terminology that makes (concise) sense locally.. it's translation, I suppose. Nice to offer back any corrections or improvements to the author where possible so that they can improve their own use of notation.
jka 5y ago
Thank you - I struggle to have a more meaningful mental model of matrices than "int[][]" but I'll read up on this. There are a bunch of cases where I've felt intuitively that "this should be solved with numpy using matrices" -- perhaps time to learn some of that in more detail. (could you add a bit more detail about any notation in particular that was useful? I see the matrix direct product symbol and have a vague initial understanding of that and block matrices)
- nestorD 5y ago
  Part 2 to 6 of the paper explains the elements of notation I used. The algorithm I wrote had to do with both the usual matrix product and the kronecker product (in short it lets you compute the Kronecker product of several matrices together time a given matrix much more efficiently and with a significantly lower memory usage). The notation was useful to me as it surfaces the property Wikipedia describes in the "Matrix Equation" [0] section on the Kronecker product and makes it intuitive. [0]: https://en.wikipedia.org/wiki/Kronecker_product#Matrix_equations https://en.wikipedia.org/wiki/Kronecker_product#Matrix_equat...

kurthr 5y ago

This above is exactly the example I would give. Raising and lowering operators and Christoffel Symbols are critical to having an ability to talk about Reimann Curvature (General Relativity). However, there are many abstract concepts (zero, I, infinity, pi, e) where notation and symbolism can dramatically improve intuition. Similarly, there are notations for different groups, or simply types number systems, N J R C. Hey, why not floats and strings too? In addition, there are also many functions that we use/define (sin, cosh, B, P Y), which are basis sets for the solution of various differential and partial differential equations. Failure to use some of these notations makes explaining oneself (even to yourself) almost impossible and using a different notation will frustrate others.

jka 5y ago
Refactoring other people's messages into terminology that makes (concise) sense locally.. it's translation, I suppose. Nice to offer back any corrections or improvements to the author where possible so that they can improve their own use of notation.

jka 5y ago

Thank you - I struggle to have a more meaningful mental model of matrices than "int[][]" but I'll read up on this. There are a bunch of cases where I've felt intuitively that "this should be solved with numpy using matrices" -- perhaps time to learn some of that in more detail. (could you add a bit more detail about any notation in particular that was useful? I see the matrix direct product symbol and have a vague initial understanding of that and block matrices)

nestorD 5y ago
Part 2 to 6 of the paper explains the elements of notation I used. The algorithm I wrote had to do with both the usual matrix product and the kronecker product (in short it lets you compute the Kronecker product of several matrices together time a given matrix much more efficiently and with a significantly lower memory usage). The notation was useful to me as it surfaces the property Wikipedia describes in the "Matrix Equation" [0] section on the Kronecker product and makes it intuitive. [0]: https://en.wikipedia.org/wiki/Kronecker_product#Matrix_equations https://en.wikipedia.org/wiki/Kronecker_product#Matrix_equat...