INdAM Workshop: Low-rank Structures and Numerical Methods in Matrix and Tensor Computations

Stage-parallel Runge-Kutta methods via low-rank matrix equation corrections

Sep 1, 2025, 4:10 PM

1h 10m

Palazzone di Cortona

Poster Poster Session

Speaker

Fabio Durastante (Università di Pisa)

Description

Implicit Runge-Kutta (IRK) methods [2] are highly effective for solving stiff ordinary differential equations (ODEs)

\begin{array}{ll}
M {y}'(t)=f({y}(t),t), & t \in [0,T], \
{y}(0) = {y}_0.
\end{array}

However, their usage can be computationally expensive for large-scale problems due to the need to solve coupled algebraic equations at each step. This study improves IRK efficiency by leveraging parallelism to decouple stage computations and reduce communication overhead 1. In the linear case, the generic RK method takes the form

\begin{array}{l}
M {y}'(t) = - L {y}(t) + \hat{{f}}(t), \
{y}(0) = {y}_0,
\end{array} \qquad M,L \in {R}^{N \times N},

for which the computational expensive step is given by the computation of the stages $K$ by

$$ M K= - L {y}_n {1}_s^\top - h L K A^\top + F.$$ If the stage matrix $A$ was diagonalizable as $A = X \Lambda X^{-1}$, this could be solved by doing $$ \begin{array}{l} {r} = - ( X^{-1} {1}_s \otimes L ) {y}_n + \left(X^{-1} \otimes I\right)\textrm{vec}\left( F\right),\\ \left(I_s \otimes M + h \Lambda \otimes L\right) {z} = {r},\\ \textrm{vec} \left( K \right) = \left(X \otimes I\right) {z}. \end{array} $$ This is not the case in general. Nevertheless, for two well-known IRK families—symmetric methods and collocation methods—we write $A$ as the sum of a diagonalizable plus a low-rank matrix. With this we devise a strategy using the parallel block-diagonal solution in the previous equation followed by a sequential matrix-equation solution to advance the method. We illustrate the idea with several numerical examples and discuss the extension to the more general nonlinear setting [3].

References

1. Durastante, F. and M. Mazza (2025). Stage-Parallel Implicit Runge–Kutta methods via low-rank matrix equation corrections. arXiv: 2505.17719 [math.NA]
2. Hairer, E., S. P. Nørsett, and G. Wanner (1993). Solving ordinary differential equations. I. Second. Vol. 8. Springer Series in Computational Mathematics. Berlin: Springer-Verlag, pp. xvi+528. ISBN: 3-540-56670-8.
3. Jay, L. O. (2000). “Inexact simplified Newton iterations for implicit Runge-Kutta methods”. In: SIAM J.
   Numer. Anal. 38.4, pp. 1369–1388. ISSN: 0036-1429,1095-7170. DOI: 10.1137/S0036142999360573.