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:
where is the numerical discretization of a continuous-time semi-explicit Differential-Algebraic Equation (DAE):
with differential state , algebraic state , and control . 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 :
with linear dynamics , and .
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 . 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 can be written as:
with a Butcher tableau written as:
caption:
:::
where , , and for are differential integration variables. When the abscissae are all unique (that is, the method is nonconfluent [8]), the equations in (4) can be rewritten in the so-called integral form:
with
caption:
:::
where and [4]. In this form for , are the values of the differential state at the abscissa , and is the concatenation of these values.
In the rest of this paper, we discuss DIRK methods, that is, methods where the matrix (and therefore also ) 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 , with , as shown in Figure 1. This property additionally holds for the integral form with , .

Figure 1. Sparsity structure of 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 . In the integral case this is written:
for . In a practical implementation, this involves applying Newton’s method to the system
where , and .
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
is solved for by first factorizing the matrix , most commonly by the LU factorization with lower triangular, and upper triangular (and (in the most naive case) done in FLOPs. These factors are then used in sequence to solve:
with . Each of these operations, called triangular back-solves, take a total of FLOPs. Note that if we are solving the matrix equation with , the corresponding back-solves require FLOPs. A general dense matrix multiplication of with , , takes FLOPs. Finally, when is diagonal the multiplication with only requires 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 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 stages. The computation required can be split into two components: the solution of 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 , and back-solving for . In the case of an stage FIRK method this corresponds to:
which must be done at each Newton iteration. The sensitivity calculation phase then consists of a matrix valued back-solve:
where is the concatenation of matrix and in (3). If the factors of the matrix are already available at the solution, then this corresponds to a matrix valued back-solve with the FLOP cost:
The total cost in FLOPs for a single step of a FIRK integrator is on the order of:
with 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 (or ) is lower triangular, the Jacobians of both the differential and integral Runge-Kutta equations are block lower triangular:
with each block . It is well known [16] that block triangular systems of the form in Equation (8) can be solved via the recursion:
When using this structured solve the FLOP cost of the factorization is reduced to
as it is only necessary to factor the square matrices of size . In the case of the formulation (6), we further observe that the block matrices of below the diagonal are all scaled identity matrices. This simplifies (12) to
meaning the total work needed for the back-solve reduces to
Finally, the matrix-valued back-solve required for sensitivity calculation requires vector back-solves as before. In total, this yields a total amount of FLOPs of
Note that if one implements the integrator using the differential form as in (4), the blocks with , become dense. This means that the back-solve requires dense matrix-vector multiplications of size , making the high-order term increase from to . 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 with an approximation
The inexact Newton system solve for then becomes:
This reduces the number of matrices which need to be factorized at each Newton iteration from 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 , we calculate the true matrix at the solution, and use the accurate factorization when applying the implicit function theorem to (6). This constitutes additional factorizations of square 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 [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 matrix.
We plot approximate FLOP counts in Figure 2, comparing SDIRK and FIRK methods of equivalent order accuracy, assuming . 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 [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 .
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 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 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.

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.

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 begins to exceed the size of the L1 cache of the CPU. The second is quite pronounced as the state dimension scales towards , 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]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]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]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]J. B. Rawlings, D. Q. Mayne, and M. M. Diehl, Model Predictive Control: Theory, Computation, and Design, 2nd ed. Nob Hill, 2017.
- [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]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]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]C. A. Kennedy and M. H. Carpenter, “Diagonally implicit Runge-Kutta methods for ordinary differential equations: a review,” NASA, Tech. Rep., 2016.
- [9]E. H. Nilsen, “The implementation of sirk methods for differential algebraic equations,” University of Auckland, Tech. Rep., 1997.
- [10]C. A. Kennedy and M. H. Carpenter, “Singly-Implicit Runge–Kutta methods for stiff, Ordinary Differential-Equations,” NASA, Tech. Rep., 2025.
- [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]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]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]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]R. Quirynen, “Numerical simulation methods for embedded optimization,” Ph.D. dissertation, KU Leuven and University of Freiburg, 2017.DOI
- [16]I. S. Duff, A. M. Erisman, and J. K. Reid, Direct methods for sparse matrices. USA: Clarendon Press, 1987.
- [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]J. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed., ser. Springer Series in Operations Research and Financial Engineering. Springer, 2006.
- [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]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]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]S. P. Norsett, “Semi-explicit Runge-Kutta methods,” Department of Mathematics, University of Trondheim, Tech. Rep. 6, 1974.
- [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]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.


