From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 24188 invoked by alias); 13 Dec 2004 18:51:00 -0000 Mailing-List: contact gsl-discuss-help@sources.redhat.com; run by ezmlm Precedence: bulk List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gsl-discuss-owner@sources.redhat.com Received: (qmail 24120 invoked from network); 13 Dec 2004 18:50:51 -0000 Received: from unknown (HELO home.apiacoa.org) (81.57.191.70) by sourceware.org with SMTP; 13 Dec 2004 18:50:51 -0000 Received: from localhost (localhost [127.0.0.1]) by home.apiacoa.org (Postfix) with ESMTP id DC6ED24BFF; Mon, 13 Dec 2004 19:50:50 +0100 (CET) Received: from home.apiacoa.org ([127.0.0.1]) by localhost (home.localdomain [127.0.0.1]) (amavisd-new, port 10024) with LMTP id 16173-02; Mon, 13 Dec 2004 19:50:50 +0100 (CET) Received: from [172.17.102.65] (unknown [150.161.2.204]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by home.apiacoa.org (Postfix) with ESMTP id 257B724BFE; Mon, 13 Dec 2004 19:50:49 +0100 (CET) Message-ID: <41BDE486.9090009@apiacoa.org> Date: Mon, 13 Dec 2004 18:51:00 -0000 From: Fabrice Rossi User-Agent: Mozilla Thunderbird 1.0 (X11/20041206) MIME-Version: 1.0 To: gsl-discuss@sources.redhat.com Cc: Toan T Nguyen Subject: Re: Help: working with large gsl_vector References: <200412102351.20027.ntt@physics.ucla.edu> In-Reply-To: <200412102351.20027.ntt@physics.ucla.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-SW-Source: 2004-q4/txt/msg00119.txt.bz2 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.