# Checking feasibility of a system of inequalities

Consider the following system of inequalities:

$$Ax=b \\ x\geq 0$$

$A$ is a $m\times n$ (non-square) and sparse matrix in which some part of entries are rational.

1. How feasibility of this system can be checked without using linear programming?

2. Is the ellipsoid method useful for checking feasibility of the corresponding polyhedral?

-
I would guess that finding feasible points to this system is almost equivalent to LP. The ellipsoid method is not considered to be effective practically. Primal-dual interior methods are (but also, simplex is still pretty good). –  copper.hat Jul 19 '12 at 16:03
The question is whether feasibility of this polyhedral can be checked using ellipsoid method. Since in my problem entries are partly rational. If yes, what is the running time. I need it for theoretical part not practical side. –  Star Jul 19 '12 at 16:13