Re: [Help-glpk] Why 3 arrays in glp_load_matrix()

[Meketon, Marc]

Linear program matrices tend to be very sparse.  As an example assume a typical real-life linear program has 10000 rows and 40000 columns.  It is very common for a well formulated linear program of that size to have an average of 4 non-zero entries per column.  In our example, the ia, ja, ar arrays in GLPK would total 40000*4*16 bytes, or 2.44MB.  Using the normal matrix notation, as you suggested, would take 10000*40000*8 bytes, or 3GB.  A 1250:1 reduction in memory.  Note that 32-bit Windows usually does not allow more than about 1.5GB for program memory. 

 

More importantly, there is a huge savings in computations.  For example, consider the multiplication of Ax, where A is the 10000 x 40000 matrix and x is a 40000 x 1 column vector.  Without sparse matrix data structures, Ax would take around 381M of floating point operations.  But using sparsity, this could be done is 0.15M computations.

 

Lastly, the key computational step is to obtain the LU factorization of the basis.  Usually if the matrix is sparse, so is the L and U factors (although not quite as sparse).  The point is that GLPK is very careful to keep all matrices including the internal ones like L and U sparse so that storage and computational time is vastly reduced.

 

 

 

From: help-glpk-bounces+address@hidden [mailto:help-glpk-bounces+address@hidden On Behalf Of Dušan Plavák
Sent: Thursday, January 22, 2015 11:32 PM
To: address@hidden
Subject: [Help-glpk] Why 3 arrays in glp_load_matrix()

 

Hi there,

Why we have to use 3 arrays to define table?

 

from documentation:

 

ia[1] = 1, ja[1] = 1, ar[1] = 1.0; /* a[1,1] = 1 */

ia[2] = 1, ja[2] = 2, ar[2] = 1.0; /* a[1,2] = 1 */

ia[3] = 1, ja[3] = 3, ar[3] = 1.0; /* a[1,3] = 1 */

ia[4] = 2, ja[4] = 1, ar[4] = 10.0; /* a[2,1] = 10 */

ia[5] = 3, ja[5] = 1, ar[5] = 2.0; /* a[3,1] = 2 */

ia[6] = 2, ja[6] = 2, ar[6] = 4.0; /* a[2,2] = 4 */

ia[7] = 3, ja[7] = 2, ar[7] = 2.0; /* a[3,2] = 2 */

ia[8] = 2, ja[8] = 3, ar[8] = 5.0; /* a[2,3] = 5 */

ia[9] = 3, ja[9] = 3, ar[9] = 6.0; /* a[3,3] = 6 */

 

what about:

a[1][1] = 1

a[1][2] = 1

a[1]3] = 1

 

a[2][1] = 10

a[2][2] = 4

a[2][3] = 5

 

a[3][1] = 2

a[3][2] = 2

a[3][3] = 6

 

???

 

It is 27 vs 9 assignments;

 

Thanks

 

--

S pozdravom Dušan Plavák

---

This e-mail and any attachments may be confidential or legally privileged. If you received this message in error or are not the intended recipient, you should destroy the e-mail message and any attachments or copies, and you are prohibited from retaining, distributing, disclosing or using any information contained herein. Please inform us of the erroneous delivery by return e-mail. Thank you for your cooperation.