Automatic Differentiation - Taylor Arithmetics

[Nisoli Isaia]

Dear all,

I was planning in doing a Cython implementation of Forward automatic differentiation and 

Taylor arithmetics  as in

https://press.princeton.edu/titles/9488.html

to use to implement a library for Sage with rigorous quadrature and integration of ODE.

I'm trying to understand which parent class could be the best for these objects for them 

to be compatible with Sage coercion model.

What is the usual procedure, I read through 

http://doc.sagemath.org/html/en/reference/structure/sage/structure/element.html

but I'm still confused.

Best wishes

Isaia

[Marc Mezzarobba]

Nisoli Isaia wrote:
> I was planning in doing a Cython implementation of Forward automatic
> differentiation and
> Taylor arithmetics as in
> https://press.princeton.edu/titles/9488.html
> to use to implement a library for Sage with rigorous quadrature and
> integration of ODE.

This is very interesting!

> I'm trying to understand which parent class could be the best for
> these objects for them
> to be compatible with Sage coercion model.

I think the most natural thing to do would be to implement new parents
similar to the rings of power series, but which would additionally track
bounds on the truncation errors. Some refactoring in the implementations
of polynomials and power series may be necessary to make it possible to
share code when that makes sense.

Note that in the case of a single variable, Sage already has very
efficient code for arithmetic on real and complex interval Taylor series
based on Arb. The available operations include composition of arbitrary
series as well as a number of specialized routines for composing with
elementary and special functions ("intrinsics" in Taylor model
parlance). See the methods *_trunc and _*_series of polynomials over RBF
and CBF. Arb provides a lot more functions of this kind that are not yet
exposed by Sage.

--
Marc

[Nisoli Isaia]

Dear Marc,

can you pinpoint me to how to have access to these?

I tried 

P.<x>=CBF[]

x._sin_series(4)

but for most of the _series method I get a NotImplemented error.

Where could I find the headers and the implementation files?

Best wishes

Isaia

 

--
Marc

[Marc Mezzarobba]

Nisoli Isaia wrote:
> P.<x>=CBF[]
> x._sin_series(4)

Indeed, I remembered wrong. Only a few of these arb functions are
accessible from sage at this point. It is trivial to add more, though.
The relevant files are

src/sage/libs/arb/acb_poly.pxd
src/sage/rings/polynomial/polynomial_complex_arb.pyx

Also, contrary to what I said, we only have an implementation based on
arb for the case of complex coefficients. Again, it wouldn't be hard
(but maybe a bit tedious) to implement real polynomials on the same
model.

Sorry for the incorrect information!

--
Marc

[Nisoli Isaia]

Thank you!

I think I could start by exposing these ARB functions to SAGE,

so that the interface is more complete, and then try to do the same

for Real Interval.

Best wishes

Isaia

[TB]

Do you know how this (forward automatic differentiation implementation)
will compare to autograd [1] or ForwardDiff.jl [2]? Can for example
autograd be used as some sort of a backend?

There is also the "tutorial implementation" autodidact [3] which seems
relevant.

Regards,
TB

[1] https://github.com/HIPS/autograd/
[2] https://github.com/JuliaDiff/ForwardDiff.jl
[3] https://github.com/mattjj/autodidact

> --
> You received this message because you are subscribed to the Google
> Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to sage-devel+...@googlegroups.com
> <mailto:sage-devel+...@googlegroups.com>.
> To post to this group, send email to sage-...@googlegroups.com
> <mailto:sage-...@googlegroups.com>.
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

[mmarco]

You might be interested in taking a look at tides [1]. It is a library for integration of ODE's in high precission using precisely automatic differentiation and Taylor arithmetic. It doesn't use interval arithemtic (so, no certified computation), but maybe some ideas could be useful.

The way it works is by translating the function that defines your ODE to c-code and then compiling it.

There is a tides optional package for sage, and an interface to it.

[1] https://iuma.unizar.es/es/investigacion/software/TIDES

[rjf]

You might be interested in this ..

https://people.eecs.berkeley.edu/~fateman/papers/ADIL.pdf

which is algorithm differentiation written in Lisp.

Sage includes Lisp (underneath Maxima, for example)

Manipulation of program source to produce other program source

is routinely supported in Lisp,  and there is a built-in compiler

to use when appropriate.  

I do not know about the particular difficulties one might face

in using Cython, which I have not used,  but in comparison to

some other code, the lisp included in that paper is about 10% of

the code size and considerably more extensive and extendable.

RJF

[Nisoli Isaia]

Dear Marc,

I've seen that you wrote a sage interface for sollya, which 

seems to take already take care of Taylor models.

Is Sollya already a part of Sage?

Are there any plans of Sollya entering sage?

Best wishes

Isaia

[Marc Mezzarobba]

Nisoli Isaia wrote:
> I've seen that you wrote a sage interface for sollya, which
> seems to take already take care of Taylor models.

Indeed, though the Taylor models in Sollya may be a bit limited, and (if
I understood right, but I'm really no expert here) have some performance
issues.

> Is Sollya already a part of Sage?
> Are there any plans of Sollya entering sage?

No. This doesn't prevent you from writing Python/Cython code that uses
both Sage and Sollya, of course, but I think such code would take quite
a bit of effort to include in Sage itself.

--
Marc

[mforets]

Hi all,

Yet another open source alternative: Taylor models are implemented in Julia (see TaylorModels.jl), and this library offers validated integration of ODEs (disclaimer: i also contribute to this and related projects that use other methods). Feel free to ask if you have questions about the algorithms available; an experimental evaluation on a set of benchmark cases is finished but not yet public, though i can send it personally.

I'm aware that there have been sustained efforts for better Python-Julia interaction (see e.g. pyjulia), but i have little experience with these so i can't tell you if it would be easy or hard to make TaylorModels.jl play nicely in a Sage environment.

Best,

Marcelo.-

[Francesco Biscani]

(Apologies for reviving this old thread, but since I saw a couple of mentions of ODE integration via Taylor's method in the mailing list archive, I thought that some people might be interested)

We just released the latest version of our Taylor integrator heyoka.py:

https://github.com/bluescarni/heyoka.py

heyoka.py is an implementation of Taylor's method for the numerical integration of systems of ODEs based on automatic differentiation and just-in-time compilation via LLVM.

Current features include:

- support for both double-precision and extended-precision floating-point types,
- the ability to maintain machine precision accuracy over tens of billions of timesteps,

- high-precision zero-cost dense output,
- fast and accurate event detection,

- excellent performance,

- batch mode integration to harness the power of modern SIMD instruction sets.

heyoka.py needs to represent the ODEs symbolically in order to apply the automatic differentiation rules necessary for an efficient implementation of Taylor's method. For this purpose, heyoka.py uses its own expression system, but in recent versions we added the ability to convert heyoka.py's symbolic expressions to/from SymPy. Here's a simple example of interoperability between heyoka.py and SymPy:

https://bluescarni.github.io/heyoka.py/notebooks/sympy_interop.html

It should not be difficult in principle to implement similar basic interoperability with Sage's expression system.

More tutorials and examples are available here:

https://bluescarni.github.io/heyoka.py/tutorials.html

https://bluescarni.github.io/heyoka.py/examples.html

Thanks and kind regards,

  Francesco.

--

You received this message because you are subscribed to the Google Groups "sage-devel" group.

To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
To post to this group, send email to sage-...@googlegroups.com.