Debian Bug report logs - #500521
fminimizer nmsimplex unnecessary size calculation

version graph

Package: gsl; Maintainer for gsl is Dirk Eddelbuettel <edd@debian.org>;

Reported by: Ian Jackson <ijackson@chiark.greenend.org.uk>

Date: Mon, 29 Sep 2008 01:24:01 UTC

Severity: wishlist

Tags: patch

Found in version 1.8-2

Fixed in version gsl/1.11+dfsg-2

Done: Dirk Eddelbuettel <edd@debian.org>

Bug is archived. No further changes may be made.

Forwarded to Brian Gough <bjg@network-theory.co.uk>

Toggle useless messages

View this report as an mbox folder, status mbox, maintainer mbox


Report forwarded to debian-bugs-dist@lists.debian.org, Dirk Eddelbuettel <edd@debian.org>:
Bug#500521; Package gsl. (Mon, 29 Sep 2008 01:24:04 GMT) Full text and rfc822 format available.

Acknowledgement sent to Ian Jackson <ijackson@chiark.greenend.org.uk>:
New Bug report received and forwarded. Copy sent to Dirk Eddelbuettel <edd@debian.org>. (Mon, 29 Sep 2008 01:24:04 GMT) Full text and rfc822 format available.

Message #5 received at submit@bugs.debian.org (full text, mbox):

From: Ian Jackson <ijackson@chiark.greenend.org.uk>
To: submit@bugs.debian.org
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.




Information forwarded to debian-bugs-dist@lists.debian.org, Dirk Eddelbuettel <edd@debian.org>:
Bug#500521; Package gsl. (Tue, 30 Sep 2008 00:03:06 GMT) Full text and rfc822 format available.

Acknowledgement sent to Ian Jackson <ijackson@chiark.greenend.org.uk>:
Extra info received and forwarded to list. Copy sent to Dirk Eddelbuettel <edd@debian.org>. (Tue, 30 Sep 2008 00:03:06 GMT) Full text and rfc822 format available.

Message #10 received at 500521@bugs.debian.org (full text, mbox):

From: Ian Jackson <ijackson@chiark.greenend.org.uk>
To: 500521@bugs.debian.org
Subject: Re: Bug#500521: Acknowledgement (fminimizer nmsimplex unnecessary size calculation)
Date: Tue, 30 Sep 2008 01:00:02 +0100
I forgot to attach the patch.

diff -u orig/gsl-1.8/multimin/fminimizer.c gsl-1.8/multimin/fminimizer.c
--- orig/gsl-1.8/multimin/fminimizer.c	2005-06-26 14:25:35.000000000 +0100
+++ gsl-1.8/multimin/fminimizer.c	2008-09-29 02:07:29.000000000 +0100
@@ -90,7 +90,9 @@
 
   gsl_vector_memcpy (s->x,x);
 
-  return (s->type->set) (s->state, s->f, s->x, &(s->size), step_size);
+  s->simplex_size_valid = 0;
+
+  return (s->type->set) (s->state, s->f, s->x, step_size);
 }
 
 void
@@ -105,7 +107,9 @@
 int
 gsl_multimin_fminimizer_iterate (gsl_multimin_fminimizer * s)
 {
-  return (s->type->iterate) (s->state, s->f, s->x, &(s->size), &(s->fval));
+  s->simplex_size_valid = 0;
+
+  return (s->type->iterate) (s->state, s->f, s->x, &(s->fval));
 }
 
 const char * 
@@ -128,7 +132,12 @@
 }
 
 double
-gsl_multimin_fminimizer_size (const gsl_multimin_fminimizer * s)
+gsl_multimin_fminimizer_size (gsl_multimin_fminimizer * s)
 {
-  return s->size;
+  if (!s->simplex_size_valid)
+    {
+      s->simplex_size = (s->type->get_size) (s->state);
+      s->simplex_size_valid = 1;
+    }
+  return s->simplex_size;
 }
Only in gsl-1.8/multimin: fminimizer.c~
diff -u orig/gsl-1.8/multimin/gsl_multimin.h gsl-1.8/multimin/gsl_multimin.h
--- orig/gsl-1.8/multimin/gsl_multimin.h	2005-06-26 14:25:35.000000000 +0100
+++ gsl-1.8/multimin/gsl_multimin.h	2008-09-29 02:08:17.000000000 +0100
@@ -84,13 +84,12 @@
   int (*alloc) (void *state, size_t n);
   int (*set) (void *state, gsl_multimin_function * f,
               const gsl_vector * x, 
-              double * size,
               const gsl_vector * step_size);
   int (*iterate) (void *state, gsl_multimin_function * f, 
                   gsl_vector * x, 
-                  double * size,
                   double * fval);
   void (*free) (void *state);
