2019/01/30 by Jean‐Guillaume Dumas, Joris van der Hoeven, Dumas, Jean-Guillaume +5
Computer Science · Mathematics · #FOS: Computer and information sciences #Information Theory (cs.IT) #Matrix Theory and Algorithms #Polynomial and algebraic computation #Symbolic Computation (cs.SC) #Tensor decomposition and applications
paper · doi:10.48550/arxiv.1901.10730
openalex publication_date 2019/01/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present new algorithms to detect and correct errors in the lower-upper factorization of a matrix, or the triangular linear system solution, over an arbitrary field. Our main 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 dimension times the number of errors when there are few errors, smoothly growing to the cost of fast matrix multiplication as the number of errors increases. We also present applications to general linear system solving.