\documentclass[format=acmsmall, review=true]{acmart}

\usepackage{alltt}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage[strings]{underscore}
\usepackage{wrapfig}

% Metadata Information
\acmJournal{TOMS}
\acmVolume{0}
\acmNumber{0}
\acmArticle{0}
\acmYear{2020}
\acmMonth{0}
\copyrightyear{2020}
%\acmArticleSeq{9}

% Copyright
\setcopyright{acmcopyright}
%\setcopyright{acmlicensed}
%\setcopyright{rightsretained}
%\setcopyright{usgov}
%\setcopyright{usgovmixed}
%\setcopyright{cagov}
%\setcopyright{cagovmixed}

% DOI
\acmDOI{0000001.0000001}

% Paper history
\received{December 2020}

\citestyle{acmnumeric}

\begin{document}

\title{Remark on Algorithm 982: Explicit solutions of triangular systems
of first-order linear initial-value ordinary differential equations with
constant coefficients}

\author{W. Van Snyder}
\streetaddress{2229 Shields Street}
\city{La Crescenta}
\state{CA}
\country{USA}
\makeatletter
\email{van.snyder@sbcglobal.net}
\thanks{Author's e-mail address: van.snyder@sbcglobal.net}
\makeatother

\begin{abstract}

  \emph{Algorithm 982: Explicit solutions of triangular systems of
  first-order linear initial-value ordinary differential equations with
  constant coefficients} provides an explicit solution for an homogeneous
  system, and a brief description of how to compute a solution for the
  inhomogeneous case. The method described is not directly useful if the
  coefficient matrix is singular. This remark explains more completely how
  to compute the solution for the inhomogeneous case, and for the singular
  coefficient matrix case.

\end{abstract}

\ccsdesc[500]{Mathematics of computing~Solvers}
\ccsdesc[500]{Mathematics of computing~Ordinary differential equations}

\terms{Mathematics of computing, Mathematical software, Solvers,
       Mathematical analysis, Differential equations, 
       Ordinary differential equations}

\keywords{ordinary differential equations, initial value problem,
          first order, constant coefficient, triangular system, explicit
          solution}

\maketitle

The formal solution for the homogeneous system

\newcommand{\D}{\text{d}}
\begin{equation}\label{one}
\frac{\D \mathbf{N}(t)}{\D t} = \mathbf{A}\, \mathbf{N}(t)
\end{equation}

{\parindent 0pt in which $\mathbf{A}$ is a constant triangular matrix, is}

\begin{equation}\label{two}
\mathbf{N}(t) = \exp(\mathbf{A}\,t)\, \mathbf{N}(0) \,.
\end{equation}

Because this requires to compute the exponential of the matrix
$\mathbf{A}\,t$, Algorithm 982 \cite{Algorithm-982} provides an explicit
solution

\begin{equation}\label{six}
N_i(t) = N_i(0)\, e^{a_{ii} t} + \sum_{j=1}^{i-1} z_{ij}
 \left( N_j(t) - N_j(0) \, e^{a_{ii} t} \right)
\end{equation}

{\parindent 0pt where the constant coefficients $z_{ij}$ are calculated
using the recurrence}

\begin{equation}\begin{split}\label{seven}
z_{ij} = \,& 0 \text{ if } i \leq j \text{, and}\\
z_{ij} = \,& \frac{a_{ij} - \sum_{k=1}^{i-j-1} a_{i-k,j} \, z_{i,i-k}}
              {a_{jj}-a_{ii}} \text{ if } i > j \,.
\end{split}\end{equation}

This solution requires to compute the exponential of only the diagonal
elements of $\mathbf{A} t$. This is, of course, equivalent to computing

\begin{equation}
\mathbf{N}(t) =
\exp(\mathbf{A}\,t) \, \mathbf{N}(0) = \mathbf{M}\,\exp(\mathbf{\Lambda}\,t) \,\,
                      \mathbf{M}^{-1} \, \mathbf{N}(0) \,,
\end{equation}

{\parindent 0pt where $\mathbf{M}$ is the modal matrix of $\mathbf{A}$,
and $\mathbf{\Lambda}$ is the diagonal matrix consisting of the
eigenvalues of $\mathbf{A}$, which are the diagonal elements of
$\mathbf{A}$. Computing $\exp(\mathbf{\Lambda}\,t)$ requires to compute
only the exponential of the diagonal elements of $\mathbf{A} t$. But this
method does not require to compute and invert the modal matrix. It is well
known, and obvious from Equation (\ref{seven}), that this method does not
work if $\mathbf{A}$ is defective.}

The solution given in \cite{Algorithm-982} for an inhogeneous equation

\begin{equation}\label{five}
\frac{\D \mathbf{N}(t)}{\D t} = \mathbf{A} ( \mathbf{N}(t) + \mathbf{B} ) 
\end{equation}

{\parindent 0pt with $\mathbf{B}$ constant is}

\begin{equation}\label{inhomogeneous-1}
\mathbf{N}(t) = \exp( \mathbf{A} t )\, \mathbf{\hat N}(0) - \mathbf{B} \,,
\end{equation}

{\parindent 0pt where $\mathbf{\hat N}(0) = \mathbf{N}(0)+\mathbf{B}$. For
a system of the form}

\begin{equation}
\frac{\D \mathbf{N}(t)}{\D t} = \mathbf{A} \mathbf{N}(t) + \mathbf{C}
\end{equation}

{\parindent 0pt the general solution if $\mathbf{A}$ is nonsingular is}

\begin{equation}
\mathbf{N}(t) = \exp( \mathbf{A} t ) \,
  ( \mathbf{N}(0) + \mathbf{A}^{-1} \mathbf{C} ) -
  \mathbf{A}^{-1} \mathbf{C}
\end{equation}

{\parindent 0pt where $\mathbf{B}$ in Equations (\ref{five}) and
(\ref{inhomogeneous-1}) has been replaced by $\mathbf{A}^{-1} \mathbf{C}$.
But this is not useful if $\mathbf{A}$ is singular. Singular systems arise
when modeling nuclear decay if nonradioactive daughter isotopes are
included.}

Assume that if $\mathbf{A}$ is singular, it has been permuted to a form
that has a leading nonsingular triangle $\mathbf{A}_m$ with $m$ rows and
columns, i.e., $a_{ii} \neq 0$ for $i \leq m$, and $a_{ii} = 0$ for $i >
m$. The solutions for the first $m$ equations $\mathbf{N}_m$ are given by
the first $m$ rows of Equation (\ref{inhomogeneous-1}), \emph{viz.}

\begin{equation}\label{inhomogeneous-2}
\mathbf{N}_m(t) = \exp( \mathbf{A}_m t )\,
                  \mathbf{\hat N}_m(0) - \mathbf{B}_m \,.
\end{equation}

{\parindent 0pt where $\mathbf{B}_m = \mathbf{A}_m^{-1} \mathbf{C}_m$.}

The first term in Equation (\ref{inhomogeneous-2}) is of the same form as
the formal solution given by Equation (\ref{two}), and is therefore given
by the first $m$ solutions in Equation (\ref{six}), with $\mathbf{N}_m(t)$
replaced by $\mathbf{\hat N}_m(t)$. Equation (\ref{six}) becomes

\begin{equation}\label{six-inhomogeneous}
N_i(t) = \hat N_i(0)\, e^{a_{ii} t} + \sum_{j=1}^{i-1} z_{ij}
 \left( \hat N_j(t) - \hat N_j(0) \, e^{a_{ii} t} \right) - B_i \,,\, i\leq m
 \,.
\end{equation}

If $\mathbf{A}$ is singular, remaining equations are of the form

\begin{equation}\label{ten}
\frac{\D N_k(t)}{\D t} = \sum_{l=1}^{k-1} a_{kl}\,N_l(t) + C_k\,,\, k > m\,,
\end{equation}

{\parindent 0pt for which the solutions are simply}

\begin{equation}\label{eleven}
N_k(t) = \sum_{l=1}^{k-1} a_{kl}\int_0^t N_l(t)\,\D t +
         C_k\,t  + N_k(0) \,,\, k > m \,,
\end{equation}

{\parindent 0pt  because the right-hand sides do not depend upon $N_k(t)$.
The $C_k\,t$ term in Equation (\ref{eleven}) does not appear in
Equation (\ref{six-inhomogeneous}). Therefore, it is clear that Equation
(\ref{six-inhomogeneous}) does not produce a correct solution for $k>m$ .}

From Equation (\ref{six-inhomogeneous}),

\begin{equation}\label{twelve}
\int_0^t N_l(t)\, \D t = \hat N_l(0) \, \frac{e^{a_{ll} t}-1}{a_{ll}} +
  \sum_{j=1}^{l-1} z_{lj} \left( \int_0^t \hat N_j(t)\,\D t -
  \hat N_j(0) \, \frac{e^{a_{ll} t}-1}{a_{ll}} \right) - B_l\,t \,,\, l \leq m \,.
\end{equation}

% Be careful fiddling these widths. If you get them wrong, the plain-text
% sentence between the two subroutine interfaces will be put into the wrap.
\begin{wrapfigure}{r}{0.55\textwidth}
\vspace*{-\baselineskip}
\begin{centering}
\includegraphics[width=0.47\textwidth,keepaspectratio]{Remark-1}\\
\caption{\parbox[c]{0.47\textwidth}{
Shape of nondefective matrix for \\
which this method works}}
\end{centering}
\end{wrapfigure}

\vspace*{3pt}

Algorithm 982 was motivated by study of nuclear decay. If isotope $j$ does
not decay, it cannot contribute to accumulation of isotope $i$. Therefore,
if $a_{jj} =0$, then  $a_{ij} = 0$ for $i > j$, it is not necessary to
compute $\int_0^t N_l(t)\, \D t$ for $l > m$, and the upper bound for the
summations in Equations (\ref{ten}) and (\ref{eleven}) is $m$ instead of
$k-1$.

In equations where $a_{jj} = 0$ and $a_{ij} \neq 0$ for $i>j$, integrals
of Equation (\ref{eleven}) are required in the right-hand side of Equation
(\ref{eleven}). This results in multi-dimensional quadratures, which can be
reduced to one dimension using integration by parts. The provided software
does not compute solutions for this case.

The {\tt Compute\_Solution} subroutine provided with Algorithm 982 has
been revised to allow to provide $\mathbf{B}$:

% The kludge using tabbing is here because neither verbatim nor alltt
% lined up the text in pdflatex. Using alltt worked fine in xdvi, and
% below.
{\tt\begin{tabbing}\hspace*{\parindent}\=
  su\=br\=outine Compute_Solution ( T, A, \=Z, N0\=, N_T, B ) \\
\>\>re\>al(rk), intent(in) :: T        \>! Independent variable\\
\>\>re\>al(rk), intent(in) :: A(:,:)   \>! Coefficient matrix for ODE\\
\>\>re\>al(rk), intent(in) :: Z(:,:)   \>! Coefficient matrix solutions\\
\>\>re\>al(rk), intent(in) :: N0(:)    \>! Initial condition\\
\>\>re\>al(rk), intent(out) :: N_T(:)  \>! Solution N(T)\\
\>\>re\>al(rk), intent(in), optional :: B(:)\>\>! For inhomogeneous equations.\\
\>\>\>! Let M be the index in A of the last nonzero diagonal element.\\
\>\>\>! Then B(1:m) is B in    d N(t)/d t = A ( N(t) + B )\\
\>\>\>! and B(m+1:) is C in    d N(t)/d t = A N(t) + C. Remember that here,\\
\>\>\>! columns of A after M are zero, so this is just a quadrature.\\
\>\>\>! Backsolve_A_C_B can compute B(1:m) if all you have is C.\\
\>end subroutine Compute_Solution
\end{tabbing}}

% \begin{alltt}
%   subroutine Compute_Solution_* ( T, A, Z, N0, N_T, B )
%     real(rk), intent(in) :: T          ! Independent variable
%     real(rk), intent(in) :: A(:,:)     ! Coefficient matrix for ODE
%     real(rk), intent(in) :: Z(:,:)     ! Coefficient matrix solutions
%     real(rk), intent(in) :: N0(:)      ! Initial condition
%     real(rk), intent(out) :: N_T(:)    ! Solution N(T)
%     real(rk), intent(in), optional :: B(:)  ! For inhomogeneous equations.
%       ! Let M be the index in A of the last nonzero diagonal element.
%       ! Then B(1:m) is B in    d N(t)/d t = A ( N(t) + B )
%       ! and B(m+1:) is C in    d N(t)/d t = A N(t) + C. Remember that here,
%       ! columns of A after M are zero, so this is just a quadrature.
%       ! Backsolve_A_C_B can compute B(1:m) if all you have is C.
%   end subroutine Compute_Solution
% \end{alltt}

Because the new argument {\tt B} is optional, the revised procedure can be
used in software that solves the homogeneous case by simply omitting the
{\tt B} argument, and used in existing software that used the original
version, without adding the {\tt B} argument.

As a convenience, a generic subroutine is included to solve $A_m B_m =
C_m$:

\begin{alltt}
  subroutine Solve_A_C_B ( A, C, B, Status )
    real(rk), intent(in) :: A(:,:) ! Lower triangular coefficient matrix
    real(rk), intent(in) :: C(:)   ! Right hand side of A B = C
    real(rk), intent(out) :: B(:)  ! Solution of A_m B_m = C_m, where M is the
                                   ! index of the last nonzero diagonal in A
    integer, intent(out) :: Status ! M, the index of the last nonzero diagonal
                                   ! in A, if there are no nonzeroes after M,
                                   ! else the negative of the index of the
                                   ! first column after M containing any
                                   ! nonzero element.
  end subroutine Solve_A_C_B
\end{alltt}

The named constant {\tt RK} has the value {\tt KIND(0.0d0)} in the double
precision specific subroutines, and {\tt KIND(0.0e0)} in the single
precision specific subroutines.

\bibliographystyle{acmsmall}

\bibliography{Remark}

\end{document}
