david/PRK-ind

Given a partitioned Runge-Kutta method defined by coefficients \(b_k, A_k\), and \(c\), a stage-by-stage error analysis leads one to consider the functions

\[r(Z)^T = [r_1(Z),\dots,r_s(Z)] = \left(\sum_k b^T_k Z_k\right) \left(I - \sum_k A_k Z_k\right)^{-1}\]

Here \(Z_k = \Delta t L_k\). The point of this note is to show that the various \(r_j(Z)\) are linearly independent under some reasonable assumptions. For simplicity, we restrict our attention to explicit methods.

We first define an explicit partitioned Runge-Kutta method to be irreducible if the following condition holds:

\[\text{For each } i\in [1,2,\dots,s] \text{ there exists } k_i \in [1,2,\dots,r] \text{ such that } (A_{k_i})_{i,i-1} \ne 0.\]

\[\text{For each } i \in [1,2,\dots,s] \text{ there exists } j_i \in [1,2,\dots,r] \text{ such that } (b_{j_i})_i \ne 0.\]

The first condition states that the sum of the incidence matrices of the \(A_k\) has no zero entries on its first subdiagonal. The second condition is the same requirement, but with respect to the vector \(b\). We remark that a weaker definition of reducibility might be sufficient to prove a result like that below, but the definition given is convenient and is satisfied by all practical methods we know of.

We further suppose that \[\begin{equation} \label{prod} \prod_{i=1}^s L_{k_i} \ne 0 \end{equation}\] for all choices of sequences \(k_i \in [1,2,\dots,r]\). Condition \(\eqref{prod}\) implies that the space of multivariate polynomials in \(\{Z_1,Z_2,\dots,Z_r\}\) of degree \(j\) contains some elements that don’t belong to the corresponding space of polynomials of degree \(j-1\).

Given an explicit irreducible method and matrices \(L_k\) satisfying \(\eqref{prod}\), the matrices \(r_j(Z)\) are non-zero and linearly independent.

We prove this statement by showing that \(r_j(Z)\) is a polynomial of degree exactly \(s-j+1\).

First we rewrite \(r(Z)\) using an identity and the fact that \(A_k^s = 0\). Let \[A\cdot Z = \sum_k A_k Z_k.\] Then \[r(Z)^T = \left(\sum_k b^T_k Z_k\right) \left(I + A\cdot Z + (A\cdot Z)^2 + \cdots + (A\cdot Z)^{s-1}\right).\] Next observe that, by the assumptions of explicitness and irreducibility, the first \(s-j\) columns of \(A^j\) are non-zero while the remainder are identically zero. Furthermore, the \((s,j)\) entry of \((A\cdot Z)^j\) is a polynomial of degree \(s-j\). Finally, \(r_j(Z)\) is obtained by multiplying the \(j\)th column of the right-side matrix by \(b^T_k Z_k\).