Re: [Help-glpk] lpx_load_matrix

[Andrew Makhorin]

>I believe the answer to my question is the following: lpx_load_matrix
>expects the arrays to be passed such that ar has no zero values.
>
>I have attached a patch to fix this.  It simply ignores entries whose
>ar value is 0.  At least in my case, it would have simplified my code
>to have been able to pass a sparse matrix written out completely
>rather than being obliged to compact it myself.  The patch is
>compatible with existing client code except in the case that the
>client depends on getting an error for a zero ar entry.
>
>(Note that the patch is really just four lines: an if statement and
>its closing brace as well as deleting the fault line.  But it changes
>indentation, so it's longer.)

It is better to remove zero coefficients before call to lpx_load_matrix
using, say, the following routine:

int remove_zeros(int ne, int ia[], int ja[], double ar[])
{     int k, new_ne = 0;
      for (k = 1; k <= ne; k++)
      {  if (ar[k] != 0.0)
         {  new_ne++;
            ia[new_ne] = ia[k];
            ja[new_ne] = ja[k];
            ar[new_ne] = ar[k];
         }
      }
      return new_ne;
}

>The routine has another problem that I have not fixed:
>
>Presenting the values as three arrays, ia, ja, and ar, increases the
>likelihood of cache misses over defining a structure
>
>    struct coeff { int i; int j; double val; }
>
>and passing an array of these structures.  (This can be significant at
>the level of L1 or L2 cache, which are much smaller.  Normally VM
>cache is too large to be affected.)

(ia,ja,ar) corresponds to so-called "storage-by-indices" format, which
is widely used in many sparse matrix packages. Note that lpx_load_matrix
refers not only to input data, but to internal glpk data which have more
complicated structure, so even smooth access to input data using your
data structure would not allow exploiting the cache memory efficiently.
However, loading the matrix takes a tiny percentage of the total solution
time, so "optimizing" lpx_load_matrix gives no practical gain.

Andrew Makhorin