Find dominated or subsumed linear inequalities efficiently
Unfortunately there is a nearly-quadratic-time lower bound that may prove a barrier.  In particular, you can't solve it in $O(N^{2-\varepsilon})$ time for any $\varepsilon&gt;0$ unless the Strong Exponential Time Hypothesis is false.  In particular, the special case where all coefficients are 0 or 1 and the RHS is the same for all inequalities is equivalent to searching a bunch of sets for a pair that have a subset relationship, and that is hard: see https://cstheory.stackexchange.com/q/9896/5038.
The one saving grace is that this lower bound is for arbitrary sets, i.e., it does not take into account sparsity.  It is possible that you might be able to use sparsity somehow to do better than the general case.
Here is an algorithm that takes advantage of sparsity to do a bit better.  Suppose that every inequality has only $K$ nonzero coefficients.  Form a balanced binary tree on the $N$ inequalities.  Annotate each node with a map that maps $x_i$ to the max of all coefficients of $x_i$ in all inequalities under that node.  Now given an inequality $A$, you can check whether it dominates any other inequality by traversing the tree in a top-down breadthfirst fashion.  Any time you hit a node that maps $x_i$ to something smaller than $x_i$'s coefficient in $A$, there is no need to visit any of the children of that node, and traversal of that subtree can be skipped.  Heuristically, I expect you'll probably need to visit $O(KN/M)$ nodes of the tree on average (well, plus $O(\lg N)$ to account for the fact that each inequality dominates itself, but I'll ignore that as it seems likely to be small in comparison to the other terms).  Creating the tree takes $O(NK)$ time, and visiting each node takes $O(K)$ time, so I expect the overall running time per inequality will be something like $O(KN + K^2N/M)$, on average.  Since you have $N$ inequalities, the total time should be something like $O(KN + K^2N^2/M)$.  I don't know whether this is any better than what you already have in mind, though.