Tue 30 Sep 2008 06:27:17 PM UTC, original submission:
http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=500521
From: Ian Jackson <ijackson@chiark.greenend.org.uk>
To: -unavailable-
Subject: fminimizer nmsimplex unnecessary size calculation
Date: Mon, 29 Sep 2008 02:21:59 +0100
Package: gsl
Version: 1.8-2
Tags: patch
Severity: wishlist
The minimiser
gsl_multimin_fminimizer_nmsimplex
always computes the simplex size for each step. This is done using
gsl_blas_dnrm2 which is quite careful. This computation involves
around n^2 divisions (where n is the problem dimensionality).
For high-dimensionality problems this can easily dominate useful work.
The caller might try to work around this by calling
gsl_multimin_fminimizer_size less often but this is ineffective
because the size calculation is actually done each time the simplex is
modified by _iterate or _set.
The attached patch arranges to
- not calculate the size unless it is requested
- cache the returned value so that existing programs are no slower
Unfortunately this requires us to drop the `const' from the prototype
of gsl_multimin_fminimizer_size. But I think this is still a good
tradeoff.
An alternative option would be to always call ->get_size and not
bother caching. That would make slower any existing programs that
call _fminimizer_size but wouldn't need a change of prototype. That
might be acceptable given that the performance properties of _size
are not spelled out.
Ian.
|