+  double (*get_size) (void *state);
 }
 gsl_multimin_fminimizer_type;
 
@@ -103,7 +102,8 @@
   double fval;
   gsl_vector * x;
   
-  double size;
+  int simplex_size_valid;
+  double simplex_size;
 
   void *state;
 }
@@ -135,7 +135,7 @@
 gsl_multimin_fminimizer_minimum (const gsl_multimin_fminimizer * s);
 
 double
-gsl_multimin_fminimizer_size (const gsl_multimin_fminimizer * s);
+gsl_multimin_fminimizer_size (gsl_multimin_fminimizer * s);
 
 /* Convergence test functions */
 
Only in gsl-1.8/multimin: gsl_multimin.h~
diff -u orig/gsl-1.8/multimin/simplex.c gsl-1.8/multimin/simplex.c
--- orig/gsl-1.8/multimin/simplex.c	2005-06-26 14:25:35.000000000 +0100
+++ gsl-1.8/multimin/simplex.c	2008-09-29 02:01:18.000000000 +0100
@@ -150,8 +150,10 @@
 }
 
 static double
-nmsimplex_size (nmsimplex_state_t * state)
+nmsimplex_get_size (void *vstate)
 {
+  nmsimplex_state_t *state = (nmsimplex_state_t *) vstate;
+
   /* calculates simplex size as average sum of length of vectors 
      from simplex center to corner points:     
 
@@ -218,7 +220,7 @@
 static int
 nmsimplex_set (void *vstate, gsl_multimin_function * f,
                const gsl_vector * x,
-               double *size, const gsl_vector * step_size)
+               const gsl_vector * step_size)
 {
   int status;
   size_t i;
@@ -252,10 +254,6 @@
       gsl_vector_set (state->y1, i + 1, val);
     }
 
-  /* Initialize simplex size */
-
-  *size = nmsimplex_size (state);
-
   return GSL_SUCCESS;
 }
 
@@ -272,7 +270,7 @@
 
 static int
 nmsimplex_iterate (void *vstate, gsl_multimin_function * f,
-                   gsl_vector * x, double *size, double *fval)
+                   gsl_vector * x, double *fval)
 {
 
   /* Simplex iteration tries to minimize function f value */
@@ -395,10 +393,6 @@
   gsl_matrix_get_row (x, x1, lo);
   *fval = gsl_vector_get (y1, lo);
 
-  /* Update simplex size */
-
-  *size = nmsimplex_size (state);
-
   return GSL_SUCCESS;
 }
 
@@ -408,7 +402,8 @@
   &nmsimplex_alloc,
   &nmsimplex_set,
   &nmsimplex_iterate,
-  &nmsimplex_free
+  &nmsimplex_free,
+  &nmsimplex_get_size
 };
 
 const gsl_multimin_fminimizer_type
Only in gsl-1.8/multimin: simplex.c~




Reply sent to Dirk Eddelbuettel <edd@debian.org>:
You have marked Bug as forwarded. (Tue, 30 Sep 2008 00:15:03 GMT) Full text and rfc822 format available.

Message #13 received at 500521-forwarded@bugs.debian.org (full text, mbox):

From: Dirk Eddelbuettel <edd@debian.org>
To: Brian Gough <bjg@network-theory.co.uk>
Cc: Ian Jackson <ijackson@chiark.greenend.org.uk>, 500521-forwarded@bugs.debian.org
Subject: Re: Bug#500521: fminimizer nmsimplex unnecessary size calculation
Date: Mon, 29 Sep 2008 19:13:28 -0500
Ian:    Ack, and thanks for the bug report. It is an upstream issue, so I am
	passing this on.  Did you by chance consider the current 1.11 sources?

Brian:  See the description below, as well as the follow-up patch at
	http://bugs.debian.org/500521 Comments, esp on the patch, would be
	appreciated. I guess this may come back to the oft-discussed issue of
	simplicity and clarity of interfaces and usage versus performance.

Cheers, Dirk


On 29 September 2008 at 02:21, Ian Jackson wrote:
| 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.
| 
| 

-- 
Three out of two people have difficulties with fractions.




Message #14 received at 500521-forwarded@bugs.debian.org (full text, mbox):

