Fast matrix multiplication and its algebraic neighbourhood
From MaRDI portal
Publication:4610195
DOI10.1070/SM8833zbMath1476.68006OpenAlexW2748859075MaRDI QIDQ4610195
Publication date: 6 April 2018
Published in: Sbornik: Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1070/sm8833
tensor decompositionbilinear algorithmsmatrix multiplicationexponent of matrix multiplicationfeasible matrix multiplication
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) History of mathematics in the 20th century (01A60) History of numerical analysis (65-03) Numerical linear algebra (65F99) History of computer science (68-03) History of linear algebra (15-03)
Related Items
Symmetric matrices whose entries are linear functions, Heuristic algorithms for recognition of some cubic hypersurfaces, Strassen's \(2 \times 2\) matrix multiplication algorithm: a conceptual perspective
Uses Software
Cites Work
- Tensor Decompositions and Applications
- TT-cross approximation for multidimensional arrays
- On the arithmetic complexity of Strassen-like matrix multiplications
- On sunflowers and matrix multiplication
- Transformations of matrix structures work again
- Optimization techniques for small matrix multiplication
- The aggregation and cancellation techniques as a practical tool for faster matrix multiplication
- On the additive complexity of 2 \(\times 2\) matrix multiplication
- How to multiply matrices faster
- The techniques of trilinear aggregating and the recent progress in the asymptotic acceleration of matrix operations
- Fast dynamic transitive closure with lookahead
- Fast matrix multiplication is stable
- Matrix multiplication via arithmetic progressions
- Fast rectangular matrix multiplication and some applications
- Solving structured linear systems with large displacement rank
- On varieties of optimal algorithms for the computation of bilinear mappings. II. Optimal algorithms for \(2\times 2\)-matrix multiplication
- Stability of fast algorithms for matrix multiplication
- Relations between exact and approximate bilinear algorithms. Applications
- New combinations of methods for the acceleration of matrix multiplication
- Trilinear aggregating with implicit canceling for a new acceleration of matrix multiplication
- Fast matrix multiplication without APA-algorithms
- On the asymptotic complexity of rectangular matrix multiplication
- On practical algorithms for accelerated matrix multiplication
- Polynomial division with a remainder by means of evaluation and interpolation
- General context-free recognition in less than cubic time
- Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics
- On the optimal evaluation of a set of bilinear forms
- \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
- Fast rectangular matrix multiplication and applications
- Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z}\)]
- GEMMW: A portable level 3 BLAS Winograd variant of Strassen's matrix- matrix multiply algorithm
- On the exponent of all pairs shortest path problem
- Rectangular matrix multiplication revisited
- Design, analysis, and implementation of a multiprecision polynomial rootfinder
- An improved combinatorial algorithm for Boolean matrix multiplication
- Computations with quasiseparable polynomials and matrices
- Corrigendum to ``The rank of \(n{\times}n\) matrix multiplication is at least \(3n^2 - 2\sqrt{2}n^{\frac{3}{2}} - 3n\)
- On the inequivalence of bilinear algorithms for \(3\times 3\) matrix multiplication
- Fast linear algebra is stable
- Gaussian elimination is not optimal
- Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd's identity
- How Bad Are Vandermonde Matrices?
- Improving the Numerical Stability of Fast Matrix Multiplication
- Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication
- Improved bound for complexity of matrix multiplication
- Modern Computer Algebra
- Superfast and Stable Structured Solvers for Toeplitz Least Squares via Randomized Sampling
- Memory efficient scheduling of Strassen-Winograd's matrix multiplication algorithm
- The bilinear complexity and practical algorithms for matrix multiplication
- Fast sparse matrix multiplication
- A Strassen-like matrix multiplication suited for squaring and higher power computation
- Adaptive Winograd's matrix multiplications
- Randomized Algorithms for Matrices and Data
- Parallel Sparse Matrix-Matrix Multiplication and Indexing: Implementation and Experiments
- Fast context-free grammar parsing requires fast boolean matrix multiplication
- Powers of tensors and fast matrix multiplication
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- On Computations with Dense Structured Matrices
- On the complexity of matrix product
- How Can We Speed Up Matrix Multiplication?
- Noncommutative Bilinear Algorithms for $3 \times 3$ Matrix Multiplication
- Extra High Speed Matrix Multiplication on the Cray-2
- A Fast Adaptive Multipole Algorithm for Particle Simulations
- New Fast Algorithms for Matrix Operations
- Approximate Solutions for the Bilinear Form Computational Problem
- Partial and Total Matrix Multiplication
- Some Properties of Disjoint Sums of Tensors Related to Matrix Multiplication
- On the Asymptotic Complexity of Matrix Multiplication
- Rapid Multiplication of Rectangular Matrices
- Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms
- On the Additive Complexity of Matrix Multiplication
- On the Number of Multiplications Required for Matrix Multiplication
- A Lower Bound for Matrix Multiplication
- Exploiting fast matrix multiplication within the level 3 BLAS
- Triangular Factorization and Inversion by Fast Matrix Multiplication
- On The Complexity Of Symmetric Computations*
- Lower Bounds for Matrix Product
- On the Singular Values of Matrices with Displacement Structure
- On cap sets and the group-theoretic approach to matrix multiplication
- FFPACK
- Tensor approximations of matrices generated by asymptotically smooth functions
- Communication lower bounds and optimal algorithms for numerical linear algebra
- Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
- Accuracy and Stability of Numerical Algorithms
- A Superfast Structured Solver for Toeplitz Linear Systems via Randomized Sampling
- Graph Expansion Analysis for Communication Costs of Fast Rectangular Matrix Multiplication
- Evaluation of Rational Functions
- On Obtaining Upper Bounds on the Complexity of Matrix Multiplication
- Algorithms for Structured Linear Systems Solving and Their Implementation
- Regularity Lemmas and Combinatorial Algorithms
- Fast approximate computations with Cauchy matrices and polynomials
- An Algorithm for the Machine Calculation of Complex Fourier Series
- Speeding up the Four Russians Algorithm by About One More Logarithmic Factor
- Multiplying matrices faster than coppersmith-winograd
- New Lower Bounds for the Rank of Matrix Multiplication
- Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
- A New Algorithm for Inner Product
- ON THE NUMBER OF MULTIPLICATIONS REQUIRED TO COMPUTE CERTAIN FUNCTIONS
- On the number of multiplications necessary to compute certain functions
- On Winograd's Algorithm for Inner Products
- On Minimizing the Number of Multiplications Necessary for Matrix Multiplication
- Fast matrix multiplication using coherent configurations
- Motivation for working in numerical analysis
- A fast algorithm for particle simulations
- Nearly optimal computations with structured matrices
- Lower bounds for the bilinear complexity of associative algebras
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
