TY - GEN
T1 - LU factorization with errors
AU - Dumas, Jean Guillaume
AU - Pernet, Clément
AU - Van Der Hoeven, Joris
AU - Roche, Daniel S.
N1 - Publisher Copyright:
© 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM.
PY - 2019/7/8
Y1 - 2019/7/8
N2 - 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.
AB - 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.
KW - Algorithms
KW - Error correction
KW - Linear algebra
KW - Matrix factorization
KW - Sparse interpolation
U2 - 10.1145/3326229.3326244
DO - 10.1145/3326229.3326244
M3 - Conference contribution
AN - SCOPUS:85069786487
T3 - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC
SP - 131
EP - 138
BT - ISSAC 2019 - Proceedings of the 2019 ACM International Symposium on Symbolic and Algebraic Computation
PB - Association for Computing Machinery
T2 - 44th ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2019
Y2 - 15 July 2019 through 18 July 2019
ER -