Re: [Help-glpk] lpx_load_matrix

[Jeff Abrahamson]

On Sun, Sep 12, 2004 at 12:16:08PM +0400, Andrew Makhorin wrote:
> >(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;
> }

Yes, and this is what I did in my code so as not to be dependent on a
custom modification to glpk.  But the patch would leave the user with
the choice: prune the input arrays or let glpk do it.  There's no cost
to glpk, it's doing the if() anyway.


> >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.

Agreed, that's why I didn't spend any time on it.  I just hear my
high-performance computing colleagues talk about this sort of thing
and how it was common in Fortran days but kills modern processors.

I wouldn't try to optimize something I hadn't profiled, but I might,
in my own code, avoid styles that are likely to cause poor cache
performance when the overhead of doing so is slight.

I probably spoke too strongly, I didn't mean to slight GLPK.

-- 
 Jeff

 Jeff Abrahamson  <http://www.purple.com/jeff/>    +1 215/837-2287
 GPG fingerprint: 1A1A BA95 D082 A558 A276  63C6 16BF 8C4C 0D1D AE4B

 A cool book of games, highly worth checking out:
 http://www.amazon.com/exec/obidos/ASIN/1931686963/purple-20

signature.asc
Description: Digital signature