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

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 ⋮ 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 ⋮ Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Universal points in the asymptotic spectrum of tensors ⋮ Deterministic Truncation of Linear Matroids ⋮ Computing minimal interpolation bases ⋮ A note on the complexity of computing the number of reachable vertices in a digraph ⋮ Complexity of constructing Dixon resultant matrix ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Faster sparse multivariate polynomial interpolation of straight-line programs ⋮ Extreme Witnesses and Their Applications ⋮ New applications of the polynomial method: The cap set conjecture and beyond ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ A note on the gap between rank and border rank ⋮ Abelian tensors ⋮ On the complexity exponent of polynomial system solving ⋮ Complexity bounds for approximately solving discounted MDPs by value iterations ⋮ Improved exact algorithms for mildly sparse instances of MAX SAT ⋮ The Complexity of Escaping Labyrinths and Enchanted Forests. ⋮ Sketching with Kerdock's Crayons: Fast Sparsifying Transforms for Arbitrary Linear Maps ⋮ Efficiently correcting matrix products ⋮ Time and space efficient generators for quasiseparable matrices ⋮ Data-driven model reduction by moment matching for linear and nonlinear systems ⋮ Efficiently Correcting Matrix Products ⋮ 3D Rectangulations and Geometric Matrix Multiplication ⋮ Quantum Complexity of Boolean Matrix Multiplication and Related Problems ⋮ Maximum matching width: new characterizations and a fast algorithm for dominating set ⋮ Solving the clique cover problem on (bull, \(C_4\))-free graphs ⋮ Lower bounds for Boolean circuits of bounded negation width ⋮ Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back ⋮ Fast computation of the \(N\)-th term of a \(q\)-holonomic sequence and applications ⋮ Some fast algorithms multiplying a matrix by its adjoint ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Tensor surgery and tensor rank ⋮ Asymptotic tensor rank of graph tensors: beyond matrix multiplication ⋮ Improved bounds for rectangular monotone min-plus product and applications ⋮ Retracted: Invertible matrices over some quotient rings: identification, generation, and analysis ⋮ On the evaluation of some sparse polynomials ⋮ In search of hyperpaths ⋮ Unnamed Item ⋮ Revisiting Decomposition by Clique Separators ⋮ Fast matrix multiplication and its algebraic neighbourhood ⋮ Computing isomorphisms and embeddings of finite fields ⋮ A Fast Deterministic Detection of Small Pattern Graphs in Graphs Without Large Cliques ⋮ The Complexity of Perfect Packings in Dense Graphs ⋮ Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the Boolean Convolution ⋮ Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model ⋮ Further Limitations of the Known Approaches for Matrix Multiplication ⋮ Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product ⋮ Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs ⋮ Efficient and Adaptive Parameterized Algorithms on Modular Decompositions ⋮ Strong Collapse for Persistence ⋮ K-plex cover pooling for graph neural networks ⋮ Algorithms and conditional lower bounds for planning problems ⋮ Deterministic computation of the characteristic polynomial in the time of matrix multiplication ⋮ Fast amortized multi-point evaluation ⋮ On cap sets and the group-theoretic approach to matrix multiplication ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximating the minimum cycle mean ⋮ Unnamed Item ⋮ Improved method for finding optimal formulas for bilinear maps in a finite field ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Strassen's \(2 \times 2\) matrix multiplication algorithm: a conceptual perspective ⋮ Packing $A$-Paths in Group-Labelled Graphs via Linear Matroid Parity ⋮ The complexity of perfect matchings and packings in dense hypergraphs ⋮ Fast computation of approximant bases in canonical form ⋮ Sparse matrix multiplication and triangle listing in the congested clique model ⋮ Cryptanalysis of Feistel Networks with Secret Round Functions ⋮ Rectilinear link diameter and radius in a rectilinear polygonal domain ⋮ Polynomial-Time Algorithms for Multiple-Arm Identification with Full-Bandit Feedback ⋮ Hamming Distance Completeness ⋮ Computing Persistent Homology of Flag Complexes via Strong Collapses ⋮ On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic ⋮ Testing proximity to subspaces: approximate \(\ell_\infty\) minimization in constant time ⋮ Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. ⋮ Improving the Numerical Stability of Fast Matrix Multiplication ⋮ Upgrading Subgroup Triple-Product-Property Triples ⋮ Exact and approximation algorithms for weighted matroid intersection ⋮ Border Rank Nonadditivity for Higher Order Tensors ⋮ Improved distance queries and cycle counting by Frobenius normal form ⋮ A fourth-order method for computing the sign function of a matrix with application in the Yang-Baxter-like matrix equation ⋮ Acyclic Digraphs ⋮ Logical complexity of induced subgraph isomorphism for certain families of graphs ⋮ Grothendieck constant is norm of Strassen matrix multiplication tensor ⋮ Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ On hardness of several string indexing problems ⋮ On the complexity of the \(F_5\) Gröbner basis algorithm ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ 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 ⋮ \(c\)-planarity of embedded cyclic \(c\)-graphs ⋮ Correlation matrices with average constraints ⋮ Algorithms for simultaneous Hermite-Padé approximations ⋮ 3D rectangulations and geometric matrix multiplication ⋮ Robust classification via MOM minimization ⋮ Lazy or eager dynamic matching may not be fast ⋮ A simple approach to nondecreasing paths ⋮ Plethysm and fast matrix multiplication ⋮ Fast structured matrix computations: tensor rank and Cohn-Umans method ⋮ Parameterized complexity of determinant and permanent ⋮ Efficient algorithms for solving the \(p\)-Laplacian in polynomial time ⋮ First-order definitions of subgraph isomorphism through the adjacency and order relations ⋮ Solutions for subset sum problems with special digraph constraints ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Representations of torsion-free arithmetic matroids ⋮ Towards a geometric approach to Strassen's asymptotic rank conjecture ⋮ The complexity of computing all subfields of an algebraic number field ⋮ New ways to multiply \(3 \times 3\)-matrices ⋮ Work-sensitive dynamic complexity of formal languages ⋮ Analysis of the scheduling mechanism for virtualization of links with partial isolation ⋮ A fast deterministic detection of small pattern graphs in graphs without large cliques ⋮ Improved distance sensitivity oracles with subcubic preprocessing time ⋮ Sign properties of Metzler matrices with applications ⋮ A new faster algorithm for factoring skew polynomials over finite fields ⋮ Efficient computation of the characteristic polynomial of a threshold graph ⋮ Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth ⋮ Revealed preference theory: an algorithmic outlook ⋮ Verification protocols with sub-linear communication for polynomial matrix operations ⋮ Drinfeld modules with complex multiplication, Hasse invariants and factoring polynomials over finite fields ⋮ Counting invariant subspaces and decompositions of additive polynomials ⋮ Fast computation of generic bivariate resultants ⋮ Entanglement distillation from Greenberger-Horne-Zeilinger shares ⋮ Computing the bound of an Ore polynomial. Applications to factorization ⋮ On the minimum number of general or dedicated controllers required for system controllability ⋮ Algebraic methods in the congested clique ⋮ Fast likelihood calculation for multivariate Gaussian phylogenetic models with shifts ⋮ Can we beat the square root bound for ECDLP over \(\mathbb{F}_p^2\) via representation? ⋮ Modular composition via factorization ⋮ An efficient finite element solution using a large pre-solved regular element ⋮ Two bilinear \((3\times3)\)-matrix multiplication algorithms of complexity 25 ⋮ A fully polynomial parameterized algorithm for counting the number of reachable vertices in a digraph ⋮ Subquadratic-time algorithms for normal bases ⋮ An improved upper bound on maximal clique listing via rectangular fast matrix multiplication ⋮ Extreme witnesses and their applications ⋮ A fast algorithm for all-pairs Hamming distances ⋮ Faster algorithms for counting subgraphs in sparse graphs ⋮ Detecting and enumerating small induced subgraphs in \(c\)-closed graphs ⋮ Computing the depth distribution of a set of boxes ⋮ The role of randomness in the broadcast congested clique model ⋮ An algebraic attack on rank metric code-based cryptosystems ⋮ Small one-dimensional Euclidean preference profiles ⋮ Rank and border rank of Kronecker powers of tensors and Strassen's laser method ⋮ Fast approximate shortest paths in the congested clique ⋮ Subset selection for matrices with fixed blocks ⋮ Geometric adaptive Monte Carlo in random environment ⋮ Equivalent polyadic decompositions of matrix multiplication tensors ⋮ Computing Puiseux series: a fast divide and conquer algorithm ⋮ Enumeration complexity of conjunctive queries with functional dependencies ⋮ Invertible matrices over some quotient rings: identification, generation, and analysis ⋮ Sparse regression with output correlation for cardiac ejection fraction estimation ⋮ On the theory of dynamic graph regression problem ⋮ Polynomial modular product verification and its implications ⋮ A sequential regression model for big data with attributive explanatory variables ⋮ On the complexity of skew arithmetic ⋮ Approximate minimum directed spanning trees under congestion ⋮ On the effect of projection on rank attacks in multivariate cryptography

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