betaFeedback

WorksMathematics

Efficient Implementation of Diagonally Implicit Runge-Kutta Methods for Model Predictive Control

Abstract

In direct shooting methods for nonlinear optimal control, one of the major computational costs is simulation of the system and calculation of sensitivities. These costs are particularly steep when the stiffness of the controlled system prescribes the use of implicit integrators, amongst which, implicit Runge-Kutta schemes are most popular. These methods require the use of Newton's method to solve a moderately sized system of nonlinear equations with a dense Jacobian, the computation of which grows cubically with the number of stages, that is, the number of abscissa. To mitigate this we investigate the use of the family of Diagonally Implicit Runge-Kutta (DIRK) methods whose Butcher tableaux are lower triangular. We describe the structure exploiting linear algebra required to make the DIRK methods competitive with fully implicit methods, including efficient sensitivity calculations. Finally, we evaluate the performance of DIRK methods on several example systems, and show that the efficient implementation yields Pareto optimal integration schemes. The fixed step size integrators are provided as part of the acados package and use high-performance linear algebra provided by BLASFEO.

Introduction

In Nonlinear Model Predictive Control (NMPC) a feedback scheme is realized by repeatedly (and often approximately) solving the nonlinear optimal control problem:

min⁡x0,…,xNu0,…,uN−1∑i=0N−1L(xi,ui)+M(xN)s.t.x0=x^0,xi+1=F(xi,ui),i=0,…,N−1,gi(xi,ui)≤0,i=1,…,N−1,gN(xN)≤0,(1)\begin{aligned} \min_{x_0,\ldots,x_N \atop u_0,\ldots,u_{N-1}} \quad& \sum_{i=0}^{N-1} L(x_i,u_i) + M(x_N) \\ \text{s.t.}\quad& x_0 = \hat{x}_0, \\ & x_{i+1} = F(x_i,u_i), \quad i=0,\ldots,N-1, \\ & g_i(x_i,u_i) \le0, \quad i=1,\ldots,N-1, \\ & g_N(x_N) \le0, \tag*{(1)} \end{aligned}

where F(xi,ui):Rnx×Rnu→RnxF(x_i,u_i): \mathbb{R}^{n_x} \times\mathbb{R}^{n_u} \to\mathbb{R}^{n_x} is the numerical discretization of a continuous-time semi-explicit Differential-Algebraic Equation (DAE):

x˙=f(x,z,u),0=g(x,z,u),(2)\begin{aligned} \dot{x} &= f(x,z,u), \\ 0 &= g(x,z,u), \tag*{(2)} \end{aligned}

with differential state x∈Rnxx \in\mathbb{R}^{n_x}, algebraic state z∈Rnzz \in\mathbb{R}^{n_z}, and control u∈Rnuu \in\mathbb{R}^{n_u}. Specialized solvers for NMPC such as acados [1] and fatrop [2] focus on sub-problems with a linear multiple shooting structure. A major component

of building these sub-problems is the linearization of the dynamics xi+1=F(xi,ui)x_{i+1}=F(x_i,u_i):

xi+1=Aixi+Biui,(3)x_{i+1}=A_i x_i+B_i u_i, \tag*{(3)}

with linear dynamics Ai=∇xiF(xi,ui)∈Rnx×nxA_i=\nabla_{x_i}F(x_i,u_i)\in\mathbb{R}^{n_x\times n_x}, and Bi=∇uiF(xi,ui)∈Rnx×nuB_i=\nabla_{u_i}F(x_i,u_i)\in\mathbb{R}^{n_x\times n_u}.

In order to formulate the linearized dynamics, numerical integration schemes which can provide sensitivities are required. In many applications, the continuous time DAE is in fact a non-stiff Ordinary Differential Equation (ODE) and can be easily handled via explicit integration schemes such as the famous fourth order explicit scheme RK4. However, when the dynamics are numerically stiff, such explicit schemes are inefficient and implicit schemes must be used [3]. In these cases it is often suggested [4] that practitioners use members of the Gauss-Legendre or Radau-IIA classes of methods, which are both Fully-Implicit Runge-Kutta (FIRK) methods. This is because these methods are of the order proportional to twice the number of stages, and thus offer good efficiency regarding the trade-off between accuracy and evaluation cost.

