This is the mail archive of the
gsl-discuss@sources.redhat.com
mailing list for the GSL project.
Re: Help: working with large gsl_vector
- From: Fabrice Rossi <Fabrice dot Rossi at apiacoa dot org>
- To: gsl-discuss at sources dot redhat dot com
- Cc: Toan T Nguyen <ntt at physics dot ucla dot edu>
- Date: Mon, 13 Dec 2004 19:50:46 +0100
- Subject: Re: Help: working with large gsl_vector
- References: <200412102351.20027.ntt@physics.ucla.edu>
Toan T Nguyen wrote:
I'm using the multidimensional minimization procedure in GSL and have problem
with large vectors. The dimensionality of my vectors is 300000 which means my
index variable is of long integer type.
Hum. I authored the initial version of the multidimensional minimization
functions which have been improved by others, but I don't think they
have been improved in such a way that optimization in dimension 300 000
is possible. Even for a quadratic function and using a conjugate
gradient algorithm, it will take 3e5 iterations to the algorithm to
complete. As each iteration implies a linear search for minimum that
will use at least around 10 evaluations of your function, your a looking
for 3e6 function evaluation. Unless you have a very special problem, I
would guess that a function evaluation take at least 3e5 operations to
complete, which implies 9e11 operations (a.k.a. 2^39 operations). That's
a lot. And we are talking about a quadratic form, remember ?
Perhaps you could tell us a little bit more about your application ?
Fabrice
PS : Support Vector Machine algorithms have proven that it is indeed
possible to do quadratic optimization under constraints in high
dimensional space (like 10000 dimensions), but they use _very_ complex
methods.