[Math] DS: An alternative to DerivativeStructure

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

[Math] DS: An alternative to DerivativeStructure

Ajo Fod
Hello,

Ran into problems with DerivativeStructure today. It requires a lot of memory with 6000 or so independent variables. I poked around and found it the problem starts with the number of DSCompiler objects instantiated.

Given this and my earlier observation that in sparse derivative trees, the existing structure allocates space for all independent variables and hence is computationally inefficient, I designed a faster/leaner(less memory) structure.

One shortcomming of DS is that it computes only up to the first derivative. This may not be a problem in many cases such as the minimization of a multivariate function where optimization can be much quicker with a gradient. Going as far as the hessian may be fundamentally too memory or time intensive. So, it is useful to have an easier method to computing just the first derivative.

The design of DS is that all DS instances created either as a results of calling:
DS.getConst(value);  // for constants
DS.getVariable(idx, value); // for independent variables
... OR as a rest of some computation.

I felt it appropriate to add an addInPlace and multInPlace for aggregation processes so that objects are not copied over too often.

Attached is the code.

Cheers,
Ajo


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: [Math] DS: An alternative to DerivativeStructure

Luc Maisonobe-2
Le 2013-09-19 08:26, Ajo Fod a écrit :
> Hello,

Hi Ajo,

>
> Ran into problems with DerivativeStructure today. It requires a lot of
> memory with 6000 or so independent variables. I poked around and found
> it the problem starts with the number of DSCompiler objects
> instantiated.

Yes, this is a know side effect of the ability to handle both several
variables
and several derivative orders. It is even worse when you combine medium
numbers
but along both axes (say 20 derivatives and 20 variables, I guess it is
almost
impossible to fir in memory of regular desktop computers).

>
> Given this and my earlier observation that in sparse derivative trees,
> the existing structure allocates space for all independent variables
> and hence is computationally inefficient, I designed a
> faster/leaner(less memory) structure.
>
> One shortcomming of DS is that it computes only up to the first
> derivative. This may not be a problem in many cases such as the
> minimization of a multivariate function where optimization can be much
> quicker with a gradient. Going as far as the hessian may be
> fundamentally too memory or time intensive. So, it is useful to have
> an easier method to computing just the first derivative.

This sound interesting, I hope it could be added as a more specialized
alternative. The name should probably be adapted to reflect it is
designed
for order 1 and many variables (perhaps DerivativeStructure1N or
something
like that).

>
> The design of DS is that all DS instances created either as a results
> of calling:
>
> DS.getConst(value);  // for constants
>
> DS.getVariable(idx, value); // for independent variables
>
> ... OR as a rest of some computation.
>
> I felt it appropriate to add an addInPlace and multInPlace for
> aggregation processes so that objects are not copied over too often.

If you handle a really large number of variables at the same time, it
makes sense (same discussion as why general matrices and vectors are
often
not immutable).

>
> Attached is the code.

Attachments are automatically stripped from messages sent to the list.
Small
code snippets can be written directly in the mail, but larger
contributions can
only be attached to JIRA issues (but still discussion occurs on the
list, yes,
its cumbersome, we are sorry for that).

Thank you very much for you interest in this field of differentiation.

best regards,
Luc

>
> Cheers,
> Ajo
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] DS: An alternative to DerivativeStructure

Ajo Fod
Created: https://issues.apache.org/jira/browse/MATH-1036#comment-13771933



On Thu, Sep 19, 2013 at 12:29 AM, luc <[hidden email]> wrote:

