| The purpose of this thesis is to investigate the feasibility of applying the real-time paradigm to the problem of solving a system of linear equations. Unlike the conventional paradigm, the real-time paradigm is an environment characterized by the constant arrival of data and the existence of deadlines. The problem is stated as follows: Given a solution x0 of the system of equations A0x = b , with one or more of the entries of A0 changing to produce the system A1, is it possible to use x0 to obtain a solution x 1 without recomputing x1? We conjecture that this is not possible in general. This means that each time an update is received during the computation of the solution of a system of linear equations, the solution must be recomputed from scratch to accurately reflect the change (in the worst case). The only evidence to support this claim is an Ω( n) lower bound on such computations. A more convincing lower bound is required to prove our conjecture though one is not offered in this thesis. We demonstrate that while we believe it is impossible to use a previously computed solution to produce a new solution, it is possible to relax our real-time restrictions to produce a parallel solution that further improves upon the sequential solution by processing newly arriving data and producing more solutions in the same time frame. |
