
From:  Meketon, Marc 
Subject:  Re: [Helpglpk] Why 3 arrays in glp_load_matrix() 
Date:  Thu, 22 Jan 2015 23:11:49 0600 
Linear program matrices tend to be very sparse. As an example assume a typical reallife 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 nonzero 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 32bit 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: helpglpkbounces+address@hidden [mailto:helpglpkbounces+address@hidden
On Behalf Of Dušan Plavák 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 email 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 email 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 email. Thank you for your cooperation. 
[Prev in Thread]  Current Thread  [Next in Thread] 