## Computing Best Possible Pseudo-Solutions to Interval Linear Systems of Equations

South Ural State University, Chelyabinsk, Russia

Reliable Computing, Volume 19, p. 215-228, 2014

@article{panyukov2014computing,

title={Computing Best Possible Pseudo-Solutions to Interval Linear Systems of Equations},

author={Panyukov, Anatoly V and Golodov, Valentin A},

year={2014}

}

In the paper, we consider interval linear algebraic systems of equations Ax = b, with an interval matrix A and interval right-hand side vector b, as a model of imprecise systems of linear algebraic equations of the same form. We propose a new regularization procedure that reduces the solution of the imprecise linear system to computing a point from the tolerable solution set for the interval linear system with a widened right-hand side. The points from the tolerable solution set to the widened interval linear system are called pseudo-solutions, while the best pseudo-solutions are those corresponding to the minimal extension of the right-hand side that produces a nonempty tolerable solution set. We prove the existence of the best pseudo-solutions and propose a method for their computation, as a solution to a linear programming problem. Since the auxiliary linear programming problem may become nearly degenerate, it is necessary to perform computations with a precision that substantially exceeds that of the standard floating point data types. A simplex method with errorless rational computations gives an effective solution to the problem. Coarse-grained parallelism for distributed computer systems using MPI and the software for errorless rational calculations using CUDA C small-grained parallelism are the main instruments of our suitable implementation.

January 26, 2014 by hgpu