MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
1

1

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?

flag
Is $m > n$ or vice-versa? – Gilead Jun 22 2012 at 14:51
2 
 As it turns out, using an LP solver to solve linear equations isn't a terrible idea in practice. This may sound counter-intuitive, because it sounds overkill. However, because the efficiency of an LP solution depends so much on the linear algebra, good commercial LP solvers like CPLEX or Gurobi tend to incorporate highly optimized linear algebra routines (with excellent sparse matrix handling). There are other advantages to using an LP solvers: 1. matrix does not have to be square; 2. detection of inconsistencies through slacks; 3. inequality constrained solutions for underdefined systems. – Gilead Jun 22 2012 at 14:56
See here: amsterdamoptimization.com/pdf/lineq.pdf – Gilead Jun 22 2012 at 14:56

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.