Some computational problems in linear algebra as hard as matrix multiplication

DOI10.1007/BF01272518MaRDI QIDQ685718zbMATH OpenOpenAlexFDO

Authors Peter Bürgisser, Marek Karpinski, Thomas Lickteig

Publication date 10 October 1993

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01272518

zbMATH Keywords

computation treesderivationsOstrowski complexity measurestraight line programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Recommendations

• scientific article; zbMATH DE number 2151192
• Algebraic complexity theory. II: Tast matrix multiplication and combinatorics.
• The computational complexity of some problems of linear algebra
• Semi-algebraic complexity -- Additive complexity of matrix computational tasks
• Fast rectangular matrix multiplication and applications

Cites work

• Berechnung und Programm. I
• Berechnung und Programm. II
• Fast algorithms for the characteristic polynomial
• Gaussian elimination is not optimal
• scientific article; zbMATH DE number 3809415 (Why is no real title available?)
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 3461412 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3572315 (Why is no real title available?)
• Matrix multiplication via arithmetic progressions
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On the algorithmic complexity of associative algebras
• Relative bilinear complexity and matrix multiplication.
• The complexity of partial derivatives
• The Computational Complexity of Continued Fractions
• The trace invariant and matrix inversion
• Triangular Factorization and Inversion by Fast Matrix Multiplication
• Unitäre Transformationen großer Matrizen

Cited in

(6)

• Complexities of special matrix multiplication problems
• Semi-algebraic complexity -- Additive complexity of matrix computational tasks
• Lower bounds on the graver complexity of M-fold matrices
• Some independence results in complexity theory^†
• Sets of Linear Forms Which Are Hard to Compute
• Open problems in computational linear algebra

This page was built for publication: Some computational problems in linear algebra as hard as matrix multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685718)