LU factorization with errors

DOI10.1145/3326229.3326244MaRDI QIDQ5120484zbMATH OpenOpenAlexWikidataFDO

Authors Jean-Guillaume Dumas, Joris van der Hoeven, Clément Pernet, Daniel S. Roche

Publication date 10 September 2020

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

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

zbMATH Keywords

algorithmserror correctionlinear algebramatrix factorizationsparse interpolation

Mathematics Subject Classification ID

Factorization of matrices (15A23) Direct numerical methods for linear systems and matrix inversion (65F05)

Abstract: 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.

Recommendations

• Publication:4893157
• Error correction in fast matrix multiplication and inverse
• scientific article; zbMATH DE number 3994890
• scientific article; zbMATH DE number 653400
• A new approach to backward error analysis of LU factorization

Cited in

(7)

• Efficiently correcting matrix products
• Efficiently correcting matrix products
• scientific article; zbMATH DE number 1735440 (Why is no real title available?)
• Fixed-parameter tractability of error correction in graphical linear systems
• Error correction in fast matrix multiplication and inverse
• Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs
• Corrigimus, verificamus, vincimus: ensuring algorithmic accuracy in an age of uncertainty

This page was built for publication: LU factorization with errors

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