The field of numerical integration using Runge-Kutta methods has, however, spent many decades developing schemes with Butcher tableaux [5] with exploitable structure. These include a zoo of Diagonally Implicit Runge-Kutta (DIRK) methods [6, 7, 8], along with the Singly Implicit Runge-Kutta (SIRK) methods [9], [10]. These structured tableaux allow for more efficient solving of the nonlinear systems of equations by accelerating the factorization of the associated linearizations, when applying Newton’s method [8]. These structured methods are, however, only rarely used in NMPC contexts [11, 12, 13], and we are unaware of any efficient open-source implementations tailored for NMPC. An alternative approach for structure exploitation in the Runge-Kutta equations is to detect and exploit linear dependencies in the model equations. This is also implemented in acados [14] and might even be combined with a structured-tableau approach.

Contributions: In this paper, we discuss the efficient implementation of fixed-step-size SDIRK integrators in the open-source optimal control and MPC software acados. The implementation provides the capability for simulation as well as forward sensitivities, adjoint sensitivities, and symmetric Hessian propagation [15]. We discuss inexact Newton schemes and structure-exploiting calculations which allow for significant theoretical, and, as we verify, practical, speedups over FIRK methods of equivalent order. Finally, we compare our implementation on several system models and hardware platforms, both of which show the practical benefits of high-order SDIRK methods. In particular, we evaluate our implementation on compute constrained embedded hardware typical of NMPC applications.

Background

In this section, we first provide an overview of Runge-Kutta methods and their implementation. For ease of exposition, in the rest of this paper we focus only on ODEs x˙=f(x,u)\dot{x}=f(x,u). Our implementation additionally supports DAEs (2). We then review some background on dense numerical linear algebra, which we use for our theoretical analysis.

Runge-Kutta Methods

The classical differential Runge-Kutta form for a single fixed step size Δt\Delta t can be written as:

ki=f(xn+Δt∑j=1nsaijkj,un),i=1,…,ns,(4)k_i=f\left(x_n+\Delta t\sum_{j=1}^{n_s}a_{ij}k_j,u_n\right),\quad i=1,\ldots,n_s, \tag*{(4)}
xn+1=xn+Δt∑i=1nsbiki,(5)x_{n+1}=x_n+\Delta t\sum_{i=1}^{n_s}b_i k_i, \tag*{(5)}

with a Butcher tableau written as:

ccAA
c1c_1a11a12⋯a1nsa_{11}\quad a_{12}\quad\cdots\quad a_{1n_s}
c2c_2a21a22⋯a2nsa_{21}\quad a_{22}\quad\cdots\quad a_{2n_s}
⋮\vdots⋮⋮⋱⋮\vdots\quad\vdots\quad\ddots\quad\vdots
cnsc_{n_s}ans1ans2⋯ansnsa_{n_s1}\quad a_{n_s2}\quad\cdots\quad a_{n_sn_s}
bbb1b2⋯bnsb_1\quad b_2\quad\cdots\quad b_{n_s}

caption:

:::

where A∈Rns×nsA\in\mathbb{R}^{n_s\times n_s}, b,c∈Rnsb,c\in\mathbb{R}^{n_s}, and ki∈Rnxk_i\in\mathbb{R}^{n_x} for i=1,…,nsi=1,\ldots,n_s are differential integration variables. When the nsn_s abscissae cic_i are all unique (that is, the method is nonconfluent [8]), the equations in (4) can be rewritten in the so-called integral form:

Δtf(si,un)=∑j=1nsdij(sj−xn),i=1,…,ns,(6)\Delta t f(s_i,u_n)=\sum_{j=1}^{n_s}d_{ij}(s_j-x_n),\quad i=1,\ldots,n_s, \tag*{(6)}
xn+1=xn+∑i=1nsb~i(si−xn),(7)x_{n+1}=x_n+\sum_{i=1}^{n_s}\tilde{b}_i(s_i-x_n), \tag*{(7)}

with

ccDD
b~\tilde{b}

caption:

