Plethysm and fast matrix multiplication

Tim Seynnaeve

doi:10.1016/j.crma.2017.11.012

Lie algebras/Computer science

Plethysm and fast matrix multiplication

Presented by: Michèle Vergne

Tim Seynnaeve ¹

¹ Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22, 04103, Leipzig, Germany

Comptes Rendus. Mathématique, Volume 356 (2018) no. 1, pp. 52-55.

Abstract
Résumé

Motivated by the symmetric version of matrix multiplication we study the plethysm $S^{k} ({sl}_{n})$ of the adjoint representation ${sl}_{n}$ of the Lie group $S L_{n}$ . In particular, we describe the decomposition of this representation into irreducible components for $k = 3$ , and find highest-weight vectors for all irreducible components. Relations to fast matrix multiplication, in particular the Coppersmith–Winograd tensor, are presented.

Motivés par la version symétrique de la multiplication des matrices, nous étudions le pléthysme $S^{k} ({sl}_{n})$ de la représentation adjointe ${sl}_{n}$ du groupe de Lie $S L_{n}$ . En particulier, pour $k = 3$ , nous décrivons la décomposition de cette représentation en composantes irréductibles, et nous trouvons les vecteurs de plus grand poids pour toutes ces dernières. Nous présentons les liens avec la multipliction rapide des matrices, notamment le tenseur de Coppersmith–Winograd.

Received: 2017-10-10
Accepted: 2017-11-20
Published online: 2017-12-06

DOI: 10.1016/j.crma.2017.11.012

Author's affiliations:

Tim Seynnaeve ¹

¹ Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22, 04103, Leipzig, Germany

@article{CRMATH_2018__356_1_52_0,
     author = {Tim Seynnaeve},
     title = {Plethysm and fast matrix multiplication},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {52--55},
     publisher = {Elsevier},
     volume = {356},
     number = {1},
     year = {2018},
     doi = {10.1016/j.crma.2017.11.012},
     language = {en},
}

TY  - JOUR
AU  - Tim Seynnaeve
TI  - Plethysm and fast matrix multiplication
JO  - Comptes Rendus. Mathématique
PY  - 2018
SP  - 52
EP  - 55
VL  - 356
IS  - 1
PB  - Elsevier
DO  - 10.1016/j.crma.2017.11.012
LA  - en
ID  - CRMATH_2018__356_1_52_0
ER  -

%0 Journal Article
%A Tim Seynnaeve
%T Plethysm and fast matrix multiplication
%J Comptes Rendus. Mathématique
%D 2018
%P 52-55
%V 356
%N 1
%I Elsevier
%R 10.1016/j.crma.2017.11.012
%G en
%F CRMATH_2018__356_1_52_0

Tim Seynnaeve. Plethysm and fast matrix multiplication. Comptes Rendus. Mathématique, Volume 356 (2018) no. 1, pp. 52-55. doi : 10.1016/j.crma.2017.11.012. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2017.11.012/

References
Cited by

[1] P. Bürgisser; M. Clausen; M.A. Shokrollahi Algebraic Complexity Theory, Grundlehren der Mathematischen Wissenschaften, Fundamental Principles of Mathematical Sciences, vol. 315, Springer-Verlag, Berlin, 1997 (With the collaboration of Thomas Lickteig)

[2] L. Chiantini; J.D. Hauenstein; C. Ikenmeyer; J.M. Landsberg; G. Ottaviani Polynomials and the exponent of matrix multiplication, 2017 (arXiv preprint) | arXiv

[3] H. Cohn; C. Umans A group-theoretic approach to fast matrix multiplication, Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on, IEEE, 2003, pp. 438-449

[4] D. Coppersmith; S. Winograd Matrix multiplication via arithmetic progressions, J. Symb. Comput., Volume 9 (1990) no. 3, pp. 251-280

[5] W. Fulton; J. Harris Representation Theory: A First Course, vol. 129, Springer Science & Business Media, 2013

[6] R. Howe $({GL}_{n}, {GL}_{m})$ -duality and symmetric plethysm, Proc. Indian Acad. Sci. Math. Sci., Volume 97 (1988) no. 1–3, pp. 85-109 (1987)

[7] T. Kahle; M. Michałek Plethysm and lattice point counting, Found. Comput. Math., Volume 16 (2016) no. 5, pp. 1241-1261

[8] J.M. Landsberg Tensors: Geometry and Applications, Graduate Studies in Mathematics, vol. 128, American Mathematical Society, Providence, RI, 2012

[9] J.M. Landsberg Geometry and Complexity Theory, Cambridge Studies in Advanced Mathematics, Cambridge University Press, 2017

[10] J.M. Landsberg; M. Michałek On the geometry of border rank decompositions for matrix multiplication and other tensors with symmetry, SIAM J. Appl. Algebra Geom., Volume 1 (2017) no. 1, pp. 2-19

[11] J.M. Landsberg; M. Michałek Abelian tensors, J. Math. Pures Appl., Volume 108 (2017) no. 3, pp. 333-371

[12] J.M. Landsberg; M. Michałek A lower bound for the border rank of matrix multiplication, Int. Math. Res. Not. (2017) (rnx025)

[13] J.M. Landsberg; G. Ottaviani New lower bounds for the border rank of matrix multiplication, Theory Comput., Volume 11 (2015), pp. 285-298

[14] F. Le Gall Powers of tensors and fast matrix multiplication, ISSAC 2014—Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2014, pp. 296-303

[15] I.G. Macdonald Symmetric Functions and Hall Polynomials, Oxford University Press, 1998

[16] L. Manivel; M. Michałek Secants of minuscule and cominuscule minimal orbits, Linear Algebra Appl., Volume 481 (2015), pp. 288-312

[17] S.P.O. Plunkett On the plethysm of S-functions, Can. J. Math., Volume 24 (1972), pp. 541-552

[18] V. Strassen Gaussian elimination is not optimal, Numer. Math., Volume 13 (1969) no. 4, pp. 354-356

[19] R.M. Thrall On symmetrized Kronecker powers and the structure of the free Lie ring, Amer. J. Math., Volume 64 (1942), pp. 371-388

[20] V.V. Williams Multiplying matrices faster than Coppersmith–Winograd [extended abstract], STOC'12—Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 887-898

Cited by Sources:

Comments - Policy