# 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. – MCH Jul 18 '12 at 17:49
• Yes, it seems so. But, I need something fast. – Star Jul 18 '12 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 '12 at 19:57
• @Gopi this IS linear programming, factorization won't help by itself. – Sasho Nikolov Jul 19 '12 at 4:55
• @Gopi you were this close to a strongly polynomial time algorithm for linear programming ;) – Sasho Nikolov Jul 19 '12 at 15:29