sparse marix and linprog

Hi I want to solve linear programming model in MATLAB with linprog function. I need to create eye matrix in 994840x994840. I want to create it with sparse(eye(994840)), but I got "out of memory" error. Is it any way to solve my problem?

Thank you.

Answer 1

[Matt J]

   speye(994840)

[Matt J]

In general, it is not a good idea to create a sparse matrix using the syntax

   sparse(full_matrix)

unless you're sure you want to sacrifice efficiency for simplicity. It is more efficient to do

   sparse(i,j,s,...)

or dedicated things like speye().

[Matt J]

Also, do not use a sparse identity matrix to implement upper and lower bounds on the variables, if that's what you were planning to do. Use the lb, ub input arguments.

[fatema saba]

Thank you Matt. It works but I have the same problem in creating ones(994840). How can I use sparse command for this(ones(994840))?

Thanks

[John D'Errico]

ones(994840) will be a FULL matrix. There are no zeros at all. So use of a sparse form to store it will be less efficient. It will require more memory to store than a simple full matrix, since sparse is only efficient when the matrix is actually sparse.

Anyway, you don't want to create ones(994840), a matrix that would require

994840*994840*8 = 7917653004800

bytes to store, so roughly 8 terabytes of memory there!

[Matt J]

fatema,

As John says, trying to explicitly create a matrix as large and memory-consuming as ones(994840) is too brute force. You need to look to more indirect ways. If you show us the problem in more detail, we might be able to give better advice.

As an example, if you're doing this because some subset of your inequality constraints looks like

     [ones(N), S]*x<=b

where S is an NxM sparse or small matrix and N=994840, then you could introduce an additional unknown variable q and impose the equality constraint,

    q=[ones(1,N), zeros(1,M)]*x

Now the inequality constraints can be replaced by

   [ones(N,1), sparse(N,N), S]*[q;x]<=b

But notice that modified constraint matrix

    A=[ones(N,1), sparse(N,N), S]

is now much more sparse and manageable.