Fast matrix multiplication and its algebraic neighbourhood
From MaRDI portal
Publication:4610195
DOI10.1070/SM8833zbMATH Open1476.68006OpenAlexW2748859075MaRDI QIDQ4610195FDOQ4610195
Authors: Victor Y. Pan 
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
Recommendations
- Algebraic complexity theory. II: Tast matrix multiplication and combinatorics.
- On practical algorithms for accelerated matrix multiplication
- Fast rectangular matrix multiplication and some applications
- Fast rectangular matrix multiplication and applications
- scientific article; zbMATH DE number 4088834
bilinear algorithmsmatrix multiplicationtensor decompositionexponent of matrix multiplicationfeasible matrix multiplication
Numerical linear algebra (65F99) 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) History of computer science (68-03) History of linear algebra (15-03)
Cites Work
- How bad are Vandermonde matrices?
- On cap sets and the group-theoretic approach to matrix multiplication
- Fast matrix multiplication without APA-algorithms
- Some Properties of Disjoint Sums of Tensors Related to Matrix Multiplication
- Algorithms for structured linear systems solving and their implementation
- Fast dynamic transitive closure with lookahead
- A Lower Bound for Matrix Multiplication
- Improving the numerical stability of fast matrix multiplication
- Fast matrix multiplication is stable
- Fast rectangular matrix multiplication and some applications
- Detecting short directed cycles using rectangular matrix multiplication and dynamic programming
- Title not available (Why is that?)
- On the asymptotic complexity of rectangular matrix multiplication
- On The Complexity Of Symmetric Computations*
- On obtaining upper bounds on the complexity of matrix multiplication
- Evaluation of rational functions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fast approximate computations with Cauchy matrices and polynomials
- Parallel Sparse Matrix-Matrix Multiplication and Indexing: Implementation and Experiments
- Communication lower bounds and optimal algorithms for numerical linear algebra
- Fast matrix multiplication using coherent configurations
- On the singular values of matrices with displacement structure
- On the complexity of matrix product
- Nearly optimal computations with structured matrices
- Graph expansion analysis for communication costs of fast rectangular matrix multiplication
- On the inequivalence of bilinear algorithms for \(3\times 3\) matrix multiplication
- Exploiting multiple levels of parallelism in sparse matrix-matrix multiplication
- Lower Bounds for Matrix Product
- Title not available (Why is that?)
- Title not available (Why is that?)
- Adaptive Winograd's matrix multiplications
- Motivation for working in numerical analysis
- Efficient algorithms on sets of permutations, dominance, and real-weighted APSP
- GEMMW: A portable level 3 BLAS Winograd variant of Strassen's matrix- matrix multiply algorithm
- Design, analysis, and implementation of a multiprecision polynomial rootfinder
- Title not available (Why is that?)
- Powers of tensors and fast matrix multiplication
- Title not available (Why is that?)
- Title not available (Why is that?)
- A fast algorithm for particle simulations
- Tensor Decompositions and Applications
- Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics
- An Algorithm for the Machine Calculation of Complex Fourier Series
- TT-cross approximation for multidimensional arrays
- Tensor approximations of matrices generated by asymptotically smooth functions
- Randomized Algorithms for Matrices and Data
- Gaussian elimination is not optimal
- Improved bound for complexity of matrix multiplication
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Partial and Total Matrix Multiplication
- Title not available (Why is that?)
- Triangular Factorization and Inversion by Fast Matrix Multiplication
- Accuracy and Stability of Numerical Algorithms
- Multiplying matrices faster than coppersmith-winograd
- How to multiply matrices faster
- Matrix multiplication via arithmetic progressions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A New Algorithm for Inner Product
- General context-free recognition in less than cubic time
- Modern computer algebra
- Fast context-free grammar parsing requires fast Boolean matrix multiplication
- Title not available (Why is that?)
- On the Asymptotic Complexity of Matrix Multiplication
- Title not available (Why is that?)
- \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
- New lower bounds for the rank of matrix multiplication
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the number of multiplications necessary to compute certain functions
- Regularity Lemmas and Combinatorial Algorithms
- Memory efficient scheduling of Strassen-Winograd's matrix multiplication algorithm
- A Strassen-like matrix multiplication suited for squaring and higher power computation
- On the arithmetic complexity of Strassen-like matrix multiplications
- On sunflowers and 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
- On the Additive Complexity of Matrix Multiplication
- FFPACK
- Title not available (Why is that?)
- Speeding up the four Russians algorithm by about one more logarithmic factor
- The aggregation and cancellation techniques as a practical tool for faster matrix multiplication
- Fast rectangular matrix multiplication and applications
- On Computations with Dense Structured Matrices
- On the exponent of all pairs shortest path problem
- Rectangular matrix multiplication revisited
- Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
- Title not available (Why is that?)
- Exploiting fast matrix multiplication within the level 3 BLAS
- Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)
- Fast sparse matrix multiplication
- Lower bounds for the bilinear complexity of associative algebras
- Computations with quasiseparable polynomials and matrices
- Superfast and stable structured solvers for Toeplitz least squares via randomized sampling
- Transformations of matrix structures work again
- A superfast structured solver for Toeplitz linear systems via randomized sampling
- Relations between exact and approximate bilinear algorithms. Applications
- The bilinear complexity and practical algorithms for matrix multiplication
- Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms
- On Winograd's Algorithm for Inner Products
- On Minimizing the Number of Multiplications Necessary for Matrix Multiplication
- On the additive complexity of 2 \(\times 2\) matrix multiplication
- Corrigendum to ``The rank of \(n{\times}n\) matrix multiplication is at least \(3n^2 - 2\sqrt{2}n^{\frac{3}{2}} - 3n\)
- Optimization techniques for small matrix multiplication
- Fast linear algebra is stable
- Approximate Solutions for the Bilinear Form Computational Problem
- Fast algorithms for \((\max, \min)\)-matrix multiplication and bottleneck shortest paths
- Trilinear aggregating with implicit canceling for a new acceleration of matrix multiplication
- On practical algorithms for accelerated matrix multiplication
- Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd's identity
- How Can We Speed Up Matrix Multiplication?
- Noncommutative Bilinear Algorithms for $3 \times 3$ Matrix Multiplication
- Title not available (Why is that?)
- Title not available (Why is that?)
- Stability of fast algorithms for matrix multiplication
- New combinations of methods for the acceleration of matrix multiplication
- Polynomial division with a remainder by means of evaluation and interpolation
- A practical algorithm for faster matrix multiplication
- Rapid Multiplication of Rectangular Matrices
- On the Number of Multiplications Required for Matrix Multiplication
- Title not available (Why is that?)
- The techniques of trilinear aggregating and the recent progress in the asymptotic acceleration of matrix operations
- Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
- 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
- Title not available (Why is that?)
- ON THE NUMBER OF MULTIPLICATIONS REQUIRED TO COMPUTE CERTAIN FUNCTIONS
- Title not available (Why is that?)
- On the optimal evaluation of a set of bilinear forms
- Title not available (Why is that?)
Cited In (26)
- Fast rectangular matrix multiplication and applications
- Fast Multiresolution Algorithms for Matrix-Vector Multiplication
- Title not available (Why is that?)
- Multiplying matrices faster than coppersmith-winograd
- How to multiply matrices faster
- Title not available (Why is that?)
- Automatic generation of fast algorithms for matrix–vector multiplication
- Nonlinear transformations of the matrix multiplication algorithm
- Heuristic algorithms for recognition of some cubic hypersurfaces
- Fast matrix multiplication is stable
- The techniques of trilinear aggregating and the recent progress in the asymptotic acceleration of matrix operations
- Symmetric matrices whose entries are linear functions
- Fast commutative matrix algorithms
- Fast algorithms with preprocessing for matrix-vector multiplication problems
- Fast vector arithmetic over \(\mathbb{F}_3\)
- Algorithm 898
- Strassen's \(2 \times 2\) matrix multiplication algorithm: a conceptual perspective
- Fast hybrid matrix multiplication algorithms
- Fast matrix decomposition in \(\mathbb F_2\)
- Matrix multiplication, a little faster
- Title not available (Why is that?)
- How Can We Speed Up Matrix Multiplication?
- A new fast root-finder for black box polynomials
- The aggregation and cancellation techniques as a practical tool for faster matrix multiplication
- Title not available (Why is that?)
- Fast multiplication of interval matrices (Interval version of Strassen's algorithm)
Uses Software
This page was built for publication: Fast matrix multiplication and its algebraic neighbourhood
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4610195)
