Numerical linear system solving with parametric entries by error correction

Abstract

We consider the problem of solving a full rank consistent linear system A(u)x = b(u) where the m x n matrix A and the m-dimensional vector b has entries that are polynomials in u over a field. We give an algorithm that computes the unique solution x = f(u)/g(u), which is a vector of rational functions, by evaluating the parameter u at distinct points. Those points ξλ where the matrix A evaluates to a matrix A(ξλ), with entries over the scalar field, of lower rank, or in the numeric setting to an ill-conditioned matrix, are not identified but accounted for by error-correcting code techniques. We also correct true errors where the evaluation at some u = ξλ results in an erroneous, possibly full rank consistent and well-conditioned scalar linear system. Our algorithm generalizes Welch/Berlekamp decoding of Reed/Solomon error correcting codes and their numeric floating point counterparts.