عنوان

Parametric Linear System Solving with Error Correction

Number

TL52400

.Language of Text, Soundtrack etc

انگلیسی

Title Proper

Parametric Linear System Solving with Error Correction

General Material Designation

[Thesis]

First Statement of Responsibility

Waddell, Cleveland Alexander

Subsequent Statement of Responsibility

Blackman, Terrance

Name of Publisher, Distributor, etc.

North Carolina State University

Date of Publication, Distribution, etc.

2019

Text of Note

162 p.

Dissertation or thesis details and type of degree

Ph.D.

Body granting the degree

North Carolina State University

Text preceding or following the note

2019

Text of Note

Consider solving a black box linear system, A(u)x = b(u), where the entries are polynomials in u over a field K, and A(u) is full rank. The solution, x = (1/g(u))ƒ(u), where g is always the least common monic denominator, can be recovered even if some evaluations are erroneous. In [Boyer and Kaltofen, Proc. SNC 2014] the problem is solved with an algorithm that generalizes Welch/Berlekamp decoding of an algebraic Reed-Solomon code. Their algorithm requires the sum of a degree bound for the numerators plus a degree bound for the denominator of the solution. We describe an algorithm that given the same inputs uses possibly fewer evaluations to compute the solution. We introduce a second count for the number of evaluations required to recover the solution based on work by Stanley Cabay. The Cabay count includes bounds for the highest degree polynomial in the coefficient matrix and right side vector, but does not require solution degree bounds. Instead our algorithm iterates until the Cabay termination criterion is reached. At this point our algorithm returns the solution. Assuming we have the actual degrees for all necessary input parameters, we give the criterion that determines when the Cabay count is fewer than the generalized Welch/Berlekamp count. We then specialize the algorithm for parametric linear system solving to the recovery of a vector of rational functions, (1/g(u))ƒ(u). If the rational function vector is the solution to a full rank linear system our early termination strategy applies and we may recover it from fewer evaluations than generalized Welch/Berlekamp decoding. We then show that if entries in our rational function vector are polynomials, then the vector can be viewed as an interleaved Reed-Solomon code. Thus if the errors occur in bursts we can again do better than generalized Welch/Berlekamp decoding. The aforementioned algorithms do not work when the matrix of the system, A(u)x = b(u), is rank deficient and some evaluations cause errors. We next present an algorithm for solving black box linear systems where the entries are polynomials over a field and the matrix of the system is rank deficient. The algorithm first locates and removes all errors, after which it computes a solution that satisfies the input degree bounds. Finally we view the recovery of a vector of polynomials as the decoding of interleaved Reed-Solomon codes. It is known that interleaved schemes improve the error correction capabilities of codes when errors occur in bursts. If we consider that the evaluations of the polynomials in the vector are done one at a time and that the errors are dependent then it is likely that errors occur in consecutive evaluations (bursts). An error model that considers consecutive entries in the vector to be wrong is a burst error model. We show how to encode and transmit data (polynomials) so that the data (polynomials) transmitted can be recovered with fewer evaluations than is required by Generalized Welch/Berlekamp decoding.

Subject Term

Applied mathematics

Waddell, Cleveland Alexander

Blackman, Terrance

North Carolina State University

Electronic name

p

[Thesis]

276903

a

Y