Question

I want to use MATLAB linprog to solve a problem, and I check it by a much smaller, much simpler example.

But I wonder if MATLAB can support my real problem, there may be a 300*300*300*300 matrix...


Maybe I should give the exact problem. There is a directed graph of network nodes, and I want to get the lowest utilization of the edge capacity under some constraints. Let m be the number of edges, and n be the number of nodes. There are mn² variables and nm² constraints. Unfortunately, n may reach 300...

I want to use MATLAB linprog to solve it. As described above, I am afraid MATLAB can not support it...Lastly the matrix must be sparse, can some way simplify it?

Was it helpful?

Solution

First: a 300*300*300*300 array is not called a matrix, but a tensor (or simply array). Therefore you can not use matrix/vector algebra on it, because that is not defined for arrays with dimensionality greater than 2, and you can certainly not use it in linprog without some kind of interpretation step.

Second: if I interpret that 300⁴ to represent the number of elements in the matrix (and not the size), it really depends if MATLAB (or any other software) can support that.

As already answered by ben, if your matrix is full, then the answer is likely to be no. 300^4 doubles would consume almost 65GB of memory, so it's quite unlikely that any software package is going to be capable of handling that all from memory (unless you actually have > 65 GB of RAM). You could use a blockproc-type scheme, where you only load parts of the matrix in memory and leave the rest on harddisk, but that is insanely slow. Moreover, if you have matrices that huge, it's entirely possible you're overlooking some ways in which your problem can be simplified.

If you matrix is sparse (i.e., contains lots of zeros), then maybe. Have a look at MATLAB's sparse command.

So, what exactly is your problem? Where does that enormous matrix come from? Perhaps I or someone else sees a way in which to reduce that matrix to something more manageable.

OTHER TIPS

On my system, with 24GByte RAM installed, running Matlab R2013a, memory gives me:

Maximum possible array:     44031 MB (4.617e+10 bytes) *
Memory available for all arrays:     44031 MB (4.617e+10 bytes) *
Memory used by MATLAB:      1029 MB (1.079e+09 bytes)
Physical Memory (RAM):     24574 MB (2.577e+10 bytes)

*  Limited by System Memory (physical + swap file) available.

On a 64-bit version of Matlab, if you have enough RAM, it should be possible to at least create a full matrix as big as the one you suggest, but whether linprog can do anything useful with it in a realistic time is another question entirely.

As well as investigating the use of sparse matrices, you might consider working in single precision: that halves your memory usage for a start.

well you could simply try: X=zeros( 300*300*300*300 ) on my system it gives me a very clear statement:

>> X=zeros( 300*300*300*300 )
Error using zeros
Maximum variable size allowed by the program is exceeded.

since zeros is a build in function, which only fills a array of the given size with zeros you can asume that handling such a array will not be possible

you can also use the memory command

>> memory
Maximum possible array:     21549 MB (2.260e+10 bytes) *
Memory available for all arrays:     21549 MB (2.260e+10 bytes) *
Memory used by MATLAB:       685 MB (7.180e+08 bytes)
Physical Memory (RAM):     12279 MB (1.288e+10 bytes)

*  Limited by System Memory (physical + swap file) available.

>> 2.278e+10 /8   
%max bytes avail for arrays divided by 8 bytes for double-precision real values

ans =
2.8475e+09

>> 300*300*300*300

ans =
8.1000e+09

which means I dont even have the memory to store such a array.

while this may not answer your question directly it might still give you some insight.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top