Efficient Explicit Taylor ODE Integrators with Symbolic-Numeric Computing Songchen Tan, Oscar Smith, Christopher Rackauckas Abstract Taylor series methods show a newfound promise for the solution of non-stiff ordinary differential equations (ODEs) given the rise of new compiler-enhanced techniques for calculating high order derivatives. In this paper we detail a new Julia-based implementation that has two important techniques: (1) a general purpose higher-order automatic differentiation engine for derivative evaluation with low overhead; (2) a combined symbolic-numeric approach to generate code for recursively computing the Taylor polynomial of the ODE solution. We demonstrate that the resulting software’s compiler-based tooling is transparent to the user, requiring no changes from interfaces required to use standard explicit Runge-Kutta methods, while achieving better run time performance. In addition, we also developed a comprehensive adaptive time and order algorithm that uses different step size and polynomial degree across the integration period, which makes this implementation more efficient and versatile in a broad range of dynamics. We show that for codes compatible with compiler transformations, these integrators are more efficient and robust than the traditionally used explicit Runge-Kutta methods. keywords ODE numerical integrators, automatic differentiation, Taylor series, the Julia language † † runningheads: Efficient Explicit Taylor ODE Integrators with Symbolic-Numeric Computing / S. Tan, O. Smith and C. Rackauckas 1 Introduction The numerical integration of ordinary differential equations (ODEs) remains a cornerstone of computational science and engineering, with applications ranging from celestial mechanics and astrodynamics [ 4 ] , fluid dynamics [ 15 ] , and control systems [ 32 ] to modern machine learning models such as neural ODEs [ 11 ] . Among diverse classes of integrators for non-stiff problems, methods based on Taylor polynomials (also known as Taylor methods) [ 12 ] offer an intriguing alternative to the more widely employed Runge–Kutta schemes [ 1 , 23 , 24 , 30 ] . In an explicit Taylor method, one computes a Taylor polynomial of the solution about the current time and then uses that polynomial to advance the solution for a step size. Formally, for an initial value problem u^{\prime}=f(u,t);\quad u(t_{0})=u_{0} with f:(\mathbb{R}^{d}\times\mathbb{R})\to\mathbb{R}^{d} and u_{0}\in\mathbb{R}^{d} , assuming the discretized times are t_{n} for n\in\mathbb{N} , corresponding solution values are u_{n}=u(t_{n}) , derivatives are u_{n}^{(k)}=(\mathrm{d}^{k}u/\mathrm{d}t^{k})(t_{n}) . At each step, one computes a polynomial of degree p and step size h : u_{n+1}=u_{n}+u^{(1)}_{n}h+\frac{1}{2}u^{(2)}_{n}h^{2}+\cdots+\frac{1}{p!}u^{(p)}_{n}h^{p} For the rest of this paper we will omit the word “explicit” and refer to this as the “Taylor method”. The appeal of Taylor methods lies chiefly in two features. Firstly, for sufficiently smooth functions f one can systematically increase the convergence order of the method by computing more terms in the polynomial (via automatic differentiation). For problems requiring very high precision (e.g., long‐term orbit propagation, sensitivity analysis), high‐order Taylor methods can outperform standard methods [ 18 , 3 ] . Secondly, the polynomial interpolation of solution u comes for free in the Taylor approach, therefore one can readily compute u(t) for arbitrary t\in(t_{n},t_{n+1}) and construct a dense output [ 2 ] . Despite these advantages, Taylor methods have been less popular because of the complexity of evaluating higher-order derivatives, while the most widely used explicit Runge-Kutta methods only require that the user supplies the function f to the solver. For evaluating higher-order derivatives, because numerical differentiation is too slow and inaccurate, Taylor methods need some way to compute higher order derivatives exactly, which either requires user intervention to derive such functions or some automatic differentiation via algorithmic, symbolic, or compiler means. The chief challenge is to construct an automatic differentiation engine that can compute arbitrary high order derivatives of a broad range of functions with small overhead [ 10 ] . In addition, computing the Taylor polynomial of an ODE solution is a recursive process in nature [ 17 ] , which must be combined in a clever way with the aforementioned higher-order automatic differentiation engine. If, instead, the automatic differentiation engine is regarded as a separate “black box” from the ODE integrator, there will be a lot of redundancies. To see this, one can imagine the procedure for p=3 : 1. Obtain u_{n}^{(1)} using the relation u_{n}^{(1)}=f(u(t),t)|_{t=t_{n}} ; 2. Obtain u_{n}^{(2)} using the relation u_{n}^{(2)}=(\mathrm{d}/\mathrm{d}t)(f(u(t),t))|_{t=t_{n}} , which needs u_{n}^{(1)} to be already available; 3. Obtain u_{n}^{(3)} using the relation u_{n}^{(3)}=(\mathrm{d}^{2}/\mathrm{d}t^{2})(f(u(t),t))|_{t=t_{n}} , which needs u_{n}^{(1)},u_{n}^{(2)} to be already available; Note that here \mathrm{d}/\mathrm{d}t means the total derivative \frac{\mathrm{d}}{\mathrm{d}t}f(u(t),t)=\frac{\partial f}{\partial u}\frac{\mathrm{d}u}{\mathrm{d}t}+\frac{\partial f}{\partial t} Therefore, one can only get one additional term with each call to the higher-order AD engine. Assuming that doing order- k AD on f needs O(k^{2}) times the operations in f (which is a reasonable assumption for most implementation of Taylor-mode AD), the total complexity should be O(1^{2}+2^{2}+\cdots+p^{2})=O(p^{3}/3) which is prohibitively expensive [ 17 ] . To overcome this problem, previous implementations such as ATOMFT [ 6 , 10 ] , taylor by Jorba et al [ 18 ] and TIDES [ 2 ] must develop their special-purpose automatic differentiation engine specifically for the application of solving ODEs, which can efficiently handle the recursive computation of Taylor polynomial. These approaches are asymptotically efficient since it is proven [ 17 ] that the complexity could be reduced to O(p^{2}) . However, using languages like C and FORTRAN, they often need a separate build step to transform user-defined functions to the actual code computing Taylor polynomials of ODE solutions, either via a hand-written parser [ 10 ] or another computer algebra system like Mathematica [ 2 ] . The build step imposes significant limitations on how the user could write their ODE function (e.g. they can only use a small set of elementary functions), and makes these implementations hard to incorporate in modern computing environments where scientific and engineering users often call the methods from a dynamical language interface. Within the Julia community, TaylorIntegration.jl [ 20 ] uses a general purpose higher-order automatic differentiation engine [ 5 ] , but relies on ad hoc macros to analyze user-defined functions and partially remove the redundancy in computing Taylor polynomials. This implementation reduces the barrier to use Taylor methods, but still requires users to write ODE functions in a pretty restrictive way such that it could be parsed by the specific macro. We will compare this approach with our approach in more detail in the appendix. In addition to these transformation-based methods, Griewank et al [ 17 ] also introduced a coefficient doubling method that could also reduce the complexity to O(p^{2}) , but at the complexity of concretely storing some Jacobian matrices A_{i}\equiv(\partial u_{i}/\partial u_{0}) . In the context of solving large-scale ODE systems, this is not appealing since the space complexity on dimension d could be O(d^{2}) instead of O(d) . The JAX implementation [ 7 ] of this algorithm tried to avoid storing Jacobians by computing more Jacobian-vector products, but their performance result didn’t show significant improvement compared to recursively computing coefficients. Nevertheless, recent advances in higher-order automatic differentiation engines [ 25 ] and symbolic-numeric computational frameworks [ 16 ] have given Taylor methods new possibilities. In this paper, we utilize these new techniques in developing a new implementation of the Taylor methods of arbitrary order. Our key contributions are: • Non-intrusively composed a general-purpose computer algebra system [ 16 ] with a general-purpose higher-order automatic differentiation engine [ 26 ] to establish an efficient, low-overhead framework for Taylor methods in Julia; • Symbolically removed redundant computation and synthesized code for computing the Taylor polynomial of ODE solution. Compared with previous approaches, this provides a more seamless user experience since the code transformations happen at the user’s first call to the solver using just-in-time compilation, and does not require the user to leave the usual Julia programming environment; • Introduced and systematically evaluated an mechanism to use different step size and polynomial degree across different integration regions. In problems where the convergence radius of Taylor series of ODE functions might vary a lot, the adaptive polynomial degree solvers could outperform their fixed-degree counterparts. The remainder of the paper is organized as follows. In section 2 we introduce the Taylor-mode AD and the symbolic-numeric approach to compute the Taylor polynomial of ODE solutions, as well as a mechanism to control the step size and polynomial degree across the integration time period. Section 3 shows numerical experiments with focus on comparing our integrator to state-of-the-art Runge-Kutta algorithms, and section 4 offers concluding remarks and directions for future research. 2 Theory 2.1 Taylor-mode automatic differentiation for higher-order directional derivatives Let U be an open subset of \mathbb{R}^{d_{1}} , and let f:U\to\mathbb{R}^{d_{2}} be a sufficiently smooth function. The derivative of f at a point x\in\mathbb{R}^{d_{1}} is a linear operator Df(x):\mathbb{R}^{d_{1}}\to\mathbb{R}^{d_{2}} such that it maps a vector v\in\mathbb{R}^{n} to Df(x)[v] , which is the directional derivative of f at x in the direction of v , also known as the Jacobian-vector product. Similarly, for p\in\mathbb{Z}^{+}>1 , the derivative of p -th order of f at a point x is a multilinear operator D^{p}f(x):(\mathbb{R}^{d_{1}},\cdots,\mathbb{R}^{d_{1}})\to\mathbb{R}^{d_{2}} such that it maps a tuple of vectors (v_{1},\ldots,v_{p}) to D^{p}f(x)[v_{1},\cdots,v_{p}] , the directional derivative of f at x in the direction of (v_{1},\ldots,v_{p}) . First-order forward-mode AD can be viewed as an algorithm to propagate directional derivative information through the composition of functions [ 21 ] . For example, let f(x)=g(h(x)) be a composite function for \mathbb{R}^{d_{1}}\to\mathbb{R}^{d_{2}} and x\in\mathbb{R}^{d_{1}} be a specific point in its domain. Suppose that we already have h_{0}=h(x) representing the primal output of h , and h_{1}=Dh(x)[v] representing the perturbation of h along some direction v\in\mathbb{R}^{d_{1}} . Now for the composite function, we want to know what is the perturbation of f along direction v ; in other words, we want to know f_{1}=Df(x)[v] in addition to f_{0}=f(x) . The answer to that is simply the chain rule: • f_{0}=g(h_{0}) • f_{1}=Dg(h_{0})[h_{1}] Similarly, the Taylor-mode AD can be viewed as an algorithm to propagate higher-order directional derivative information through compositions of functions. Suppose that we already have a Taylor bundle for h at x along v : (h_{0},h_{1},\ldots,h_{p})=(h(x),Dh(x)[v],D^{2}h(x)[v,v],\ldots,D^{p}h(x)[v,\ldots,v]) and we want to know (f_{0},f_{1},\ldots,f_{p})=(f(x),Df(x)[v],D^{2}f(x)[v,v],\ldots,D^{p}f(x)[v,\ldots,v]) the answer to that is, in turn, the Faà di Bruno’s formula: • f_{0}=g(h_{0}) • f_{1}=Dg(h_{0})[h_{1}] • f_{2}=D^{2}g(h_{0})[h_{1},h_{1}]+Dg(h_{0})[h_{2}] • \cdots In our practical implementation of Taylor-mode AD, a pushforward rule is defined for every “simple” function, so that derivatives of any complicated functions that are composed of these simple functions can be computed automatically, either via operator-overloading or source-code transformation techniques. Our previous work [ 25 ] has shown that for any functions composed of elementary functions and arbitrary control flow, the p -th order directional derivative is at most O(p^{2}) times more expensive than computing the function itself, in contrast to naively nesting first-order forward-mode AD which could be O(2^{p}) times expensive [ 7 ] . We provided a reference implementation of this method in the Julia language [ 9 ] using its multiple-dispatch mechanism [ 8 ] , TaylorDiff.jl [ 26 ] , featuring an automatic generation [ 16 ] of higher-order pushforward rules from first-order pushforward rules defined in ChainRules.jl [ 31 ] . Below, we will demonstrate how to use Taylor-mode AD to implement ODE solvers. 2.2 Computing Taylor polynomial of ODE solutions In the ODE u^{\prime}=f(u) , the degree- p Taylor polynomial of ODE solution is defined as T_{n}(t)=u_{n}+u_{n}^{(1)}(t-t_{n})+\frac{1}{2}u_{n}^{(2)}(t-t_{n})^{2}+\cdots+\frac{1}{p!}u_{n}^{(p)}(t-t_{n})^{p}+O((t-t_{n})^{p+1}) such that the integration step u_{n+1}:=T_{n}(t_{n+1}) has convergence order p . If we expand both u(t) and f(u(t)) as Taylor series of t near some t_{n} , then we get u_{n}^{(k+1)}=\frac{\mathrm{d}^{k+1}u}{\mathrm{d}t^{k+1}}(t_{n})=\left[\frac{\mathrm{d}^{k}}{\mathrm{d}t^{k}}f(u(t),t)\right]\bigg|_{t=t_{n}},\quad\forall k\in\{0,\cdots,p-1\} Since f is a function of u and t , evaluating the total derivatives through the chain rules (i.e. Taylor-mode automatic differentiation) would require u_{n},u_{n}^{1},\cdots,u_{n}^{k} . Therefore, a naive approach is to do automatic differentiation on f for multiple times, each time one order higher to obtain (\mathrm{d}^{k}/\mathrm{d}t^{k})f(u(t),t)|_{t=t_{n}} and then convert to u_{n}^{(k+1)} . However, this will result in a lot of redundant computation, because when (\mathrm{d}^{k}/\mathrm{d}t^{k})f(u(t),t)|_{t=t_{n}} is computed, (\mathrm{d}^{i}/\mathrm{d}t^{i})f(u(t),t)|_{t=t_{n}} for all i1 , then this step is rejected and the system is reverted to the previous state. If e_{p}\leq 1 , it is then processed by a controller C , which could be one of Integral Controller (I), Proportional-Integral Controller (PI) or Proportional-Integral-Derivative Controller (PID), which will propose a new step size h_{\rm new} based on current step size h and scaled error e_{p} . Overall, the functionality of controllers could be written as h_{\rm new}=C(h,e_{p}) . This mechanism is summarized in algorithm 1 : Algorithm 1 Adaptive step size integration Define \dot{u}=f(u) , integration time range t\in(t_{0},t_{\rm end}) , initial value u=u_{0} Let t=t_{0} and guess an initial step size h while t1 then Reject the step size and revert u else Update step size h\leftarrow C(h,e_{p}) end if end while return u We now discuss the situation where both the degree of Taylor polynomial and step size are adjustable, using similar ideas as in [ 14 , 28 ] . This is a special opportunity for Taylor integration method since the degree can be easily adjusted. Assuming the degree p is allowed to vary in the range [p_{\min},p_{\max}] , and the operations to compute degree p polynomial is proportional to p^{2} as a result of using Taylor-mode automatic differentiation. For each value of p , the controller will propose a h(p) based on the error tolerance, therefore we can define a work-per-time ratio r=p^{2}/h(p) to capture the computational cost per unit of time, and find the p value that minimize this ratio. In practice, to avoid large oscillations in degree p , after each step the integrator is allowed to re-choose the degree among \{p-1,p,p+1\} . This mechanism is summarized in algorithm 2 . Algorithm 2 Adaptive polynomial degree and step size integration Define \dot{u}=f(u) , integration time range t\in(t_{0},t_{\rm end}) , initial value u=u_{0} Let t=t_{0} and guess an initial step size h while t1 then Reject the step size and revert u else Update step size h\leftarrow h_{\rm optimal} , degree p\leftarrow p_{\rm optimal} end if end while return u 3 Experiments 3.1 Solving various non-stiff ODE problems We focus on non-stiff problems, where explicit Taylor methods are theoretically competitive. We test several Taylor methods with different fixed polynomial degree (6, 8, 10, 12) against several Runge-Kutta methods (DP5 [ 13 ] , Tsit5 [ 27 ] , Vern6, Vern8 [ 29 ] ), on the following four non-stiff ODE problems: Lotka-Volterra problem \begin{cases}\dot{x}=ax-bxy\\ \dot{y}=-cy+dxy\end{cases} where t\in(0.0,10.0) , a=1.5,b=1.0,c=3.0,d=1.0 , and x_{0}=y_{0}=1.0 . Fitzhugh-Nagumo problem \begin{cases}\dot{v}=v-v^{3}/3-w+l\\ \dot{w}=(v+a-bw)/\tau\end{cases} where t\in(0.0,10.0) , a=0.7,b=0.8,\tau=12.5,l=0.5 and v_{0}=w_{0}=1.0 . Rigid body problem \begin{cases}\dot{x}=I_{1}yz\\ \dot{y}=I_{2}zx\\ \dot{z}=I_{3}xy+\sin(t)^{2}/4\end{cases} where t\in(0.0,10.0) , I_{1}=-2.0,I_{2}=1.25,I_{3}=-0.5 and x_{0}=1.0,y_{0}=0.0,z_{0}=0.9 . Random linear problem \dot{u}=Au where t\in(0.0,10.0) , A\in\mathbb{R}^{16\times 16} and u_{0}\in\mathbb{R}^{16} , both of their elements are sampled from normal distribution N(0,1) . (a) Lotka-Volterra problem (b) Fitzhugh-Nagumo problem (c) Rigid body problem (d) Random linear problem Figure 2 : Work-precision diagrams for Taylor methods and Runge-Kutta methods in various non-stiff ODE problems While the work-precision curve is similar for same order Taylor methods and Runge-Kutta methods (such as Taylor6 vs Vern6, Taylor8 vs Vern8), the degree of Taylor polynomial (and therefore the convergence order) of Taylor methods can be systematically increased to achieve higher accuracy. Therefore, higher order Taylor methods can have advantage over Runge-Kutta methods, especially at higher precision. 3.2 Adaptive polynomial degree tests We consider the following problem: \dot{y}=\phi^{\prime}(t)(y-y^{2}) where \phi(t)=\kappa\tanh\frac{t-t_{0}}{\delta} and c=2.0,\delta=1.0,t_{0}=5.0,\kappa=10.0 and y_{0}=1/(1+c) . The analytical solution will be y(t)=\frac{1}{1+c\exp\left(-\phi(t)\right)} which has singularity at \phi(t)=\ln c\pm\pi i . Therefore, for some t on the real axis, the convergence radius of Taylor series will be \rho(t)\approx\frac{\pi}{|\phi^{\prime}(t)|} Now, since \phi^{\prime}(t)=\frac{\kappa}{\delta}\cosh^{-2}\left(\frac{t-t_{0}}{\delta}\right) has a peak at t_{0} , it is expected to have small convergence radius near that (the “hard” region) and large convergence radius away from that (the “easy” region). In the hard region, using a large polynomial degree p cannot increase the step size h since it is controlled by the convergence radius, and therefore smaller p is preferred; in the easy region, using a large p can greatly increase the step size, and therefore larger p is preferred. In the work-precision diagram below, we use four different fixed-degree Taylor methods (degree 6, 8, 10 and 12 respectively) and an adaptive-degree Taylor method (degree can vary between 6 and 12) to demonstrate this idea. Figure 3 : Comparison of adaptive-degree Taylor methods (degree can vary between 6 and 12) and fixed-degree Taylor method (6, 8, 10 and 12). At lower tolerances, the adaptive-degree method has a chance to use different degree at different region to achieve better performance. 4 Conclusions In this paper, we introduced explicit Taylor methods and conducted a comprehensive review of existing implementations of it. Pointing out the problems with existing implementations, we proposed a new implementation which leveraged a general purpose higher-order automatic differentiation engine and a computer algebra system, making it efficient, broadly applicable and user-friendly. We then introduced the mechanisms to adjust Taylor polynomial degree and step size at different regions across the integration time period, which help the method to achieve better performance. In numerical experiments, we compared the fixed-degree Taylor methods with various Runge-Kutta methods on four different non-stiff ODE problems. The work-precision diagrams demonstrated the advantage of Taylor methods, especially at higher precision since the convergence order of Taylor methods could be arbitrarily high. We then proposed a problem where very different convergence radii of Taylor series are expected at different regions, making the mechanism of adaptive polynomial degree profitable. In this case, the adaptive-degree Taylor method outperforms the fixed-degree ones. However, as the same for all explicit methods, explicit Taylor methods are generally unsuitable for problems that are significantly stiff, since it might be forced to use very small time steps even with a high degree of Taylor polynomial. We hope to extend our approach toward a better implementation of implicit Taylor methods [ 22 ] as well. Appendix A Comparison with TaylorIntegration.jl Here we present more detail about the comparison with TaylorIntegration.jl, which is another implementation of Taylor methods in Julia that we mentioned before. Based on the same PCR3BP problem, in fig. 4 our implementation shows better performance both before and after simplification, which demonstrates that a general and systematic computer algebra system can perform better than ad hoc code transformers. In addition, while TaylorIntegration.jl requires user to use macros to transform the ODE function as well as rewriting the function in a compatible way, our approach removes the need for any user-facing code modification, and should be readily applied to existing codebases. Figure 4 : Effect of symbolic compilation on computing Taylor polynomial, with both this work and TaylorIntegration.jl. In addition to this work (where naive and simplified are shown in blue and yellow bars), computing with TaylorIntegration.jl is shown in green bars for naive and pink for simplified. In addition to integration with floating point numbers, we note that TaylorIntegration.jl also supports interval arithmetic so it could have other purposes like global error analysis. *