A note on the efficient implementation of implicit methods for ODEs (Q1379016)

The use of implicit methods such as implicit Runge-Kutta methods for the solution of ordinary differential equations (ODEs) requires the solution of systems of nonlinear algebraic equations of dimension \(sm\), where \(m\) is the size of the differential problem \[ y'= f(t,y),\quad y(t_0)= y_0\in\mathbb{R}^m.\tag{1} \] The system of algebraic equations has the form \[ F(y):= y- h(C\otimes I_m)f- g(y_0)= 0,\tag{2} \] where \(h\) is the stepsize, \(C\) is a full \((s,s)\)-matrix, \(I_m\) is the identity matrix of size \(m\), \(g:\mathbb{R}^m\to \mathbb{R}^{sm}\) is a known function and \(y= (y_1,\dots, y_s)^T\), \(f= (f_1,\dots, f_s)^T\), \(f_i= f(t_i, y_i)\) are the vectors with the unknown approximations to the solution at the grid points \(t_1,\dots, t_s\) when an implicit Runge-Kutta method with \(s\) stages is used. Usually the problem (2) is solved by using the modified Newton iteration \[ (I- hC\otimes J_0)\Delta y_i= F(y_{i-1}),\quad i= 1,2,\dots,\tag{3} \] where \(J_0\) is the Jacobian of the function \(f\) evaluated at \((t_0, y_0)\). The authors discuss a different approach using an inner iterative procedure for each outer iteration in (3). One such inner-outer iteration scheme is of the form \[ (I- hL\otimes J_0)\Delta y^{(j)}_i= (h(C- L)\otimes J_0)\Delta y_i^{(j- 1)}- F(y_{i- 1}),\quad j= 1,\dots,\mu,\tag{4} \] here \(\mu\) is a suitable parameter and the matrix \(L\) is obtained by the \(LU\) factorization of the matrix \(C\), where \(U\) has unit diagonal entries. The authors show that if all the entires \(l_i\) (the diagonal entries of the matrix \(L\)) are equal, the leading term in the arithmetic complexity is reduced from \({2\over 3}\cdot s\cdot m^3\) to \({2\over 3}\cdot m^3\).