> Le 2013-09-19 08:26, Ajo Fod a écrit :
>
>> Hello,
>>
>
> Hi Ajo,
>
>
>
>> Ran into problems with DerivativeStructure today. It requires a lot of
>> memory with 6000 or so independent variables. I poked around and found
>> it the problem starts with the number of DSCompiler objects
>> instantiated.
>>
>
> Yes, this is a know side effect of the ability to handle both several
> variables
> and several derivative orders. It is even worse when you combine medium
> numbers
> but along both axes (say 20 derivatives and 20 variables, I guess it is
> almost
> impossible to fir in memory of regular desktop computers).
>
>
>
>> Given this and my earlier observation that in sparse derivative trees,
>> the existing structure allocates space for all independent variables
>> and hence is computationally inefficient, I designed a
>> faster/leaner(less memory) structure.
>>
>> One shortcomming of DS is that it computes only up to the first
>> derivative. This may not be a problem in many cases such as the
>> minimization of a multivariate function where optimization can be much
>> quicker with a gradient. Going as far as the hessian may be
>> fundamentally too memory or time intensive. So, it is useful to have
>> an easier method to computing just the first derivative.
>>
>
> This sound interesting, I hope it could be added as a more specialized
> alternative. The name should probably be adapted to reflect it is designed
> for order 1 and many variables (perhaps DerivativeStructure1N or something
> like that).
>
>
>
>> The design of DS is that all DS instances created either as a results
>> of calling:
>>
>> DS.getConst(value);  // for constants
>>
>> DS.getVariable(idx, value); // for independent variables
>>
>> ... OR as a rest of some computation.
>>
>> I felt it appropriate to add an addInPlace and multInPlace for
>> aggregation processes so that objects are not copied over too often.
>>
>
> If you handle a really large number of variables at the same time, it
> makes sense (same discussion as why general matrices and vectors are often
> not immutable).
>
>
>> Attached is the code.
>>
>
> Attachments are automatically stripped from messages sent to the list.
> Small
> code snippets can be written directly in the mail, but larger
> contributions can
> only be attached to JIRA issues (but still discussion occurs on the list,
> yes,
> its cumbersome, we are sorry for that).
>
> Thank you very much for you interest in this field of differentiation.
>
> best regards,
> Luc
>
>
>> Cheers,
>> Ajo
>>
>>
>> ------------------------------**------------------------------**---------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<[hidden email]>
>> For additional commands, e-mail: [hidden email]
>>
>
> ------------------------------**------------------------------**---------
> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<[hidden email]>
> For additional commands, e-mail: [hidden email]
>
>
Reply | Threaded
Open this post in threaded view
|

Re: [Math] DS: An alternative to DerivativeStructure

Luc Maisonobe
Hi Ajo,

Le 19/09/2013 16:26, Ajo Fod a écrit :
> Created: https://issues.apache.org/jira/browse/MATH-1036#comment-13771933

This looks promising. Would it be possible to have this class implement
RealFieldElement<GradStructure> and to have some unit tests?

best regards,
Luc

>
>
>
> On Thu, Sep 19, 2013 at 12:29 AM, luc <[hidden email]> wrote:
>
>> Le 2013-09-19 08:26, Ajo Fod a écrit :
>>
>>> Hello,
>>>
>>
>> Hi Ajo,
>>
>>
>>
>>> Ran into problems with DerivativeStructure today. It requires a lot of
>>> memory with 6000 or so independent variables. I poked around and found
>>> it the problem starts with the number of DSCompiler objects
>>> instantiated.
>>>
>>
>> Yes, this is a know side effect of the ability to handle both several
>> variables
>> and several derivative orders. It is even worse when you combine medium
>> numbers
>> but along both axes (say 20 derivatives and 20 variables, I guess it is
>> almost
>> impossible to fir in memory of regular desktop computers).
>>
>>
>>
>>> Given this and my earlier observation that in sparse derivative trees,
>>> the existing structure allocates space for all independent variables
>>> and hence is computationally inefficient, I designed a
>>> faster/leaner(less memory) structure.
>>>
>>> One shortcomming of DS is that it computes only up to the first
>>> derivative. This may not be a problem in many cases such as the
>>> minimization of a multivariate function where optimization can be much
>>> quicker with a gradient. Going as far as the hessian may be
>>> fundamentally too memory or time intensive. So, it is useful to have
>>> an easier method to computing just the first derivative.
>>>
>>
>> This sound interesting, I hope it could be added as a more specialized
>> alternative. The name should probably be adapted to reflect it is designed
>> for order 1 and many variables (perhaps DerivativeStructure1N or something
>> like that).
>>
>>
>>
>>> The design of DS is that all DS instances created either as a results
>>> of calling:
>>>
>>> DS.getConst(value);  // for constants
>>>
>>> DS.getVariable(idx, value); // for independent variables
>>>
>>> ... OR as a rest of some computation.
>>>
>>> I felt it appropriate to add an addInPlace and multInPlace for
>>> aggregation processes so that objects are not copied over too often.
>>>
>>
>> If you handle a really large number of variables at the same time, it
>> makes sense (same discussion as why general matrices and vectors are often
>> not immutable).
>>
>>
>>> Attached is the code.
>>>
>>
>> Attachments are automatically stripped from messages sent to the list.
>> Small
>> code snippets can be written directly in the mail, but larger
>> contributions can
>> only be attached to JIRA issues (but still discussion occurs on the list,
>> yes,
>> its cumbersome, we are sorry for that).
>>
>> Thank you very much for you interest in this field of differentiation.
>>
>> best regards,
>> Luc
>>
>>
>>> Cheers,
>>> Ajo
>>>
>>>
>>> ------------------------------**------------------------------**---------
>>> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<[hidden email]>
>>> For additional commands, e-mail: [hidden email]
>>>
>>
>> ------------------------------**------------------------------**---------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<[hidden email]>
>> For additional commands, e-mail: [hidden email]
>>
>>
>


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] DS: An alternative to DerivativeStructure

