Quadratic-time certificates in linear algebra

DOI10.1145/1993886.1993915zbMath1323.68607OpenAlexW2068556643MaRDI QIDQ5254169

B. David Saunders, Michael Nehring, Erich L. Kaltofen

Publication date: 9 June 2015

Published in: Proceedings of the 36th international symposium on Symbolic and algebraic computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1993886.1993915

zbMATH Keywords

randomizationmatrix rankmatrix determinantFrobenius formprobabilistic proofoutput validation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Monte Carlo methods (65C05) Positive matrices and their generalizations; cones of matrices (15B48) Randomized algorithms (68W20)

Related Items (5)

Automating algorithm selection: checking for matrix properties that can simplify computations ⋮ Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs ⋮ Verification protocols with sub-linear communication for polynomial matrix operations ⋮ Elimination-based certificates for triangular equivalence and rank profiles ⋮ Recursive Double-Size Fixed Precision Arithmetic

This page was built for publication: Quadratic-time certificates in linear algebra