Error correction in fast matrix multiplication and inverse

DOI10.1145/3208976.3209001MaRDI QIDQ5120215zbMATH OpenOpenAlexWikidataFDO

Authors Daniel S. Roche

Publication date 9 September 2020

Published in Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.02270

zbMATH Keywords

algorithmserror correctionlinear algebramatrix multiplicationsparse interpolation

Mathematics Subject Classification ID

Numerical linear algebra (65F99) Analysis of algorithms (68W40)

Abstract: We present new algorithms to detect and correct errors in the product of two matrices, or the inverse of a matrix, over an arbitrary field. Our algorithms do not require any additional information or encoding other than the original inputs and the erroneous output. Their running time is softly linear in the number of nonzero entries in these matrices when the number of errors is sufficiently small, and they also incorporate fast matrix multiplication so that the cost scales well when the number of errors is large. These algorithms build on the recent result of Gasieniec et al (2017) on correcting matrix products, as well as existing work on verification algorithms, sparse low-rank linear algebra, and sparse polynomial interpolation.

Recommendations

• Efficiently correcting matrix products
• Efficiently correcting matrix products
• LU factorization with errors
• Error-free transformations of matrix multiplication by using fast routines of matrix multiplication and its applications
• A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits

Cited in

(9)

• Algorithm-based fault tolerance for matrix inversion with maximum pivoting
• Efficiently correcting matrix products
• Efficiently correcting matrix products
• Error‐free transformation of matrix multiplication with a posteriori validation
• On nondeterministic derandomization of Freivalds' algorithm: consequences, avenues and algorithmic progress
• LU factorization with errors
• Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs
• Correcting matrix products over the ring of integers
• Corrigimus, verificamus, vincimus: ensuring algorithmic accuracy in an age of uncertainty

This page was built for publication: Error correction in fast matrix multiplication and inverse

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