Plethysm and fast matrix multiplication

Seynnaeve, Tim

doi:10.1016/j.crma.2017.11.012

Lie algebras/Computer science

Plethysm and fast matrix multiplication
[Pléthysme et multiplication rapide des matrices]

Présenté par : Michèle Vergne

Seynnaeve, Tim ¹

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

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

Résumé
Abstract

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.

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.

Reçu le : 2017-10-10
Accepté le : 2017-11-20
Publié le : 2017-12-06

DOI : 10.1016/j.crma.2017.11.012

Affiliations des auteurs :

Seynnaeve, Tim ¹

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

@article{CRMATH_2018__356_1_52_0,
     author = {Seynnaeve, Tim},
     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},
     url = {http://archive.numdam.org/articles/10.1016/j.crma.2017.11.012/}
}

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

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

Seynnaeve, Tim. Plethysm and fast matrix multiplication. Comptes Rendus. Mathématique, Tome 356 (2018) no. 1, pp. 52-55. doi : 10.1016/j.crma.2017.11.012. http://archive.numdam.org/articles/10.1016/j.crma.2017.11.012/

Bibliographie
Cité par

[1] Bürgisser, P.; Clausen, M.; Shokrollahi, M.A. 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] Chiantini, L.; Hauenstein, J.D.; Ikenmeyer, C.; Landsberg, J.M.; Ottaviani, G. Polynomials and the exponent of matrix multiplication, 2017 (arXiv preprint) | arXiv

[3] Cohn, H.; Umans, C. 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] Coppersmith, D.; Winograd, S. Matrix multiplication via arithmetic progressions, J. Symb. Comput., Volume 9 (1990) no. 3, pp. 251-280

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

[6] Howe, R. $({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] Kahle, T.; Michałek, M. Plethysm and lattice point counting, Found. Comput. Math., Volume 16 (2016) no. 5, pp. 1241-1261

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

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

[10] Landsberg, J.M.; Michałek, M. 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] Landsberg, J.M.; Michałek, M. Abelian tensors, J. Math. Pures Appl., Volume 108 (2017) no. 3, pp. 333-371

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

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

[14] Le Gall, F. 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] Macdonald, I.G. Symmetric Functions and Hall Polynomials, Oxford University Press, 1998

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

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

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

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

[20] Williams, V.V. 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

Cité par Sources :