Algorithmic Differentiation, Using a C++ library

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Algorithmic Differentiation, Using a C++ library

Brad Bell
Sorry for the delay since my previous message
http://lists.gnu.org/archive/html/octave-maintainers/2017-02/msg00029.html
I was busy adding sparse calculations to Cppad Swig; see
     http://www.seanet.com/~bradbell/cppad_swig/sparse.htm

How about not using Swig, but just the C++ library that Cppad Swig creates ?
See the corresponding example
  http://www.seanet.com/~bradbell/cppad_swig/a_fun_jacobian_xam.cpp.htm

The tests (for the library without Swig) correspond to the command
     make check_lib_cplusplus
See
     http://www.seanet.com/~bradbell/cppad_swig/testing.htm

P.S.
There are some problems using Octave 4.2 with older versions of Swig;
see the heading Octave on the web page above.



Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Algorithmic Differentiation, Using a C++ library

Olaf Till-2
On Tue, Feb 28, 2017 at 07:44:49AM -0700, Brad Bell wrote:

> Sorry for the delay since my previous message
> http://lists.gnu.org/archive/html/octave-maintainers/2017-02/msg00029.html
> I was busy adding sparse calculations to Cppad Swig; see
>     http://www.seanet.com/~bradbell/cppad_swig/sparse.htm
>
> How about not using Swig, but just the C++ library that Cppad Swig creates ?
> See the corresponding example
>  http://www.seanet.com/~bradbell/cppad_swig/a_fun_jacobian_xam.cpp.htm
>
> The tests (for the library without Swig) correspond to the command
>     make check_lib_cplusplus
> See
>     http://www.seanet.com/~bradbell/cppad_swig/testing.htm
I had thought to use just cppad, but will have a look at the C++
library.

There was much delay from my side due to unforeseen involvement with
Octave Forge administration. But I'll come back to this.

Olaf

--
public key id EAFE0591, e.g. on x-hkp://pool.sks-keyservers.net

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Algorithmic Differentiation, Using a C++ library

Brad Bell
Another thing to consider, instead of the library, is using CppAD +
Eigen. That would make it easy to implement matrix operations. For
example, see
     https://www.coin-or.org/CppAD/Doc/eigen_array.cpp.htm

On 02/28/2017 10:34 AM, Olaf Till wrote:

> On Tue, Feb 28, 2017 at 07:44:49AM -0700, Brad Bell wrote:
>> Sorry for the delay since my previous message
>> http://lists.gnu.org/archive/html/octave-maintainers/2017-02/msg00029.html
>> I was busy adding sparse calculations to Cppad Swig; see
>>      http://www.seanet.com/~bradbell/cppad_swig/sparse.htm
>>
>> How about not using Swig, but just the C++ library that Cppad Swig creates ?
>> See the corresponding example
>>   http://www.seanet.com/~bradbell/cppad_swig/a_fun_jacobian_xam.cpp.htm
>>
>> The tests (for the library without Swig) correspond to the command
>>      make check_lib_cplusplus
>> See
>>      http://www.seanet.com/~bradbell/cppad_swig/testing.htm
> I had thought to use just cppad, but will have a look at the C++
> library.
>
> There was much delay from my side due to unforeseen involvement with
> Octave Forge administration. But I'll come back to this.
>
> Olaf
>


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Algorithmic Differentiation (Using a C++ library)

Oliver Heimlich
On 01.03.2017 15:38, Brad Bell wrote:
> Another thing to consider, instead of the library, is using CppAD +
> Eigen. That would make it easy to implement matrix operations. For
> example, see
>     https://www.coin-or.org/CppAD/Doc/eigen_array.cpp.htm

Slightly off topic: There once was an Octave package for AD [1], which
is now unmaintained. I believe the reason is that it was mainly build in
CPP code, which is no longer compatible with the current Octave API.
Most of the code is used to introduce a new data type into Octave, with
overloaded operations.

Now that we have classes in Octave, it would be possible to revive this
package using a classdef data type, overloaded operators and vectorized
m-file code. (Possible GSoC project?!?)

The unmaintained package contains documentation and many test cases,
which could easily be taken over.

If everything goes well, we would have:
- fast code that uses Octave's matrix operations
- easier to maintain m-file code
- the possibility to use other data types in AD

Regarding the last point: I think of combining AD with the interval data
type. This way it would become possible to compute guaranteed enclosures
for the Jacobian, and you don't have to rely on “NearEqual” checks with
approximate values in your script.

Oliver

[1] https://octave.sourceforge.io/ad/

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Algorithmic Differentiation (Using a C++ library)