From: Brian Gough <bjg@gnu.org>
To: Dirk Eddelbuettel <edd@debian.org>
Cc: Ian Jackson <ijackson@chiark.greenend.org.uk>, 500521-forwarded@bugs.debian.org
Subject: Re: Bug#500521: fminimizer nmsimplex unnecessary size calculation
Date: Tue, 30 Sep 2008 21:15:26 +0100
At Mon, 29 Sep 2008 19:13:28 -0500,
Dirk Eddelbuettel wrote:
> 
> 
> Ian:    Ack, and thanks for the bug report. It is an upstream issue, so I am
> 	passing this on.  Did you by chance consider the current 1.11 sources?
> 
> Brian:  See the description below, as well as the follow-up patch at
> 	http://bugs.debian.org/500521 Comments, esp on the patch, would be
> 	appreciated. I guess this may come back to the oft-discussed issue of
> 	simplicity and clarity of interfaces and usage versus performance.
> 

Thanks for the bug report and patch, now logged at
https://savannah.gnu.org/bugs/?24418.

I confirm that this is still a problem with 1.11 -- I'll apply the
patch for the next release.

-- 
Brian Gough

GNU Scientific Library -
http://www.gnu.org/software/gsl/




Reply sent to Dirk Eddelbuettel <edd@debian.org>:
You have taken responsibility. (Wed, 29 Oct 2008 15:54:12 GMT) Full text and rfc822 format available.

Notification sent to Ian Jackson <ijackson@chiark.greenend.org.uk>:
Bug acknowledged by developer. (Wed, 29 Oct 2008 15:54:14 GMT) Full text and rfc822 format available.

Message #19 received at 500521-close@bugs.debian.org (full text, mbox):

From: Dirk Eddelbuettel <edd@debian.org>
To: 500521-close@bugs.debian.org
Subject: Bug#500521: fixed in gsl 1.11+dfsg-2
Date: Wed, 29 Oct 2008 15:32:04 +0000
Source: gsl
Source-Version: 1.11+dfsg-2

We believe that the bug you reported is fixed in the latest version of
gsl, which is due to be installed in the Debian FTP archive:

gsl-bin_1.11+dfsg-2_i386.deb
  to pool/main/g/gsl/gsl-bin_1.11+dfsg-2_i386.deb
gsl_1.11+dfsg-2.diff.gz
  to pool/main/g/gsl/gsl_1.11+dfsg-2.diff.gz
gsl_1.11+dfsg-2.dsc
  to pool/main/g/gsl/gsl_1.11+dfsg-2.dsc
libgsl0-dbg_1.11+dfsg-2_i386.deb
  to pool/main/g/gsl/libgsl0-dbg_1.11+dfsg-2_i386.deb
libgsl0-dev_1.11+dfsg-2_i386.deb
  to pool/main/g/gsl/libgsl0-dev_1.11+dfsg-2_i386.deb
libgsl0ldbl_1.11+dfsg-2_i386.deb
  to pool/main/g/gsl/libgsl0ldbl_1.11+dfsg-2_i386.deb



A summary of the changes between this version and the previous one is
attached.

Thank you for reporting the bug, which will now be closed.  If you
have further comments please address them to 500521@bugs.debian.org,
and the maintainer will reopen the bug report if appropriate.

Debian distribution maintenance software
pp.
Dirk Eddelbuettel <edd@debian.org> (supplier of updated gsl package)

(This message was generated automatically at their request; if you
believe that there is a problem with it please contact the archive
administrators by mailing ftpmaster@debian.org)


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Format: 1.8
Date: Wed, 29 Oct 2008 09:49:19 -0500
Source: gsl
Binary: libgsl0ldbl libgsl0-dev gsl-bin libgsl0-dbg libgsl0-prof
Architecture: source i386
Version: 1.11+dfsg-2
Distribution: unstable
Urgency: low
Maintainer: Dirk Eddelbuettel <edd@debian.org>
Changed-By: Dirk Eddelbuettel <edd@debian.org>
Description: 
 gsl-bin    - GNU Scientific Library (GSL) -- binary package
 libgsl0-dbg - GNU Scientific Library (GSL) -- debug symbols package
 libgsl0-dev - GNU Scientific Library (GSL) -- development package
 libgsl0-prof - GNU Scientific Library (GSL) -- Profiling Libraries
 libgsl0ldbl - GNU Scientific Library (GSL) -- library package