:::

where D∈Rns×ns=A−1D\in\mathbb{R}^{n_s\times n_s}=A^{-1} and b~∈Rns=DTb\tilde{b}\in\mathbb{R}^{n_s}=D^{\mathsf{T}}b [4]. In this form si∈Rnxs_i\in\mathbb{R}^{n_x} for i=1,…,nsi=1,\ldots,n_s, are the values of the differential state at the abscissa cic_i, and s∈Rnsnxs\in\mathbb{R}^{n_sn_x} is the concatenation of these values.

In the rest of this paper, we discuss DIRK methods, that is, methods where the matrix AA (and therefore also DD) is lower triangular. Several extensions of the DIRK concept exist, of which we focus on the Singly Diagonally Implicit Runge-Kutta (SDIRK) methods. SDIRK methods are defined by a lower triangular tableau, with equal diagonal elements aii=γa_{ii}=\gamma, with i=1,…,nsi=1,\ldots,n_s, as shown in Figure 1. This property additionally holds for the integral form with dii=γ−1d_{ii}=\gamma^{-1}, i=1,…,nsi=1,\ldots,n_s.

Sparsity structure of A matrices

Figure 1. Sparsity structure of AA matrices.

In both the differential (4) and integral (5) case, the RK integration step reduces to the solution of a square system of nonlinear equations of dimension nsnxn_sn_x. In the integral case this is written:

hi(s;xn,un)=∑j=1nsdij(sj−xn)−hf(si,un)=0,(7)(8)h_i(s;x_n,u_n)=\sum_{j=1}^{n_s}d_{ij}(s_j-x_n)-h f(s_i,u_n)=0,\quad(7) \tag*{(8)}

for i=1,…,nsi=1,\ldots,n_s. In a practical implementation, this involves applying Newton’s method to the system

HkΔs=−hk(9)H^k\Delta s=-h^k \tag*{(9)}
sk+1=sk+Δs,(10)s^{k+1}=s^k+\Delta s, \tag*{(10)}

where Hk=∇sh(sk;xn,un)∈Rnsnx×nsnxH^k=\nabla_s h(s^k;x_n,u_n)\in\mathbb{R}^{n_sn_x\times n_sn_x}, and hk=h(sk;xn,un)∈Rnsnxh^k=h(s^k;x_n,u_n)\in\mathbb{R}^{n_sn_x}.

Numerical Linear Algebra

There are two major computational costs associated with implicit RK schemes: function (and Jacobian) evaluation, and the numerical linear algebra involved in the (possibly inexact) Newton’s method (8) used to solve the corresponding set of nonlinear equations (7). We measure these costs as a number of Floating Point Operations (FLOPs), e.g. additions, multiplications, and divisions. In general a linear system

Ax=b,Ax=b,

