Barriers for rectangular matrix multiplication

DOI10.1007/S00037-025-00264-9MaRDI QIDQ7007039zbMATH OpenFDO

Authors Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam

Publication date 27 March 2025

Published in Computational Complexity (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00037-025-00264-9

zbMATH Keywords

Coppersmith-Winograd tensorsrectangular matrix multiplicationsupport functionals

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites work

• A Deterministic Linear Program Solver in Current Matrix Multiplication Time
• Barriers for fast matrix multiplication from irreversibility
• CVXPY: a Python-embedded modeling language for convex optimization
• Degeneration and complexity of bilinear maps: Some asymptotic spectra.
• Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract)
• Fast rectangular matrix multiplication and applications
• Fast rectangular matrix multiplication and some applications
• Faster algorithms for rectangular matrix multiplication
• Faster matrix multiplication via asymmetric hashing
• Faster rectangular matrix multiplication by combination loss analysis
• Further limitations of the known approaches for matrix multiplication
• Gaussian elimination is not optimal
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 7788370 (Why is no real title available?)
• Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor
• Limits on all known (and some unknown) approaches to matrix multiplication
• Limits on the Universal method for matrix multiplication
• Matrix multiplication via arithmetic progressions
• Multiplying matrices faster than coppersmith-winograd
• New bounds for matrix multiplication: from alpha to omega
• On cap sets and the group-theoretic approach to matrix multiplication
• On the asymptotic complexity of rectangular matrix multiplication
• Powers of tensors and fast matrix multiplication
• Rapid Multiplication of Rectangular Matrices
• Rectangular matrix multiplication revisited
• Relative bilinear complexity and matrix multiplication.
• Solving linear programs in the current matrix multiplication time
• The asymptotic spectrum of tensors.
• Universal points in the asymptotic spectrum of tensors

Cited in

(1)

• Asymptotic spectra: theory, applications, and extensions

This page was built for publication: Barriers for rectangular matrix multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7007039)