[Bug-gsl] [bug #24418] fminimizer nmsimplex unnecessary size calculation

[Brian Gough]

URL:
  <http://savannah.gnu.org/bugs/?24418>

                 Summary: fminimizer nmsimplex unnecessary size calculation
                 Project: GNU Scientific Library
            Submitted by: bjg
            Submitted on: Tue 30 Sep 2008 07:27:17 PM BST
                Category: Performance
                Severity: 3 - Normal
        Operating System: 
                  Status: Confirmed
             Assigned to: None
             Open/Closed: Open
                 Release: 1.11
         Discussion Lock: Any

    _______________________________________________________

Details:

http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=500521

From: Ian Jackson <address@hidden>
To: address@hidden
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.







    _______________________________________________________

File Attachments:


-------------------------------------------------------
Date: Tue 30 Sep 2008 07:27:17 PM BST  Name: simplex_patch.c  Size: 6kB   By:
bjg

<http://savannah.gnu.org/bugs/download.php?file_id=16592>

    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?24418>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/