[math-fun] Grochow/Moore: "Matrix multiplication algorithms from group orbits"
Some of us may like the preprint at https://arxiv.org/abs/1612.01527 Abstract: We show how to construct highly symmetric algorithms for matrix multiplication. In particular, we consider algorithms which decompose the matrix multiplication tensor into a sum of rank-1 tensors, where the decomposition itself consists of orbits under some finite group action. We show how to use the representation theory of the corresponding group to derive simple constraints on the decomposition, which we solve by hand for n=2,3,4,5, recovering Strassen's algorithm (in a particularly symmetric form) and new algorithms for larger n. While these new algorithms do not improve the known upper bounds on tensor rank or the matrix multiplication exponent, they are beautiful in their own right, and we point out modifications of this idea that could plausibly lead to further improvements. Our constructions also suggest further patterns that could be mined for new algorithms, including a tantalizing connection with lattices. Best regards, jj
Thanks, Joerg! I’m happy to talk about this if people are interested. - cris
On Dec 8, 2016, at 10:11 AM, Joerg Arndt <arndt@jjj.de> wrote:
Some of us may like the preprint at https://arxiv.org/abs/1612.01527
Abstract: We show how to construct highly symmetric algorithms for matrix multiplication. In particular, we consider algorithms which decompose the matrix multiplication tensor into a sum of rank-1 tensors, where the decomposition itself consists of orbits under some finite group action. We show how to use the representation theory of the corresponding group to derive simple constraints on the decomposition, which we solve by hand for n=2,3,4,5, recovering Strassen's algorithm (in a particularly symmetric form) and new algorithms for larger n. While these new algorithms do not improve the known upper bounds on tensor rank or the matrix multiplication exponent, they are beautiful in their own right, and we point out modifications of this idea that could plausibly lead to further improvements. Our constructions also suggest further patterns that could be mined for new algorithms, including a tantalizing connection with lattices.
Best regards, jj
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Yes, please, talk about this some more! I always considered Strassen's algorithm to be a bit of a hack; I'm glad to see that someone has finally made some sense of this approach. At 10:06 AM 12/8/2016, Cris Moore wrote:
Thanks, Joerg! I'm happy to talk about this if people are interested. - cris
Yes, I’m happy that we found a very symmetric form of it. Some other people have been thinking along the same lines, including Burichenko and [CILO] (cited in the paper). C
On Dec 8, 2016, at 11:33 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Yes, please, talk about this some more!
I always considered Strassen's algorithm to be a bit of a hack; I'm glad to see that someone has finally made some sense of this approach.
At 10:06 AM 12/8/2016, Cris Moore wrote:
Thanks, Joerg! I'm happy to talk about this if people are interested. - cris
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Hi Cris: I noticed that there are a number of YouTube talk videos by folks in this matrixmult/tensor/geometry community. Any that you would recommend? Questions: I noticed that you use bra-ket notation; are there any relations to quantum mechanics here? 3x3 matrix multiplication; any relationship with *quaternions* here? Did I understand correctly that 2x2 is related to the symmetry of a equilateral triangle in n-space (what is 'n' here?) Did I understand correctly that 3x3 is related to the symmetry of a tetrahedron in n-space (what is 'n' here?) At 01:02 PM 12/8/2016, Cris Moore wrote:
Yes, I'm happy that we found a very symmetric form of it.
Some other people have been thinking along the same lines, including Burichenko and [CILO] (cited in the paper).
C
On Dec 8, 2016, at 11:33 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Yes, please, talk about this some more!
I always considered Strassen's algorithm to be a bit of a hack; I'm glad to see that someone has finally made some sense of this approach.
At 10:06 AM 12/8/2016, Cris Moore wrote:
Thanks, Joerg! I'm happy to talk about this if people are interested. - cris
I noticed that there are a number of YouTube talk videos by folks in this matrixmult/tensor/geometry community. Any that you would recommend?
I’m not sure - I’ll have to take a look. There’s a good review paper here: http://theoryofcomputing.org/articles/gs005/ <http://theoryofcomputing.org/articles/gs005/>
I noticed that you use bra-ket notation; are there any relations to quantum mechanics here?
that’s a cultural thing - really it’s just row and column vectors. That way <u|v> is an inner product, and |u><v| is an outer product.
3x3 matrix multiplication; any relationship with *quaternions* here?
I’ve thought about that a little - it would be great! - but I don’t know of one.
Did I understand correctly that 2x2 is related to the symmetry of a equilateral triangle in n-space (what is 'n' here?)
yes, where n=2 (n is the size of matrices we’re multiplying)
Did I understand correctly that 3x3 is related to the symmetry of a tetrahedron in n-space (what is 'n' here?)
yes, where n=3, and so on for higher-dimensional simplices - although for n > 2 this construction is not optimal in terms of the tensor rank. - cris
At 01:02 PM 12/8/2016, Cris Moore wrote:
Yes, I'm happy that we found a very symmetric form of it.
Some other people have been thinking along the same lines, including Burichenko and [CILO] (cited in the paper).
C
On Dec 8, 2016, at 11:33 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Yes, please, talk about this some more!
I always considered Strassen's algorithm to be a bit of a hack; I'm glad to see that someone has finally made some sense of this approach.
At 10:06 AM 12/8/2016, Cris Moore wrote:
Thanks, Joerg! I'm happy to talk about this if people are interested. - cris
Just to make sure that I understand correctly, see inline questions below. At 09:20 AM 12/9/2016, Cris Moore wrote:
Did I understand correctly that 2x2 is related to the symmetry of a equilateral triangle in n-space (what is 'n' here?)
yes, where n=2 (n is the size of matrices we're multiplying)
I.e., this is *not* the symmetric group on 3 elements, but the cyclic group of 3 elements, correct?
Did I understand correctly that 3x3 is related to the symmetry of a tetrahedron in n-space (what is 'n' here?)
yes, where n=3, and so on for higher-dimensional simplices - although for n > 2 this construction is not optimal in terms of the tensor rank.
I.e., this is *not* the symmetric group on 4 elements, but the symmetry group of the equilateral tetrahedron in ordinary 3-space? --- Using the same tensor ideas, are there closely related problems that *would* result in the symmetric group of 3 elements; 4 elements? What would such a "generalized matrix multiplication" look like? Any chance that the idea of *solvable groups* comes up in relation to the matrix mult problem? Does this "geometric" line of attack have any elegant treatment of *determinant* computation?
Did I understand correctly that 2x2 is related to the symmetry of a equilateral triangle in n-space (what is 'n' here?)
yes, where n=2 (n is the size of matrices we're multiplying)
I.e., this is *not* the symmetric group on 3 elements, but the cyclic group of 3 elements, correct?
In fact it’s the symmetric group, or alternately the dihedral group. So it includes all 3!=6 permutations.
I.e., this is *not* the symmetric group on 4 elements, but the symmetry group of the equilateral tetrahedron in ordinary 3-space?
For n > 2, what matters in this particular family of constructions (we’re looking for others as well) is that we act on the vertices of the simplex in a 3-transitive way. [That means that any ordered triple of distinct elements can get sent to any other ordered triple.] In n dimensions, this simplex has n+1 vertices. So in n=3 we use S_4, in n=4 we use A_5 (the even permutations of 5 objects), and in n=5 we use a funky embedding of S_5 in S_6 that acts 3-transitively on subsets of {1,2,3,4,5,6} of size 3.
Any chance that the idea of *solvable groups* comes up in relation to the matrix mult problem?
Well, there’s a nice theory of permutation groups and when you can have 3-transitivity, 4-transitivity, etc. without having all permutations (or at least all even ones).
Does this "geometric" line of attack have any elegant treatment of *determinant* computation?
I’m not sure. As you probably know, understanding the determinant vs. the permanent in an algebraic/geometric way is one of the major goals of this field. My collaborator Josh Grochow knows a lot more about this than I do… - Cris
Some additional questions: What about extended sequences of 2x2 matrix multiplications? Are there any savings if you're doing a sequence? What about *quaternion multiplication* itself? This can be done with fewer than the obvious number of scalar (Q1: real; Q2: complex) multiplications. Does this new theory provide any more insight into minimizing quaternion multiplication? What about quaternion rotations -- e.g., qvq* -- where q* is the quaternion conjugate of q ? Can this theory take advantage of the fact that q=q0+w, q*=q0-w, where q0 is real and w is a real 3-vector? Are there any new insights into FFT's -- e.g., a novel/elegant exposition? At 09:58 AM 12/9/2016, Cris Moore wrote:
Did I understand correctly that 2x2 is related to the symmetry of a equilateral triangle in n-space (what is 'n' here?)
yes, where n=2 (n is the size of matrices we're multiplying)
I.e., this is *not* the symmetric group on 3 elements, but the cyclic group of 3 elements, correct?
In fact it's the symmetric group, or alternately the dihedral group. So it includes all 3!=6 permutations.
I.e., this is *not* the symmetric group on 4 elements, but the symmetry group of the equilateral tetrahedron in ordinary 3-space?
For n > 2, what matters in this particular family of constructions (we're looking for others as well) is that we act on the vertices of the simplex in a 3-transitive way. [That means that any ordered triple of distinct elements can get sent to any other ordered triple.]
In n dimensions, this simplex has n+1 vertices. So in n=3 we use S_4, in n=4 we use A_5 (the even permutations of 5 objects), and in n=5 we use a funky embedding of S_5 in S_6 that acts 3-transitively on subsets of {1,2,3,4,5,6} of size 3.
Any chance that the idea of *solvable groups* comes up in relation to the matrix mult problem?
Well, there's a nice theory of permutation groups and when you can have 3-transitivity, 4-transitivity, etc. without having all permutations (or at least all even ones).
Does this "geometric" line of attack have any elegant treatment of *determinant* computation?
I'm not sure. As you probably know, understanding the determinant vs. the permanent in an algebraic/geometric way is one of the major goals of this field. My collaborator Josh Grochow knows a lot more about this than I do - Cris
participants (3)
-
Cris Moore -
Henry Baker -
Joerg Arndt