Ajo Fod
Hi Luc,

I'll work on tests when I get a chance.

RealFieldElement has a lot of functions so its a bit out of my way.

Cheers,
-Ajo



On Thu, Sep 19, 2013 at 10:58 AM, Luc Maisonobe <[hidden email]>wrote:

> Hi Ajo,
>
> Le 19/09/2013 16:26, Ajo Fod a écrit :
> > Created:
> https://issues.apache.org/jira/browse/MATH-1036#comment-13771933
>
> This looks promising. Would it be possible to have this class implement
> RealFieldElement<GradStructure> and to have some unit tests?
>
> best regards,
> Luc
>
> >
> >
> >
> > On Thu, Sep 19, 2013 at 12:29 AM, luc <[hidden email]> wrote:
> >
> >> Le 2013-09-19 08:26, Ajo Fod a écrit :
> >>
> >>> Hello,
> >>>
> >>
> >> Hi Ajo,
> >>
> >>
> >>
> >>> Ran into problems with DerivativeStructure today. It requires a lot of
> >>> memory with 6000 or so independent variables. I poked around and found
> >>> it the problem starts with the number of DSCompiler objects
> >>> instantiated.
> >>>
> >>
> >> Yes, this is a know side effect of the ability to handle both several
> >> variables
> >> and several derivative orders. It is even worse when you combine medium
> >> numbers
> >> but along both axes (say 20 derivatives and 20 variables, I guess it is
> >> almost
> >> impossible to fir in memory of regular desktop computers).
> >>
> >>
> >>
> >>> Given this and my earlier observation that in sparse derivative trees,
> >>> the existing structure allocates space for all independent variables
> >>> and hence is computationally inefficient, I designed a
> >>> faster/leaner(less memory) structure.
> >>>
> >>> One shortcomming of DS is that it computes only up to the first
> >>> derivative. This may not be a problem in many cases such as the
> >>> minimization of a multivariate function where optimization can be much
> >>> quicker with a gradient. Going as far as the hessian may be
> >>> fundamentally too memory or time intensive. So, it is useful to have
> >>> an easier method to computing just the first derivative.
> >>>
> >>
> >> This sound interesting, I hope it could be added as a more specialized
> >> alternative. The name should probably be adapted to reflect it is
> designed
> >> for order 1 and many variables (perhaps DerivativeStructure1N or
> something
> >> like that).
> >>
> >>
> >>
> >>> The design of DS is that all DS instances created either as a results
> >>> of calling:
> >>>
> >>> DS.getConst(value);  // for constants
> >>>
> >>> DS.getVariable(idx, value); // for independent variables
> >>>
> >>> ... OR as a rest of some computation.
> >>>
> >>> I felt it appropriate to add an addInPlace and multInPlace for
> >>> aggregation processes so that objects are not copied over too often.
> >>>
> >>
> >> If you handle a really large number of variables at the same time, it
> >> makes sense (same discussion as why general matrices and vectors are
> often
> >> not immutable).
> >>
> >>
> >>> Attached is the code.
> >>>
> >>
> >> Attachments are automatically stripped from messages sent to the list.
> >> Small
> >> code snippets can be written directly in the mail, but larger
> >> contributions can
> >> only be attached to JIRA issues (but still discussion occurs on the
> list,
> >> yes,
> >> its cumbersome, we are sorry for that).
> >>
> >> Thank you very much for you interest in this field of differentiation.
> >>
> >> best regards,
> >> Luc
> >>
> >>
> >>> Cheers,
> >>> Ajo
> >>>
> >>>
> >>>
> ------------------------------**------------------------------**---------
> >>> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<
> [hidden email]>
> >>> For additional commands, e-mail: [hidden email]
> >>>
> >>
> >>
> ------------------------------**------------------------------**---------
> >> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<
> [hidden email]>
> >> For additional commands, e-mail: [hidden email]
> >>
> >>
> >
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]
>
>