Closes: 500521 503290
Changes: 
 gsl (1.11+dfsg-2) unstable; urgency=low
 .
   * debian/*: Applied patch by Matthew Vernon for building an optional package
     libgsl0-prof from source by setting setting DEB_BUILD_OPTIONS=buildprof
     Many thanks for suggesting the patch, and even providing it!
   							(Closes: #503290)
 .
   * multimin/*: Applied patch by Ian Jackson to skip unncessary size
     calculations; patch also intgegrated upstream	(Closes: #500521)
Checksums-Sha1: 
 7734972e201ce717e5578d78ed907c41fa766edd 1118 gsl_1.11+dfsg-2.dsc
 4bac02b9f7297118236116490e5d074fd4c41c13 17162 gsl_1.11+dfsg-2.diff.gz
 20e34aed2466906e0d780e01afeeec0b5f3a2e32 870302 libgsl0ldbl_1.11+dfsg-2_i386.deb
 0ee90bba764ec13cbc19b49882f8f6a66ba9a049 1119036 libgsl0-dev_1.11+dfsg-2_i386.deb
 6d7677f16e41e8e95ae7c6e9efe41e9e35ad8503 28292 gsl-bin_1.11+dfsg-2_i386.deb
 b5f3ef273c35ea112cadbb437a3dea819800e6cb 1336876 libgsl0-dbg_1.11+dfsg-2_i386.deb
Checksums-Sha256: 
 0347318388ab65df3c5e68584229d98483006a6f4173fb0b22c19973daa06bcc 1118 gsl_1.11+dfsg-2.dsc
 5014304320501588f3ed3f0a6c29e930687884af136b4a0d991d985dd1df0afc 17162 gsl_1.11+dfsg-2.diff.gz
 c095f8353342f2999d4e5b22718a0f535430d1f5e62564e39e6dbde56cc18733 870302 libgsl0ldbl_1.11+dfsg-2_i386.deb
 1bb51b4de3feee42ea0d285282c4ee58569cb2c93c96b44a2531d731cb669a70 1119036 libgsl0-dev_1.11+dfsg-2_i386.deb
 4d8cf634c18c5fc380b48441ffce654176c25d0f3e951ae38971e77b713744f0 28292 gsl-bin_1.11+dfsg-2_i386.deb
 6b5cab488626c1971a19cdf58b378f5f559d933ac6f3d9fbe2df1eea5410a4a3 1336876 libgsl0-dbg_1.11+dfsg-2_i386.deb
Files: 
 91467f5f01a2b980e3e125718294edce 1118 math optional gsl_1.11+dfsg-2.dsc
 a2176f3314fc5646cdf4c9d41b469770 17162 math optional gsl_1.11+dfsg-2.diff.gz
 6ef217792618303954f45a74ce88e4dd 870302 math optional libgsl0ldbl_1.11+dfsg-2_i386.deb
 83e99b380bab2cd844fe7681b56cf571 1119036 libdevel optional libgsl0-dev_1.11+dfsg-2_i386.deb
 115ef833c1def15060f849fd39062fca 28292 math optional gsl-bin_1.11+dfsg-2_i386.deb
 c934a6cf2df0e2f03e253eebb15d9d44 1336876 libdevel extra libgsl0-dbg_1.11+dfsg-2_i386.deb

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iD8DBQFJCH7ZCZSR95Gw07cRAo0fAJ9VMKkOIFRLrVumDjTE7qtUcrLZ1ACfVisa
zZ12H4wz55UTu91zkDzc2Rs=
=tkU4
-----END PGP SIGNATURE-----





Message #20 received at 500521-forwarded@bugs.debian.org (full text, mbox):

From: Brian Gough <bjg@gnu.org>
To: Dirk Eddelbuettel <edd@debian.org>
Cc: Ian Jackson <ijackson@chiark.greenend.org.uk>, 500521-forwarded@bugs.debian.org, bug-gsl@gnu.org
Subject: Re: Bug#500521: fminimizer nmsimplex unnecessary size calculation
Date: Sat, 29 Nov 2008 21:40:38 +0000
At Mon, 29 Sep 2008 19:13:28 -0500,
Dirk Eddelbuettel wrote:
> 
> 
> Ian:    Ack, and thanks for the bug report. It is an upstream issue, so I am
> 	passing this on.  Did you by chance consider the current 1.11 sources?
> 
> Brian:  See the description below, as well as the follow-up patch at
> 	http://bugs.debian.org/500521 Comments, esp on the patch, would be
> 	appreciated. I guess this may come back to the oft-discussed issue of
> 	simplicity and clarity of interfaces and usage versus performance.
> 

Just to let you know, there is now an O(N) implementation of the
simplex algorithm in GSL, which should solve the performance problems
of the O(N^2) version.

http://git.savannah.gnu.org/gitweb/?p=gsl.git;a=commit;h=b8e9d15cc5000b495a36f569b413b1866577fe7b

-- 
Brian Gough




Bug archived. Request was from Debbugs Internal Request <owner@bugs.debian.org> to internal_control@bugs.debian.org. (Mon, 16 Mar 2009 08:08:51 GMT) Full text and rfc822 format available.

Send a report that this bug log contains spam.


Debian bug tracking system administrator <owner@bugs.debian.org>. Last modified: Thu Apr 17 01:12:26 2014; Machine Name: buxtehude.debian.org

Debian Bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.