The computational complexity of some problems of linear algebra (extended abstract)

DOI10.1007/BFB0023480MaRDI QIDQ5048945zbMATH OpenOpenAlexFDO

Authors Jonathan F. Buss, Gudmund S. Frandsen, Jeffrey Shallit

Publication date 9 November 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

matrix rank

Mathematics Subject Classification ID

Vector spaces, linear dependence, rank, lineability (15A03) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The computational complexity of some problems of linear algebra
• On the complexity of matrix rank and rigidity
• scientific article; zbMATH DE number 1256731
• On the Complexity of Matrix Rank and Rigidity
• The complexity of matrix rank and feasible systems of linear equations

Cites work

• A note on matrix rigidity
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• scientific article; zbMATH DE number 3876606 (Why is no real title available?)
• scientific article; zbMATH DE number 42574 (Why is no real title available?)
• scientific article; zbMATH DE number 3467028 (Why is no real title available?)
• scientific article; zbMATH DE number 3597878 (Why is no real title available?)
• scientific article; zbMATH DE number 1261801 (Why is no real title available?)
• scientific article; zbMATH DE number 1306875 (Why is no real title available?)
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals

Cited in

(12)

• The complexity of linear problems in fields
• The bit complexity of matrix multiplication and of related computations in linear algebra. The segmented algorithms
• The communication complexity of several problems in matrix computation
• The computational complexity of some problems of linear algebra
• The complexity of matrix rank and feasible systems of linear equations
• Combinatorial optimization methods to determine the rank of a matrix over a commutative ring, with engineering applications
• Computational Complexity and Numerical Stability of Linear Problems
• scientific article; zbMATH DE number 1256731 (Why is no real title available?)
• scientific article; zbMATH DE number 2072707 (Why is no real title available?)
• Interval Linear Algebra and Computational Complexity
• Communication complexity of matrix computation over finite fields
• Multivariate signatures with polynomial factorization

This page was built for publication: The computational complexity of some problems of linear algebra (extended abstract)

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