Re: [sage-devel] Re: Automatic Differentiation - Taylor Arithmetics

[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.

On Mon, 29 Apr 2019 at 12:12, mmarco  wrote:

> 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
>
> El viernes, 19 de abril de 2019, 14:48:09 (UTC+2), Nisoli Isaia escribió:
>>
>> 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
>>
> --
> 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+unsubscr...@googlegroups.com.
> To post to this group, send email to sage-devel@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.
>

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/CAHExjCvSLtAbMW1KwhsF63ORvJXH55bTb2WkGWXp-OYV3%2BLyVQ%40mail.gmail.com.

[sage-devel] Re: Automatic Differentiation - Taylor Arithmetics

[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.-

El sábado, 18 de mayo de 2019, 6:18:45 (UTC-3), Marc Mezzarobba escribió:
>
> 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 
>
>

-- 
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+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/2f5f1c9b-6569-44bd-9dc3-0554c678c784%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Automatic Differentiation - Taylor Arithmetics

[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

-- 
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+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/qboil2%2458lt%241%40blaine.gmane.org.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Automatic Differentiation - Taylor Arithmetics

[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

On Saturday, April 20, 2019 at 5:36:46 AM UTC-3, Marc Mezzarobba wrote:
>
> 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 
>
>

-- 
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+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/d7b9286b-98d1-4288-8f12-4f41511879f8%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Automatic Differentiation - Taylor Arithmetics

[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


On Friday, April 19, 2019 at 5:48:09 AM UTC-7, Nisoli Isaia wrote:
>
> 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
>

-- 
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+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Automatic Differentiation - Taylor Arithmetics

[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

El viernes, 19 de abril de 2019, 14:48:09 (UTC+2), Nisoli Isaia escribió:
>
> 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
>

-- 
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+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: Automatic Differentiation - Taylor Arithmetics

[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

On 24/04/2019 2:33, Nisoli Isaia wrote:

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


On Monday, April 22, 2019 at 4:59:36 AM UTC-3, Marc Mezzarobba wrote:

Nisoli Isaia wrote:
 > P.=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


--
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+unsubscr...@googlegroups.com 
.
To post to this group, send email to sage-devel@googlegroups.com 
.

Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.


--
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+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Automatic Differentiation - Taylor Arithmetics

[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


On Monday, April 22, 2019 at 4:59:36 AM UTC-3, Marc Mezzarobba wrote:
>
> Nisoli Isaia wrote: 
> > P.=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 
>
>

-- 
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+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Automatic Differentiation - Taylor Arithmetics

[Marc Mezzarobba]

Nisoli Isaia wrote:
> P.=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

-- 
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+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Automatic Differentiation - Taylor Arithmetics

[Nisoli Isaia]

On Saturday, April 20, 2019 at 5:36:46 AM UTC-3, Marc Mezzarobba wrote:
>
> 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. 
>

Dear Marc,
can you pinpoint me to how to have access to these?
I tried 

P.=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 
>
>

-- 
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+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Automatic Differentiation - Taylor Arithmetics

[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

-- 
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+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.