Oliver Heimlich
(I hope you don't mind that I cc to the mailing list)

On 01.03.2017 21:07, Brad Bell wrote:

> On 03/01/2017 12:12 PM, Oliver Heimlich wrote:
>> On 01.03.2017 15:38, Brad Bell wrote:
>>> Another thing to consider, instead of the library, is using CppAD +
>>> Eigen. That would make it easy to implement matrix operations. For
>>> example, see
>>>      https://www.coin-or.org/CppAD/Doc/eigen_array.cpp.htm
>> Slightly off topic: There once was an Octave package for AD [1], which
>> is now unmaintained. I believe the reason is that it was mainly build in
>> CPP code, which is no longer compatible with the current Octave API.
>> Most of the code is used to introduce a new data type into Octave, with
>> overloaded operations.
>>
>> Now that we have classes in Octave, it would be possible to revive this
>> package using a classdef data type, overloaded operators and vectorized
>> m-file code. (Possible GSoC project?!?
> I have taken a brief look at the package source code. It appears to just
> implement first order foward mode. Is this correct ?

Yes, this is also my impression.

> There is a lot to and AD package (e.g, Cppad and Adolc) that can compute
> arbitrary order derivatives using forward or reverse mode and  combine
> multiple rows or columns when computing sparse Jacobians and Hessians .
> While this, and other features of a complete AD package can be
> reproduced, I think it would be simpler to take advantage of an existing
> package.

First order forward mode is quite simple to implement. I am not an
expert in AD and wasn't aware of the advanced functionality that you
want to use.

> Yes I agree that, hooking up and AD package to Octave would make a good
> GSoC project.


>> The unmaintained package contains documentation and many test cases,
>> which could easily be taken over.
> As for a source of AD test cases, one could look here
>     https://www.coin-or.org/CppAD/Doc/listallexamples.htm
> For more tests, that are not also examples, see
>     https://github.com/coin-or/CppAD/tree/master/test_more

Test cases of the Octave package can be found in [2]

>> If everything goes well, we would have:
>> - fast code that uses Octave's matrix operations
>> - easier to maintain m-file code
>> - the possibility to use other data types in AD

> It might also help to look at the MATLAB packages that do AD; see
>     http://www.autodiff.org/?module=Tools&language=MATLAB

As far as I see, these packages are either proprietary software or use
the source transformation method (instead of operator overloading).

>> Regarding the last point: I think of combining AD with the interval data
>> type. This way it would become possible to compute guaranteed enclosures
>> for the Jacobian, and you don't have to rely on “NearEqual” checks with
>> approximate values in your script.
> Cppad allows for an arbitrary Base type that the derivatives a
> calculated with. It can be an interval type.

I am not sure, if (and how easy) it is possibly to combine a
templated(?) C++ library with types that are implemented in Octave as
classes.

Oliver

>> [1] https://octave.sourceforge.io/ad/
[2]
https://sourceforge.net/p/octave/automatic_differentiation/ci/default/tree/inst/__ga__.m

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Algorithmic Differentiation (Using a C++ library)

Brad Bell
On 03/01/2017 01:57 PM, Oliver Heimlich wrote:
... snip ...
> I am not sure, if (and how easy) it is possibly to combine a
> templated(?) C++ library with types that are implemented in Octave as
> classes.
The Cppad Swig C++ library is an example of specializing a template
library to a particular type and then hooking that specialization up to
a scripting language.

... snip ...

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Algorithmic Differentiation (Using a C++ library)

Olaf Till-2
On Wed, Mar 01, 2017 at 02:06:29PM -0700, Brad Bell wrote:
> On 03/01/2017 01:57 PM, Oliver Heimlich wrote:
> ... snip ...
> >I am not sure, if (and how easy) it is possibly to combine a
> >templated(?) C++ library with types that are implemented in Octave as
> >classes.
> The Cppad Swig C++ library is an example of specializing a template library
> to a particular type and then hooking that specialization up to a scripting
> language.

Swig makes an interface from Octave to C++. What Oliver would need is
the opposite direction. This wouldn't work...

I agree that passing an interval type, implemented with Octave
classes, to an AD type would only be possible if AD is also
implemented with Octave classes. This would need AD to be implemented
first, and to make a specialization then which internally generates an
interval type from the arguments (making it dependent on the interval
package). But:

1. 'interval' must support vectors for this.

2. For AD itself to be useful, we need it to be thoroughly
   implemented, including Hessians, at least.

Olaf

--
public key id EAFE0591, e.g. on x-hkp://pool.sks-keyservers.net

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Algorithmic Differentiation (Using a C++ library)

Urathai

Olaf Till writes:

> On Wed, Mar 01, 2017 at 02:06:29PM -0700, Brad Bell wrote:
>> On 03/01/2017 01:57 PM, Oliver Heimlich wrote:
>> ... snip ...
>> >I am not sure, if (and how easy) it is possibly to combine a
>> >templated(?) C++ library with types that are implemented in Octave as
>> >classes.
>> The Cppad Swig C++ library is an example of specializing a template library
>> to a particular type and then hooking that specialization up to a scripting
>> language.
>
> Swig makes an interface from Octave to C++. What Oliver would need is
> the opposite direction. This wouldn't work...
>
> I agree that passing an interval type, implemented with Octave
> classes, to an AD type would only be possible if AD is also
> implemented with Octave classes. This would need AD to be implemented
> first, and to make a specialization then which internally generates an
> interval type from the arguments (making it dependent on the interval
> package). But:
>
> 1. 'interval' must support vectors for this.
>
> 2. For AD itself to be useful, we need it to be thoroughly
>    implemented, including Hessians, at least.
>
> Olaf

Hi,

One way to implement automatic differentiation would be to do it with
Taylor arithmetic. For single variable functions this would allow for
computing arbitrarily order derivatives in an effective way. It can also
be generalized to multi-variable functions but I am not sure how much
work this is (though two variables should be no problem). This also fits
nicely with Olivers idea of integrating it with the interval
package. Taylor expansions are very suitable for evaluation with
integrals, one example of this can be found in [1]. Adding that
functionality to Octave would allow for very powerful interval methods.

I have created a proof-of-concept implementation of Taylor arithmetic
which is available at GitHub, [2]. So far it implements a constructor
and some basic operations, +, -, .*, ./, exp, log, .^, sin and cos. As
of yet there is no functions to actually make use of the result. It is
meant to work with the interval package and should then generate
guaranteed results.

I would be very interested in continuing this work as a
GSoC-student. Especially I am interested it developing it alongside the
interval package, it is in this environment I have used Taylor
arithmetic it before.

Regards,
Joel Dahne

[1] http://www2.math.uni-wuppertal.de/~xsc/preprints/prep_05_4.pdf
[2] https://github.com/Urathai/octave-taylor-POC

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Algorithmic Differentiation (Using a C++ library)

Brad Bell
What is the advantage of re-programming Taylor arithmetic in Octave as
apposed to using
     CppAD::AD< IntervalType >
where IntervalType is a C++ interval type ?

On 03/08/2017 01:27 PM, Joel Dahne wrote:
... snip ...

> Hi,
>
> One way to implement automatic differentiation would be to do it with
> Taylor arithmetic. For single variable functions this would allow for
> computing arbitrarily order derivatives in an effective way. It can also
> be generalized to multi-variable functions but I am not sure how much
> work this is (though two variables should be no problem). This also fits
> nicely with Olivers idea of integrating it with the interval
> package. Taylor expansions are very suitable for evaluation with
> integrals, one example of this can be found in [1]. Adding that
> functionality to Octave would allow for very powerful interval methods.
>
> I have created a proof-of-concept implementation of Taylor arithmetic
> which is available at GitHub, [2]. So far it implements a constructor
> and some basic operations, +, -, .*, ./, exp, log, .^, sin and cos. As
> of yet there is no functions to actually make use of the result. It is
> meant to work with the interval package and should then generate
> guaranteed results.
>
> I would be very interested in continuing this work as a
> GSoC-student. Especially I am interested it developing it alongside the
> interval package, it is in this environment I have used Taylor
> arithmetic it before.
>
> Regards,
> Joel Dahne
>
> [1] http://www2.math.uni-wuppertal.de/~xsc/preprints/prep_05_4.pdf
> [2] https://github.com/Urathai/octave-taylor-POC
>


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Algorithmic Differentiation (Using a C++ library)

Urathai

Brad Bell writes:

> What is the advantage of re-programming Taylor arithmetic in Octave as
> apposed to using
>      CppAD::AD< IntervalType >
> where IntervalType is a C++ interval type ?
>
> On 03/08/2017 01:27 PM, Joel Dahne wrote:
> ... snip ...
>> Hi,
>>
>> One way to implement automatic differentiation would be to do it with
>> Taylor arithmetic. For single variable functions this would allow for
>> computing arbitrarily order derivatives in an effective way. It can also
>> be generalized to multi-variable functions but I am not sure how much
>> work this is (though two variables should be no problem). This also fits
>> nicely with Olivers idea of integrating it with the interval
>> package. Taylor expansions are very suitable for evaluation with
>> integrals, one example of this can be found in [1]. Adding that
>> functionality to Octave would allow for very powerful interval methods.
>>
>> I have created a proof-of-concept implementation of Taylor arithmetic
>> which is available at GitHub, [2]. So far it implements a constructor
>> and some basic operations, +, -, .*, ./, exp, log, .^, sin and cos. As
>> of yet there is no functions to actually make use of the result. It is
>> meant to work with the interval package and should then generate
>> guaranteed results.
>>
>> I would be very interested in continuing this work as a
>> GSoC-student. Especially I am interested it developing it alongside the
>> interval package, it is in this environment I have used Taylor
>> arithmetic it before.
>>
>> Regards,
>> Joel Dahne
>>
>> [1] http://www2.math.uni-wuppertal.de/~xsc/preprints/prep_05_4.pdf
>> [2] https://github.com/Urathai/octave-taylor-POC
>>

That might be another possibility, I am not familiar enough with CppAD
to know how well it would work. I do think however that it might be hard
to get proper support for Octaves interval-type, especially the
decorated intervals.

Regards,
Joel Dahne

Loading...