# Solving a system of linear inequations

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

• In general (for arbitrary $A$), your problem is equivalent to linear programming. Jul 18, 2012 at 17:49
• Yes, it seems so. But, I need something fast.
– Star
Jul 18, 2012 at 17:57
• This forum is dedicated to Theoretical Computer Science question. Maybe you should try asking your question on Computer Science where it may be more welcolmed by the community?
– Gopi
Jul 18, 2012 at 19:57
• @Gopi this IS linear programming, factorization won't help by itself. Jul 19, 2012 at 4:55
• @Gopi you were this close to a strongly polynomial time algorithm for linear programming ;) Jul 19, 2012 at 15:29