6 ms·

Einstein Notation applied in programming

72 points by anacleto 12y ago

enupten 12y ago
There are C++ libraries which have claimed to do this. I use this regularly in Matlisp: https://github.com/matlisp/matlisp/wiki https://github.com/matlisp/matlisp/wiki
- hzhou321 12y ago
  It is not a library. It is a syntax. An important idea of MyDef is the implementation behind the syntax is accessible to the programmer so the programmer can read, check, verify, modify and create. So when the programmer later decide to optimize the code into inline assembly (just e.g.), he can, without changing any of his def code.
jpallen 12y ago
When I was doing lots of tensor computations during my PhD, I found Cadabra (http://cadabra.phi-sci.com/ http://cadabra.phi-sci.com/) which has great support for Einstein notation.
SandB0x 12y ago
Numpy has the einsum function, often very efficient as it avoids allocating memory for intermediate results. http://docs.scipy.org/doc/numpy/reference/generated/numpy.einsum.html http://docs.scipy.org/doc/numpy/reference/generated/numpy.ei...
QuantumRoar 12y ago
I've never seen a cross product being defined in that way using Einstein notation. You might want to express the cross product using the Levi-Civita symbol epsilon_{ijk} [1]. epsilon_{ijk} = 1 for i,j,k = 1,2,3 and all even permutations thereof. epsilon_{ijk} = -1 for all odd permutations of i,j,k = 1,2,3. Else it is 0. Then, the cross product reduces to: C_i = epsilon_{ijk} A_j B_k Using identities for epsilon_{ijk} you can – for example – easily calculate what A cross (B cross C) is. [1]: https://en.wikipedia.org/wiki/Levi-Civita_symbol https://en.wikipedia.org/wiki/Levi-Civita_symbol
- JadeNB 12y ago
  > I've never seen a cross product being defined in that way using Einstein notation. In fact, I can't understand this use of the notation—namely, C_i = A_{i + 1 `mod` 3}B_{i + 2 `mod` 3} —and am not sure that it's correct. There is no free variable on the right-hand side, so I'm not sure over what to sum. Even if this were fixed, we'd need something like, as you say, the Levi–Civita symbol, since a given entry of the cross product is not a sum but a difference.
  - QuantumRoar 12y ago
    Oh, you're right. I just glanced over the equation and I thought I should recommend the standard notation. But as you stated, the cross product is clearly wrong as given by the author. There's obviously no other way than defining it with a totally antisymmetric quantity like the Levi-Civita symbol.
  - hzhou321 12y ago
    When there is no free variable, there is no sum, just the loop. But you are right the the notion does not work as is because complicated subscript support is not implemented yet. But the equation is listed before the programming part is mentioned and it is an illustration of idea, so I believe it is ok. It is not difficult to add the implementation, although it will be tedious (but still behind the surface). It is matter of how useful it is. And you are probably right that implementing a Levi-Civita syntax might be more straight forward.
    - hzhou321 12y ago
      Oh I noticed my mistake, now corrected.
titanomachy 12y ago
Been a while since GR, but I'm pretty sure some of those indices are supposed to be on top. A_{ij} = B_i^k * C_{jk} possibly, but don't quote me on that.
- Potando 12y ago
  Subscripts are how it's used in the more down to earth engineering applications like anisotropic thermal conductivity and elasticity. I can see why some authors might want to put the right-hand-side-only variables somewhere else for clarity though.
- cabinpark 12y ago
  Since these are Euclidean spaces, the difference between contravariant and covariant indices is non-existent. So it doesn't matter whether the indices are upstairs or downstairs.
  - JadeNB 12y ago
    I would say not 'nonexistent', but rather 'avoidable'; or, even better, that there is an isomorphism in an appropriate sense. (Compare the situation for strings and lists of characters; the types are isomorphic, but I wouldn't say that the difference between them is non-existent!)
    - cabinpark 12y ago
      True. I'm just a lazy relativist though ;)
  - sdenton4 12y ago
    Yeah, but I find that -- like dimensional analysis -- keeping careful track of what's upstairs and downstairs can help me keep a computation from going off the rails.
- JadeNB 12y ago
  As cabinpark (https://news.ycombinator.com/item?id=9165144 https://news.ycombinator.com/item?id=9165144) points out, it is not necessary to make this distinction; but, if you want to do so, canonically a matrix has one covariant and one contravariant index, so you would want something like A_i^j = B_i^k*C_k^j .
KfZ 12y ago
What the author call "black magic" I call abstraction. Why would you need to know at all times what summation and multiplications of what rows and columns are going on in your matrices? That's why use matrices, to not have to think about those all the time.
- geocar 12y ago
  I think you missed the point. You can write `a mmu b` in KDB, but what the author refers to as no clue on the surface to tell me what is A, B, or C is about the need for improved notation, not an extended maths library. That said, I think the author's notation is terrible, so I'll use a different one. In K you can write +/+*\: or explicitly {+/+x*\:y} which is a function: sum flip x times eachleft y This allows me to see that: (2 3f;4 0f)*\:(1 2f;5 -1f) is: ((2 4f;15 -3f);(4 8f;0 -0f)) and because I want the sums to go "the other way" I just sum the flip: +/+((2 4f;15 -3f);(4 8f;0 -0f)) Now I must prefer reading it this way; my MBA has too small a screen to fit the C code the way the author wrote it, but in just a few characters it is completely obvious what is going on! This extends to the second example as well: +/1+!x (sum one plus til x) is much more clear than: int sum=0,i,a[100]; for(i=0;i<100;++i)a[i]=i+1; for(i=0;i<100;++i)sum=sum+a[i]; and while sumcode doesn't take up so much room that I can't fit it on my screen, the K example is much clearer and much more obvious to the point where I might notice that {+/1+!x} is the same as {a+x*a:x%2} -- something I might miss if the two for-loops are far enough away from each other. Do you still think we need a sumcode abstraction now? Or do you understand the value of better list comprehension?
  - hzhou321 12y ago
    I am not sure I find your syntax intuitive, but I understand that takes individual experience. The main point (I am the author btw) is to have a lexical layer above the programming language layer, and give the programer control on how to write code that is most fit his mind. For example, how about give you the ability of use your +/+*\: when you are programming in C? You may not buy it, but the idea is to separate the syntax layer from language layer so programmer can have a sliding context just like the way our mind deals with daily life.
stared 12y ago
In Julia it is easy: https://github.com/Jutho/TensorOperations.jl https://github.com/Jutho/TensorOperations.jl In some fields, e.g. condensed matter physics, you need you need to deal with contracting multidimensional tensors all the time, and with out Einstein notation it would be difficult. The simples example is so-called matrix product state (http://en.wikipedia.org/wiki/Matrix_product_state http://en.wikipedia.org/wiki/Matrix_product_state), which is similar to Markov process. But for more interesting scenarios (e.g. 2d) one needs to use at least 4 dim tensors.
mistaken 12y ago
So you've discovered what macros are for. M4 can do this and a lot more: http://en.wikipedia.org/wiki/M4_%28computer_language%29 http://en.wikipedia.org/wiki/M4_%28computer_language%29
- hzhou321 12y ago
  I know. But I find it too difficult to use. Maybe it is just me. The big idea behind MyDef is if the programmer find something is more natural, he should at least try it. I (the author) do not really care if anyone use MyDef per my implementation. One could implement MyDef in Lisp, Haskell, or any language, and I would be happy. A meta layer that individual programmer can control, rather than being sold in wholesale every single time.
mattxxx 12y ago
This is totally missing the point. Nonsingular matrices form a group; use the multiplication operator to convey a wealth of operations that you can do with it.
currentoor 12y ago
Nice post. I studied with this notation too but I was not clever enough to connect it to my programming. This is a good example of a situation where something like lisp's macro system would be very useful. But I don't understand what the author means by On the other end of the spectrum, lisp is designed for its upper layer elegance. Its macros are structured all the way to the top. However, to achieve that, it limits its lower level representations. In fact, it takes work-around for simple switches and loops. What's the work-around? Common Lisp and Clojure have built in conditionals and loops.
- hzhou321 12y ago
  Obviously it is my ignorance. I'll revise it back. But I still think MyDef is more than lisp. I need find a lisp expert friend (that is willing to understand MyDef) to make better narration. :)

72 points by anacleto 12y ago

There are C++ libraries which have claimed to do this. I use this regularly in Matlisp: https://github.com/matlisp/matlisp/wiki https://github.com/matlisp/matlisp/wiki

hzhou321 12y ago
It is not a library. It is a syntax. An important idea of MyDef is the implementation behind the syntax is accessible to the programmer so the programmer can read, check, verify, modify and create. So when the programmer later decide to optimize the code into inline assembly (just e.g.), he can, without changing any of his def code.

jpallen 12y ago

When I was doing lots of tensor computations during my PhD, I found Cadabra (http://cadabra.phi-sci.com/ http://cadabra.phi-sci.com/) which has great support for Einstein notation.

SandB0x 12y ago

Numpy has the einsum function, often very efficient as it avoids allocating memory for intermediate results. http://docs.scipy.org/doc/numpy/reference/generated/numpy.einsum.html http://docs.scipy.org/doc/numpy/reference/generated/numpy.ei...

QuantumRoar 12y ago

I've never seen a cross product being defined in that way using Einstein notation. You might want to express the cross product using the Levi-Civita symbol epsilon_{ijk} [1]. epsilon_{ijk} = 1 for i,j,k = 1,2,3 and all even permutations thereof. epsilon_{ijk} = -1 for all odd permutations of i,j,k = 1,2,3. Else it is 0. Then, the cross product reduces to: C_i = epsilon_{ijk} A_j B_k Using identities for epsilon_{ijk} you can – for example – easily calculate what A cross (B cross C) is. [1]: https://en.wikipedia.org/wiki/Levi-Civita_symbol https://en.wikipedia.org/wiki/Levi-Civita_symbol

JadeNB 12y ago
> I've never seen a cross product being defined in that way using Einstein notation. In fact, I can't understand this use of the notation—namely, C_i = A_{i + 1 `mod` 3}B_{i + 2 `mod` 3} —and am not sure that it's correct. There is no free variable on the right-hand side, so I'm not sure over what to sum. Even if this were fixed, we'd need something like, as you say, the Levi–Civita symbol, since a given entry of the cross product is not a sum but a difference.
- QuantumRoar 12y ago
  Oh, you're right. I just glanced over the equation and I thought I should recommend the standard notation. But as you stated, the cross product is clearly wrong as given by the author. There's obviously no other way than defining it with a totally antisymmetric quantity like the Levi-Civita symbol.
- hzhou321 12y ago
  When there is no free variable, there is no sum, just the loop. But you are right the the notion does not work as is because complicated subscript support is not implemented yet. But the equation is listed before the programming part is mentioned and it is an illustration of idea, so I believe it is ok. It is not difficult to add the implementation, although it will be tedious (but still behind the surface). It is matter of how useful it is. And you are probably right that implementing a Levi-Civita syntax might be more straight forward.
  - hzhou321 12y ago
    Oh I noticed my mistake, now corrected.

titanomachy 12y ago

Been a while since GR, but I'm pretty sure some of those indices are supposed to be on top. A_{ij} = B_i^k * C_{jk} possibly, but don't quote me on that.

Potando 12y ago
Subscripts are how it's used in the more down to earth engineering applications like anisotropic thermal conductivity and elasticity. I can see why some authors might want to put the right-hand-side-only variables somewhere else for clarity though.
cabinpark 12y ago
Since these are Euclidean spaces, the difference between contravariant and covariant indices is non-existent. So it doesn't matter whether the indices are upstairs or downstairs.
- JadeNB 12y ago
  I would say not 'nonexistent', but rather 'avoidable'; or, even better, that there is an isomorphism in an appropriate sense. (Compare the situation for strings and lists of characters; the types are isomorphic, but I wouldn't say that the difference between them is non-existent!)
  - cabinpark 12y ago
    True. I'm just a lazy relativist though ;)
- sdenton4 12y ago
  Yeah, but I find that -- like dimensional analysis -- keeping careful track of what's upstairs and downstairs can help me keep a computation from going off the rails.
JadeNB 12y ago
As cabinpark (https://news.ycombinator.com/item?id=9165144 https://news.ycombinator.com/item?id=9165144) points out, it is not necessary to make this distinction; but, if you want to do so, canonically a matrix has one covariant and one contravariant index, so you would want something like A_i^j = B_i^k*C_k^j .

KfZ 12y ago

What the author call "black magic" I call abstraction. Why would you need to know at all times what summation and multiplications of what rows and columns are going on in your matrices? That's why use matrices, to not have to think about those all the time.

geocar 12y ago
I think you missed the point. You can write `a mmu b` in KDB, but what the author refers to as no clue on the surface to tell me what is A, B, or C is about the need for improved notation, not an extended maths library. That said, I think the author's notation is terrible, so I'll use a different one. In K you can write +/+*\: or explicitly {+/+x*\:y} which is a function: sum flip x times eachleft y This allows me to see that: (2 3f;4 0f)*\:(1 2f;5 -1f) is: ((2 4f;15 -3f);(4 8f;0 -0f)) and because I want the sums to go "the other way" I just sum the flip: +/+((2 4f;15 -3f);(4 8f;0 -0f)) Now I must prefer reading it this way; my MBA has too small a screen to fit the C code the way the author wrote it, but in just a few characters it is completely obvious what is going on! This extends to the second example as well: +/1+!x (sum one plus til x) is much more clear than: int sum=0,i,a[100]; for(i=0;i<100;++i)a[i]=i+1; for(i=0;i<100;++i)sum=sum+a[i]; and while sumcode doesn't take up so much room that I can't fit it on my screen, the K example is much clearer and much more obvious to the point where I might notice that {+/1+!x} is the same as {a+x*a:x%2} -- something I might miss if the two for-loops are far enough away from each other. Do you still think we need a sumcode abstraction now? Or do you understand the value of better list comprehension?
- hzhou321 12y ago
  I am not sure I find your syntax intuitive, but I understand that takes individual experience. The main point (I am the author btw) is to have a lexical layer above the programming language layer, and give the programer control on how to write code that is most fit his mind. For example, how about give you the ability of use your +/+*\: when you are programming in C? You may not buy it, but the idea is to separate the syntax layer from language layer so programmer can have a sliding context just like the way our mind deals with daily life.

stared 12y ago

In Julia it is easy: https://github.com/Jutho/TensorOperations.jl https://github.com/Jutho/TensorOperations.jl In some fields, e.g. condensed matter physics, you need you need to deal with contracting multidimensional tensors all the time, and with out Einstein notation it would be difficult. The simples example is so-called matrix product state (http://en.wikipedia.org/wiki/Matrix_product_state http://en.wikipedia.org/wiki/Matrix_product_state), which is similar to Markov process. But for more interesting scenarios (e.g. 2d) one needs to use at least 4 dim tensors.

mistaken 12y ago

So you've discovered what macros are for. M4 can do this and a lot more: http://en.wikipedia.org/wiki/M4_%28computer_language%29 http://en.wikipedia.org/wiki/M4_%28computer_language%29

hzhou321 12y ago
I know. But I find it too difficult to use. Maybe it is just me. The big idea behind MyDef is if the programmer find something is more natural, he should at least try it. I (the author) do not really care if anyone use MyDef per my implementation. One could implement MyDef in Lisp, Haskell, or any language, and I would be happy. A meta layer that individual programmer can control, rather than being sold in wholesale every single time.

mattxxx 12y ago

This is totally missing the point. Nonsingular matrices form a group; use the multiplication operator to convey a wealth of operations that you can do with it.

currentoor 12y ago

Nice post. I studied with this notation too but I was not clever enough to connect it to my programming. This is a good example of a situation where something like lisp's macro system would be very useful. But I don't understand what the author means by On the other end of the spectrum, lisp is designed for its upper layer elegance. Its macros are structured all the way to the top. However, to achieve that, it limits its lower level representations. In fact, it takes work-around for simple switches and loops. What's the work-around? Common Lisp and Clojure have built in conditionals and loops.

hzhou321 12y ago
Obviously it is my ignorance. I'll revise it back. But I still think MyDef is more than lisp. I need find a lisp expert friend (that is willing to understand MyDef) to make better narration. :)