How to multiply matrices faster
From MaRDI portal
Publication:799337
zbMath0548.65022MaRDI QIDQ799337
Publication date: 1984
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
monographmatrix inversioncondition numbersbilinear algorithmsmatrix multiplicationStrassen's algorithmcomplexity of algorithmsall pair shortest distance problemAPA- algorithmsasymptotically fast algorithmsbit-time and bit-space conceptsprecision approximation algorithmstrilinear aggregating
Analysis of algorithms and problem complexity (68Q25) Theory of matrix inversion and generalized inverses (15A09) Research exposition (monographs, survey articles) pertaining to numerical analysis (65-02) Numerical computation of matrix norms, conditioning, scaling (65F35) Numerical computation of determinants (65F40) Direct numerical methods for linear systems and matrix inversion (65F05)
Related Items
Oracle computations in parallel numerical linear algebra, On the complexity of linear quadratic control, A non-recursive algorithm for classifying the states of a finite Markov chain, Binary segmentation for matrix and vector operations, Polynomial division and its computational complexity, Algebraic complexity of computing polynomial zeros, Parallel nested dissection for path algebra computations, Complexity of parallel matrix computations, Nonuniform ACC Circuit Lower Bounds, Rectangular matrix multiplication revisited, Semi-algebraic complexity -- Additive complexity of matrix computational tasks, A logarithmic Boolean time algorithm for parallel polynomial division, FAST MATRIX MULTIPLICATION ALGORITHMS ON MIMD ARCHITECTURES, On the arithmetic complexity of Strassen-like matrix multiplications, Rapid parallel computation of degrees in a quotient ring of polynomials over a finite field, An improved parallel algorithm that computes the BFS numbering of a directed graph, Algebraic and numerical techniques for the computation of matrix determinants, Bilinear mincing rank, Parallel evaluation of the determinant and of the inverse of a matrix, The bit complexity of matrix multiplication and of related computations in linear algebra. The segmented \(\lambda\) algorithms, Matrix structures in parallel matrix computations, Optimal and nearly optimal algorithms for approximating polynomial zeros, Speedup for natural problems and noncomputability, Bad and good news for Strassen's laser method: border rank of \(\mathrm{Perm}_3\) and strict submultiplicativity, Guessing singular dependencies, Fast matrix multiplication and its algebraic neighbourhood, Matrix multiplication via arithmetic progressions, On multivariate polynomials in Bernstein-Bézier form and tensor algebra, On practical algorithms for accelerated matrix multiplication, Statistical complexity of dominant eigenvector calculation, On the evaluation of the eigenvalues of a banded Toeplitz block matrix, Extended concept of significant digits and lower precision computations, Lower bounds for the non-linear complexity of algebraic computation trees with integer inputs, Parametrization of Newton's iteration for computations with structured matrices and applications, Optimization techniques for small matrix multiplication, Fast and efficient linear programming and linear least-squares computations, Newton's method and FFT trading, On the direct sum conjecture in the straight line model, Information-based complexity: New questions for mathematicians, Matrix multiplication for finite algebraic systems, Fast rectangular matrix multiplication and applications, Fast finite methods for a system of linear inequalities, Using fast matrix multiplication to find basic solutions, Efficient parallel linear programming, Fast and efficient solution of path algebra problems, Fast and efficient parallel solution of dense linear systems, Why does information-based complexity use the real number model?, Algorithms for fast convolutions on motion groups, Comparison of Accuracy and Scalability of Gauss--Newton and Alternating Least Squares for CANDECOMC/PARAFAC Decomposition, The techniques of trilinear aggregating and the recent progress in the asymptotic acceleration of matrix operations, FFT-like multiplication of linear differential operators, Bit complexity of matrix products, On the complexity of a pivot step of the revised simplex algorithm, On transformations of algorithms to multiply 2\(\times 2\) matrices, On the complexity of skew arithmetic
