Powers of tensors and fast matrix multiplication

DOI10.1145/2608628.2608664zbMath1325.65061arXiv1401.7714OpenAlexW2120248756WikidataQ56699885 ScholiaQ56699885MaRDI QIDQ3452408

François Le Gall

Publication date: 11 November 2015

Published in: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1401.7714

zbMATH Keywords

algebraic complexity theorymatrix multiplication

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Multilinear algebra, tensor calculus (15A69)

Related Items (only showing first 100 items - show all)

Strong collapse and persistent homology ⋮ Planar and Toroidal Morphs Made Easier ⋮ Unnamed Item ⋮ On Matrices With Displacement Structure: Generalized Operators and Faster Algorithms ⋮ Meet-in-the-middle attack with splice-and-cut technique and a general automatic framework ⋮ Skew-polynomial-sparse matrix multiplication ⋮ Counting Homomorphic Cycles in Degenerate Graphs ⋮ Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ A faster interior-point method for sum-of-squares optimization ⋮ Reverse-Safe Text Indexing ⋮ Triangle‐free equimatchable graphs ⋮ A modeling and computational study of the frustration index in signed networks ⋮ Towards Practical Fast Matrix Multiplication based on Trilinear Aggregation ⋮ Linear‐time algorithms for eliminating claws in graphs ⋮ A new algebraic approach to the regular syndrome decoding problem and implications for PCG constructions ⋮ Alternative fan-beam backprojection and adjoint operators ⋮ Pebbling Game and Alternative Basis for High Performance Matrix Multiplication ⋮ Bottleneck matching in the plane ⋮ Concise tensors of minimal border rank ⋮ Multi-task subspace clustering ⋮ Interpolation-based decoding of folded variants of linearized and skew Reed-Solomon codes ⋮ Fine-Grained Complexity of Regular Path Queries ⋮ Numerically stable iterative methods for computing matrix sign function ⋮ Bad and good news for Strassen's laser method: border rank of \(\mathrm{Perm}_3\) and strict submultiplicativity ⋮ Irreversibility of structure tensors of modules ⋮ Jacobi's bound: Jacobi's results translated in Kőnig's, Egerváry's and Ritt's mathematical languages ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ A fast randomized geometric algorithm for computing Riemann-Roch spaces ⋮ Asymptotic stability of probabilistic logical networks with random impulsive effects ⋮ Tropical Geometry ⋮ On Regularity Lemmas and their Algorithmic Applications ⋮ Bounds and algorithms for graph trusses ⋮ Unnamed Item ⋮ Nearly Work-Efficient Parallel Algorithm for Digraph Reachability ⋮ Border Rank Is Not Multiplicative under the Tensor Product ⋮ Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time. ⋮ On the index of convergence of a class of Boolean matrices with structural properties ⋮ Space Hardness of Solving Structured Linear Systems. ⋮ A Rank 18 Waring Decomposition of sM_〈3〉 with 432 Symmetries ⋮ Hanani-Tutte for approximating maps of graphs ⋮ Extraction of deflating subspaces using disk function of a matrix pencil via matrix sign function with application in generalized eigenvalue problem ⋮ Improved FPT Algorithms for Deletion to Forest-Like Structures ⋮ Computing cyclic invariants for molecular graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Convexity-increasing morphs of planar graphs ⋮ Improving the Complexity of Block Low-Rank Factorizations with Fast Matrix Arithmetic ⋮ Realization problems on reachability sequences ⋮ Unnamed Item ⋮ The descriptive complexity of subgraph isomorphism without numerics ⋮ Rare siblings speed-up deterministic detection and counting of small pattern graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Limits on the Universal method for matrix multiplication ⋮ Faster Algorithms for All Pairs Non-Decreasing Paths Problem ⋮ Barriers for fast matrix multiplication from irreversibility ⋮ Unnamed Item ⋮ Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors ⋮ Algorithms for Weighted Matching Generalizations II: f-factors and the Special Case of Shortest Paths ⋮ Efficient Algorithm for Computing the Triangle Maximizing the Length of Its Smallest Side Inside a Convex Polygon ⋮ Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles ⋮ Elastic-Degenerate String Matching via Fast Matrix Multiplication ⋮ Dominance Product and High-Dimensional Closest Pair under L_infty ⋮ Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication ⋮ Some aspects of the database resilience ⋮ The Faddeev-LeVerrier algorithm and the Pfaffian ⋮ A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers ⋮ Solving \((k-1)\)-stable instances of \texttt{k-terminal cut} with isolating cuts ⋮ Rectilinear link diameter and radius in a rectilinear polygonal domain ⋮ Faster geometric algorithms via dynamic determinant computation ⋮ A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes ⋮ Quantum and approximation algorithms for maximum witnesses of Boolean matrix products ⋮ On the sizes of DPDAs, PDAs, LBAs ⋮ On the nuclear norm and the singular value decomposition of tensors ⋮ On the complexity of integer matrix multiplication ⋮ Beyond the BEST theorem: fast assessment of Eulerian trails ⋮ Rural postman parameterized by the number of components of required edges ⋮ An improved combinatorial algorithm for Boolean matrix multiplication ⋮ Planar and toroidal morphs made easier ⋮ Bounds on complexity of matrix multiplication away from Coppersmith-Winograd tensors ⋮ Fast commutative matrix algorithms ⋮ Algebraic secret sharing using privacy homomorphisms for IoT-based healthcare systems ⋮ A linear time algorithm for the nullity of vertex-weighted block graphs ⋮ On the word problem for special monoids ⋮ Equimatchable claw-free graphs ⋮ An introduction to the computational complexity of matrix multiplication ⋮ Efficient computation of tridiagonal matrices largest eigenvalue ⋮ A decomposition algorithm for computing income taxes with pass-through entities and its application to the Chilean case ⋮ Why does deep and cheap learning work so well? ⋮ A simple spectral algorithm for recovering planted partitions ⋮ Induced subgraph isomorphism: are some patterns substantially easier than others? ⋮ Computing mixed volume and all mixed cells in quermassintegral time ⋮ Fast matrix multiplication by using color algebras ⋮ Simple realizability of complete abstract topological graphs simplified ⋮ Clustered planarity testing revisited ⋮ Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization ⋮ Directed evaluation ⋮ Computing syzygies in finite dimension using fast linear algebra

Uses Software

• Jordan

Cites Work

• Unnamed Item
• Unnamed Item
• An effective implementation of symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
• Cylindrical algebraic decomposition using validated numerics
• The Jordan Curve Theorem, Formally and Informally
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Definability and decision problems in arithmetic

This page was built for publication: Powers of tensors and fast matrix multiplication