is solved for x∈Rnx\in\mathbb{R}^n by first factorizing the matrix A∈Rn×nA\in\mathbb{R}^{n\times n}, most commonly by the LU factorization A=LUA=LU with LL lower triangular, and UU upper triangular (and (in the most naive case) done in 23n3\frac{2}{3}n^3 FLOPs. These factors are then used in sequence to solve:

Ly=b,Ux=y,Ly=b,\qquad Ux=y,

with y∈Rny\in\mathbb{R}^n. Each of these operations, called triangular back-solves, take a total of 2n2−n2n^2-n FLOPs. Note that if we are solving the matrix equation AX=BAX=B with X,B∈Rn×mX,B\in\mathbb{R}^{n\times m}, the corresponding back-solves require 2mn2−mn2mn^2-mn FLOPs. A general dense matrix multiplication of ABAB with A∈Rn×pA\in\mathbb{R}^{n\times p}, B∈Rp×mB\in\mathbb{R}^{p\times m}, takes nm(2p−1)nm(2p-1) FLOPs. Finally, when A∈Rn×nA\in\mathbb{R}^{n\times n} is diagonal the multiplication with B∈Rn×mB\in\mathbb{R}^{n\times m} only requires n(2m−1)n(2m-1) FLOPs [16].

Exploiting Structure

In this section, we discuss the structure of the Newton system (8), which is induced by the assumptions in DIRK methods. To this end, we first discuss the computational costs involved in forward simulation of the system, followed by those involved in the calculation of sensitivities. We discuss how the block diagonal structure of DIRK methods can be exploited, as well as exploiting the common elements on the diagonal of AA in SDIRK methods. We then evaluate the theoretical improvement of the different formulations in terms of FLOP counts, when compared to FIRK methods.

Computational Complexity for FIRK

While FLOPs are not a complete evaluation of a numerical algorithm, there is often strong correlation between wall time performance and the amount of work an algorithm does. Therefore, we first evaluate the computational cost for a fixed step size FIRK method with nsn_s stages. The computation required can be split into two components: the solution of h(s,x,z,u)=0h(s,x,z,u)=0 via Newton’s method, and sensitivity computation via application of the implicit function theorem.

During Newton’s method there are two operations which constitute the vast majority of the computational effort: factorizing the matrix HH, and back-solving for Δs\Delta s. In the case of an nsn_s stage FIRK method this corresponds to:

ζnewton=ζfactor+ζbacksolve=23(nsnx)3+2(nsnx)2−2(nsnx),\begin{aligned} \zeta_{\mathrm{newton}} &= \zeta_{\mathrm{factor}}+\zeta_{\mathrm{backsolve}}\\ &= \frac{2}{3}(n_s n_x)^3+2(n_s n_x)^2-2(n_s n_x), \end{aligned}

which must be done at each Newton iteration. The sensitivity calculation phase then consists of a matrix valued back-solve:

Sxu=H−1[∇xh∇uh](11)S_{xu}=H^{-1} \begin{bmatrix} \nabla_x h\\ \nabla_u h \end{bmatrix} \tag*{(11)}

where SxuS_{xu} is the concatenation of matrix AA and BB in (3). If the factors of the matrix HH are already available at the solution, then this corresponds to a matrix valued back-solve with the FLOP cost:

ζsens=(nu+nx)(2(nsnx)2−2(nsnx)).\zeta_{\mathrm{sens}}=(n_u+n_x)\left(2(n_s n_x)^2-2(n_s n_x)\right).

The total cost in FLOPs for a single step of a FIRK integrator is on the order of:

ζtotal=Mζnewton+ζsens≈23Mnx3ns3+2(nx3+(nu+1)nx2)ns2,\begin{aligned} \zeta_{\mathrm{total}}&=M\zeta_{\mathrm{newton}}+\zeta_{\mathrm{sens}}\\ &\approx\frac{2}{3}Mn_x^3n_s^3+2\left(n_x^3+(n_u+1)n_x^2\right)n_s^2, \end{aligned}

with MM being the number of Newton iterations required for convergence to a prescribed tolerance. In practice, we observe that performing a few Newton iterations suffices to achieve a low tolerance, practically speaking 3 to 5.

Lower Block Triangular Form

When the matrix AA (or DD) is lower triangular, the Jacobians of both the differential and integral Runge-Kutta equations are block lower triangular:

Hk=[H11k0⋯0H21kH22k⋯0⋮⋮⋱⋮Hns1kHns2k⋯Hnsnsk],H^k= \begin{bmatrix} H^k_{11} & 0 & \cdots& 0\\ H^k_{21} & H^k_{22} & \cdots& 0\\ \vdots& \vdots& \ddots& \vdots\\ H^k_{n_s1} & H^k_{n_s2} & \cdots& H^k_{n_sn_s} \end{bmatrix},

with each block Hijk∈Rnx×nxH^k_{ij}\in\mathbb{R}^{n_x\times n_x}. It is well known [16] that block triangular systems of the form in Equation (8) can be solved via the recursion:

HiikΔsi=−sik−∑j=1i−1HijkΔsj,for i=1,…,ns.(12)H^k_{ii}\Delta s_i=-s^k_i-\sum_{j=1}^{i-1}H^k_{ij}\Delta s_j,\qquad\text{for }i=1,\ldots,n_s. \tag*{(12)}

When using this structured solve the FLOP cost of the factorization is reduced to

ζ^factor=23nsnx3,\hat{\zeta}_{\mathrm{factor}}=\frac{2}{3}n_s n_x^3,

as it is only necessary to factor the nsn_s square matrices HiiH_{ii} of size nx×nxn_x\times n_x. In the case of the formulation (6), we further observe that the block matrices of HkH^k below the diagonal are all scaled identity matrices. This simplifies (12) to

HiikΔsi=−sik−∑j=1i−1aijΔsj,H^k_{ii}\Delta s_i=-s^k_i-\sum_{j=1}^{i-1}a_{ij}\Delta s_j,

meaning the total work needed for the back-solve reduces to

ζ^backsolve=ns(2nx2−nx)+12(ns−1)nsnx.\hat{\zeta}_{\mathrm{backsolve}}=n_s(2n_x^2-n_x)+\frac{1}{2}(n_s-1)n_s n_x.

Finally, the matrix-valued back-solve required for sensitivity calculation requires nx+nun_x+n_u vector back-solves as before. In total, this yields a total amount of FLOPs of

ζ^total=M(23nsnx3)+(M+nx+nu)(ns(2nx2−nx)+12(ns−1)nsnx).\hat{\zeta}_{\mathrm{total}}=M\left(\frac{2}{3}n_s n_x^3\right)+(M+n_x+n_u)\left(n_s(2n_x^2-n_x)+\frac{1}{2}(n_s-1)n_s n_x\right).

Note that if one implements the integrator using the differential form as in (4), the blocks HijkH^k_{ij} with i≠ji\ne j, become dense. This means that the back-solve requires O(ns2)O(n_s^2) dense matrix-vector multiplications of size nxn_x, making the high-order term increase from O(nsnx3)O(n_s n_x^3) to O(ns2nx3)O(n_s^2 n_x^3). This significantly impacts the practical performance of DIRK methods, making them nearly entirely outclassed for moderate amounts of stages when adjusted for equivalent order accuracy.

Jacobian Block Reuse

In the case of SDIRK methods, additional FLOP count reductions can be achieved in the regime where the Jacobian of the dynamics changes slowly [13]. When this is the case, the singly implicit characteristic can be exploited by replacing the matrices HiikH^k_{ii} with an approximation

H^k=γI−Δt∇xf(xn,u).\hat{H}^k=\gamma I-\Delta t\nabla_x f(x_n,u).

The inexact Newton system solve for Δs\Delta s then becomes:

H^kΔsi=−sik−∑j=1i−1aijΔsj.\hat{H}^k\Delta s_i=-s^k_i-\sum_{j=1}^{i-1}a_{ij}\Delta s_j.

This reduces the number of nx×nxn_x\times n_x matrices which need to be factorized at each Newton iteration from nsn_s to 1. In practice, this reduction is significant as high-order accuracy DIRK methods require comparatively many stages. This approximation also reduces the number of times the Jacobian of the dynamics needs to be evaluated by the same factor, which is, however, not a dominating factor in the domain of interest.

Sensitivity Calculation Considerations

This Jacobian reuse in the prior section is, however, only practical for reducing the computational cost of the Newton iterations. In optimal control, we additionally require accurate forward sensitivities. For the sensitivity calculation SxuS_{xu}, we calculate the true matrix HH at the solution, and use the accurate factorization when applying the implicit function theorem to (6). This constitutes additional factorizations of nsn_s square nx×nxn_x \times n_x matrices. In principle if only approximate sensitivities are required, this additional cost can also be avoided, but this exacerbates inaccuracies at large step sizes. The effects of this approximation in optimal control has been recently studied by Christensen and Jørgensen [17], and were found to have a negative impact on achievable accuracy.

While Hessian approximations are common in practical methods for NMPC, exact Hessian methods might result in better convergence properties [18] and are required for computing solution sensitivities [19]. As a consequence, a fully featured integrator needs to provide exact Hessian propagation, requiring adjoint sensitivity calculation which corresponds to a vector back-solve with H⊤H^\top [15]. While we do not discuss them in detail, the proposed implementation supports efficient computation of adjoint and second-order sensitivities by exploiting the block triangular HH matrix.

We plot approximate FLOP counts in Figure 2, comparing SDIRK and FIRK methods of equivalent order accuracy, assuming M=5M = 5. At moderate system sizes, we see significant, but not order-of-magnitude, reductions in the amount of work that needs to be done. For DIRK methods where we cannot reuse the stage factorization, the reduction is not as significant and requires larger systems for significant benefits to be seen. As such, we focus primarily on evaluating the available SDIRK methods.

Figure 2. Relative amount of work, including exact forward sensitivities, for given order SDIRK versus FIRK method.

Numerical Experiments

This section details several numerical experiments to investigate the practical usefulness of SDIRK methods.2 First, we compare integrator efficiency, both including and excluding forward sensitivity calculation, using SDIRK and FIRK methods on a nonlinear fixed wing aircraft with nx=22n_x = 22 [20]. To demonstrate the practical benefits of SDIRK methods in the case of embedded processors, we benchmark integrator performance on a series of platforms with tighter compute constraints. This reveals the stronger sensitivity of embedded MPC to the theoretical reduction in FLOP count compared to desktop x86-64 processors with wider Single Instruction, Multiple Data (SIMD) pipelines. Finally, we evaluate the effects of scaling the state space size on SDIRK performance, using the nonlinear chain of masses example.

Hardware and Software Configuration

The desktop experiments are run on an Intel Core Ultra 7 155H. In order to ensure accurate data we pin the benchmarking process to a single core and fix that core to its base frequency of 3.8 GHz. On the desktop, we compile BLASFEO including the specialized kernels taking advantage of the avx2 instruction set.

The embedded system experiments are run on an Broadcom BCM2711, quad-core Cortex-A72, clocked at 1.8 GHz, with the benchmarking process again pinned to one core. For the embedded processor, we use the ARMV8A_ARM_CORTEX_A57 target for BLASFEO, which includes specialized kernels and sizing for Cortex-A72 processors, as well as taking advantage of the NEON instruction set extension. Finally, to emulate an even more resource constrained environment we include a configuration using the Cortex-A72 as a hardware platform, paired with BLASFEO built against the GENERIC target. This is a pure C implementation of BLASFEO which does not take advantage of SIMD specialized kernels, and only the number of floating point registers available [21].

The SDIRK implementation in acados that accompanies this paper implements the following SDIRK methods:

  • An order 3 method with 2 stages [22],

  • An order 4 method with 3 stages [22],

  • An order 5 method with 5 stages [8],

  • An order 6 stiffly accurate method with 9 stages [23],

  • An order 7 method with 11 stages [23],

along with several high order SDIRK methods [23] which are uncompetitive for systems smaller than nx≈100n_x \approx100.

Fixed-wing Aircraft

As a first benchmark example, we study a fixed wing aircraft with actuated control surfaces as used in [20], which we regard in explicit form using a symbolic inversion of the inertia matrix. To evaluate the practical computational efficiency, we solve an initial value problem with a sequence of nominal controls. The terminal state of this problem is then compared to a high-accuracy solution xexactx^{\mathrm{exact}} computed by an 8 stage Radau-IIA method with 100 integration steps per control interval. The control step is taken to be 200 milliseconds, and we evaluate each integrator with nsteps=1,2,5,10n_{\mathrm{steps}} = 1, 2, 5, 10 steps on each control interval.

The plots in Figure 3, Figure 5, and Figure 6 show the trade-off between integrator accuracy and computation time in milliseconds, both with and without sensitivity calculations. As we are primarily interested in optimal control applications, we focus first on the results including exact sensitivity calculation. The resulting Pareto front on a modern laptop x86-64 processor (Figure 3) shows a relatively comparable efficiency between FIRK and SDIRK methods on a system of this size. Evaluating the performance on the arm64 processor with SIMD pipelines (Figure 5) shows a stronger advantage to using SDIRK methods when medium to high accuracy is required. Constraining computational resources further by not using SIMD exploiting kernels on the arm64 processor yields the most compelling results. In this environment, the SDIRK methods dominate the Pareto front across the entire range of accuracies and compute times.

Pareto plots for the fixed wing aircraft model on x86-64 CPU

Figure 3. Pareto plots for the fixed wing aircraft model on x86-64 CPU.

Figure 5. Pareto plots for the fixed wing aircraft model on arm64 CPU.

Figure 6. Pareto plots for the fixed wing aircraft model on arm64 CPU, using the GENERIC target in BLASFEO.

We observe a similar improvement in relative performance in the case where sensitivities are not needed. However, in this case, SDIRK methods dominate the Pareto front on all platforms. Of particular interest are the very high order accuracy methods of Alamri et al. [23] which have only recently been developed and show particularly strong efficiency at high accuracy requirements.

The above results suggest that SDIRK methods can indeed be competitive with FIRK methods in the context of NMPC. However, there are some caveats that practitioners should be aware of when choosing methods. Particularly, the SIMD performance of modern desktop and laptop processors make the efficiency trade-off significantly less appealing. Additionally, we note that while much is often spoken about the order accuracy of different RK methods, little is said about truncation error. The performance particularly of the 3 stage order 4 SDIRK method suffers significantly from its relatively large truncation error factor [8]. This makes it a generally uncompetitive method even though its order accuracy is high.

Ratio of SDIRK to FIRK computational time

Figure 4. Ratio of SDIRK to FIRK computational time.

Chain of Masses

As a second system, we regard the so-called nonlinear chain of masses described in [24]. In order to evaluate the performance of the SDIRK methods as the system size grows, we consider the system for different number of masses ranging from 3 to 125.

We compare the resulting runtime ratio between SDIRK and FIRK methods. We see from these results that as the state space dimension grows, the benefits of using SDIRK methods becomes more prominent. In practice, this is due to both the reduction in cost of the Newton steps involved in SDIRK methods, as well as cache effects as the matrix HkH^k begins to exceed the size of the L1 cache of the CPU. The second is quite pronounced as the state dimension scales towards nx≈500n_x \approx500, where FIRK methods begin to be dominated by memory access times. Additionally, the effects of improved throughput as matrix size increases are well documented [21], which is shown by the worse than expected performance ratios for small systems.

Conclusions and Future Work

In this paper, we describe the efficient implementation of Singly Diagonally Implicit Runge-Kutta (SDIRK) methods in the acados software package. We show that when carefully implemented, these methods are on the Pareto front for efficiency with respect to the trade-off between accuracy and computational time. This holds even when the calculation of accurate sensitivities is required. We further show that this efficiency persists in the case of recently developed, high-order, methods with many stages [23].

References

@bibliography

References

  1. [1]R. Verschueren, G. Frison, D. Kouzoupis, J. Frey, N. van Duijkeren, A. Zanelli, B. Novoselnik, T. Albin, R. Quirynen, and M. Diehl, “acados – a modular open-source framework for fast embedded optimal control,” Mathematical Programming Computation, pp. 147–183, 2021.arxiv.org/abs/1910.13753
  2. [2]L. Vanroye, A. Sathya, J. De Schutter, and W. Decré, “FATROP: A fast constrained optimal control problem solver for robot trajectory optimization and control,” in 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2023, pp. 10036–10043.arxiv.org/abs/2303.16746
  3. [3]E. Hairer, C. Lubich, and M. Roche, The numerical solution of differential-algebraic systems by Runge-Kutta methods, ser. Lecture Notes in Mathematics. Heidelberg: Springer, 1989, no. 1409.DOI
  4. [4]J. B. Rawlings, D. Q. Mayne, and M. M. Diehl, Model Predictive Control: Theory, Computation, and Design, 2nd ed. Nob Hill, 2017.
  5. [5]J. Butcher, “On the implementation of implicit Runge-Kutta methods,” BIT Numerical Mathematics, vol. 16, no. 3, pp. 237–240, 1976. [Online]. Available: http://dx.doi.org/10.1007/BF01932265
  6. [6]R. Alexander, “Diagonally implicit Runge-Kutta methods for stiff O.D.E.’s,” SIAM Journal on Numerical Analysis, vol. 14, no. 6, pp. 1006–1021, 1977. [Online]. Available: http://www.jstor.org/stable/2156678DOI
  7. [7]I. T. Cameron, “Solution of differential-algebraic systems using diagonally implicit Runge-Kutta methods,” IMA Journal of Numerical Analysis, vol. 3, pp. 273–289, 1983.DOI
  8. [8]C. A. Kennedy and M. H. Carpenter, “Diagonally implicit Runge-Kutta methods for ordinary differential equations: a review,” NASA, Tech. Rep., 2016.
  9. [9]E. H. Nilsen, “The implementation of sirk methods for differential algebraic equations,” University of Auckland, Tech. Rep., 1997.
  10. [10]C. A. Kennedy and M. H. Carpenter, “Singly-Implicit Runge–Kutta methods for stiff, Ordinary Differential-Equations,” NASA, Tech. Rep., 2025.
  11. [11]T. G. Flaig, “Implicit Runge–Kutta schemes for optimal control problems with evolution equations,” Computational Methods in Applied Mathematics, vol. 23, no. 4, pp. 917–952, 2023.arxiv.org/abs/1311.0640
  12. [12]M. J. Schytt and J. B. Jørgensen, “Numerical methods for optimal boundary control of advection-diffusion-reaction systems,” IFAC-PapersOnLine, vol. 58, no. 18, pp. 288–295, 2024.DOI
  13. [13]A. H. D. Christensen, N. Cantisani, and J. B. Jørgensen, “ESDIRK-based nonlinear model predictive control for stochastic differential-algebraic equations,” in 2025 European Control Conference (ECC). IEEE, 2025, pp. 2657–2662.arxiv.org/abs/2407.18852
  14. [14]J. Frey, R. Quirynen, D. Kouzoupis, G. Frison, J. Geisler, A. Schild, and M. Diehl, “Detecting and exploiting Generalized Nonlinear Static Feedback structures in DAE systems for MPC,” in Proceedings of the European Control Conference (ECC), 2019.DOI
  15. [15]R. Quirynen, “Numerical simulation methods for embedded optimization,” Ph.D. dissertation, KU Leuven and University of Freiburg, 2017.DOI
  16. [16]I. S. Duff, A. M. Erisman, and J. K. Reid, Direct methods for sparse matrices. USA: Clarendon Press, 1987.
  17. [17]A. H. D. Christensen and J. B. Jørgensen, “A comparative study of sensitivity computations in ESDIRK-based optimal control problems,” European Journal of Control, vol. 80, p. 101064, 2024, 2024 European Control Conference Special Issue. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0947358024001249DOI
  18. [18]J. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed., ser. Springer Series in Operations Research and Financial Engineering. Springer, 2006.
  19. [19]J. Frey, K. Baumgärtner, G. Frison, D. Reinhardt, J. Hoffmann, L. Fichtner, S. Gros, and M. Diehl, “Differentiable nonlinear model predictive control,” Advances in neural information processing systems (accepted for publication), 2026.arxiv.org/abs/2505.01353
  20. [20]S. Gros, R. Quirynen, and M. Diehl, “Aircraft control based on fast nonlinear MPC & multiple-shooting,” in Proceedings of the IEEE Conference on Decision and Control (CDC), 2012.DOI
  21. [21]G. Frison, D. Kouzoupis, T. Sartor, A. Zanelli, and M. Diehl, “BLASFEO: Basic linear algebra subroutines for embedded optimization,” ACM Transactions on Mathematical Software (TOMS), vol. 44, no. 4, pp. 42:1–42:30, 2018.DOI
  22. [22]S. P. Norsett, “Semi-explicit Runge-Kutta methods,” Department of Mathematics, University of Trondheim, Tech. Rep. 6, 1974.
  23. [23]Y. Alamri and D. I. Ketcheson, “Very high-order A-stable stiffly accurate diagonally implicit Runge-Kutta methods with error estimators,” Journal of Scientific Computing, vol. 100, no. 3, p. 84, 2024.
  24. [24]L. Wirsching, H. G. Bock, and M. Diehl, “Fast NMPC of a chain of masses connected by springs,” in Proceedings of the IEEE International Conference on Control Applications, Munich, 2006, pp. 591–596.

Paper details

vlnc:W_d4ungczy
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents