I have a system of linear equations in form of $AX=b$ where $A_{m\times n}$, $X_{n\times 1}$ and $b_{m\times 1}$. Coefficient matrix $A$ is quite sparse. However, using a practical LP solver like LINGO it is clear that after permutation of rows, it turns out to be like a lower triangular matrix. I do not know what the permutation function should be. Since the matrix dimension is not square, I cannot use the LU decomposition to solve the system efficiently. Can you please let me know an efficient method for linear systems with non-square coefficient matrix?
$\begingroup$
$\endgroup$
6
-
$\begingroup$ Is your system overdetermined (m>n) or underdetermined (m<n)? If it is overdetermined, there may not be a solution and you might want to find the solution which minimizes the least square norm. If it is underdetermined, there may be many solutions and in this case often one finds a solution with the smallest L2 norm. $\endgroup$– CostisCommented Jun 22, 2012 at 12:51
-
$\begingroup$ My system is overdetermined. However, it is already an LP. I converted it to a system of linear equations because I need just a feasible solution for this LP. All the entries of the matrix $A$ are 0,+1,_1 and some numbers between (0,1]. It is quite sparse as well. $\endgroup$– StarCommented Jun 22, 2012 at 13:05
-
1$\begingroup$ Good LP solvers will find a suitable permutation by themselves. Feasibility is not significantly easier than optimality. Just try out some of the NEOS online solvers with your present formulation! $\endgroup$– Arnold NeumaierCommented Jun 22, 2012 at 15:13
-
$\begingroup$ If this question is really about LP feasibility, I feel that it's a duplicate of Star's LP feasibility question. Is this really supposed to be about LP feasibility? $\endgroup$– Geoff OxberryCommented Jun 22, 2012 at 17:20
-
$\begingroup$ If you are asking about a permutation of rows, the answer is simple if not trivial: sort the rows descending according to latest appearance (by column) of nonzero entries. If you are asking about both row and column entries, the problem is more interesting. $\endgroup$– hardmath ♦Commented Jun 22, 2012 at 19:37
|
Show 1 more comment