From: Toan T Nguyen <ntt@physics.ucla.edu>
To: Fabrice Rossi <Fabrice.Rossi@apiacoa.org>
Cc: gsl-discuss@sources.redhat.com, help-gsl@gnu.org
Subject: Re: Help: working with large gsl_vector
Date: Tue, 14 Dec 2004 23:03:00 -0000 [thread overview]
Message-ID: <200412141510.28746.ntt@physics.ucla.edu> (raw)
In-Reply-To: <41BDE486.9090009@apiacoa.org>
Hi, thank you for the analysis. Apparently, my analytical calculation is able
to guess the minimum reasonably good, so I need only 20000 iterations to find
the minimum.
However, the strange thing is if I take the final minimized vector and run it
through the conjugate gradient routine again, the energy (my function to
minimize) keeps going down for a few more 1000s iterations (albeit it change
only the 4th significant digit). Do you know what's wrong?
I follow the example in the GSL document and set my success criteria as
status = gsl_multimin_test_gradient (s->gradient, 1e-20);
The initial setup of the vector is
T = gsl_multimin_fdfminimizer_conjugate_pr;
s = gsl_multimin_fdfminimizer_alloc (T, 3*nparts);
gsl_multimin_fdfminimizer_set (s, &energy, x, 0.001, 1e-12);
For clarity, I used dimensionless units so ALL the nearest neighbor distances
and the coupling constants are of the order of unity. nparts is the number of
particles which is about 100000.
Could you give some advises? Thanks a lot in advance.
Toan
On Monday 13 December 2004 10:50, Fabrice Rossi wrote:
> 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.
next prev parent reply other threads:[~2004-12-14 23:03 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2004-12-11 7:44 Toan T Nguyen
2004-12-13 18:41 ` Linas Vepstas
2004-12-13 18:51 ` Fabrice Rossi
2004-12-14 23:03 ` Toan T Nguyen [this message]
2004-12-15 11:12 ` Fabrice Rossi
2004-12-15 12:11 ` Robert G. Brown
2004-12-15 17:31 ` Linas Vepstas
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=200412141510.28746.ntt@physics.ucla.edu \
--to=ntt@physics.ucla.edu \
--cc=Fabrice.Rossi@apiacoa.org \
--cc=gsl-discuss@sources.redhat.com \
--cc=help-gsl@gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).