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.
How feasibility of this system can be checked without using linear programming?
Is the ellipsoid method useful for checking feasibility of the corresponding polyhedral?