# 1st-order linear ODE with tridiagonal matrix. Efficient solutions?

I have a 1st-rder linear ODE system where the system is characterized by $A$. Given an initial state $x_0$, I want the state at some later time $t$, efficiently.

$A$ happens to be a symmetric tridiagonal matrix where the coefficients are the same in each diagonal line.

$$A = \begin{pmatrix} a & b & 0 & 0 & ... \\ b & a & b & 0 & ... \\ 0 & b & a & b & ... \\ 0 & 0 & b & a & ... \\ \vdots &&\ddots&\ddots&\ddots\end{pmatrix}$$

I need to solve this for many different $A$'s and also many different $x_0$'s. The general solution to that is of course

$$x_t = e^{A t}x_0$$

One way to do this is to eigen-decompose $A$ into $A = F D F^\top$. Then the solution becomes

$$x_t = (F e^{D t} F^\top) x_0$$

Which is a little better because now the multiplication with $x_0$ is $O(n^2)$, but the eigen-decomposition is $O(n^3)$ still. But this doesn't take advantage of the constant values of $a$ and $b$ or the symmetric tridiagonal nature of $A$. So it seems like I should be able to do better.

-
There is a nice paper on numerical computation of matrix exponential: Nineteen Dubious Ways to Compute the Exponential of a Matrix by Moler & Van Loan (this is an update of the original paper, 25 years later). – Jean-Claude Arbaut Apr 30 '14 at 22:17

I'm not aware of any special algorithms for computing matrix exponentials for matrices with tridiagonal structure, but you probably shouldn't be solving your ODE by directly computing the matrix exponential anyway. Computing matrix exponentials is a tricky business. There's a famous paper by Cleve Moler (inventor of MATLAB) and Charles van Loan that you should check out titled "Nineteen Dubious Ways to Compute the Matrix Exponential". It goes through a variety of schemes people have tried over the years and discusses the problems with each one. That's not to say it can't be done but that it's something that needs to be handled with care.

The good news is that there are plenty of ways to numerically solve your ODE without having to resort to the matrix exponential, and these are all almost certainly more efficient. As an example, consider Euler's method. You want the solution at time $t = t_f$ to $x'(t) = Ax(t)$ with initial condition $x(0) = x_0$. Pick $K + 1$ equally-spaced time-points $0 = t_0 < t_1 < \cdots < t_K = t_f$, and let $h = (t_f - t_0)/K$ be the spacing between them. Let $x_k$ denote the approximation to the solution at time $t_k$. Euler's method is just the iteration $x_{k + 1} = x_k + hAx_k$.

Each step requires one matrix-vector multiply and one addition of two vectors. Since your matrix is tridiagonal, the matrix-vector multiply will be $O(3n)$, and the vector addition will be $O(n)$. With $K + 1$ steps, you're looking at an overall computational complexity of $O(nK)$. As far as accuracy goes, Euler's method converges at a rate of $O(h) = O(K^{-1})$, so if you double the number of points you use, you cut the error in half.

If you want something with better convergence properties than Euler's method, there are many other possibilities. Some things to search for are "Runge-Kutta methods" and "one-step methods." More sophisticated methods require more function-evaluations (matrix-vector multiplies, in this case) at each time step but can attain better accuracy with fewer time steps.

At any rate, there's no need to do an $O(n^3)$ eigenvalue computation if you don't want to!

-
I didn't read your answer, it looks like we have read the same article ;-) – Jean-Claude Arbaut Apr 30 '14 at 22:19

You are able to find a closed form expression, only depending on $a$ and $b$, for the the eigenvalues and respective eigenvectors of your matrix $A$. In fact, you can prove that, for $a \neq 0$, the eigenvalues of $A$ are given by:

$$\lambda_j=b+2a \cos(\frac{j\pi}{n+1}), \, j=1,...,n$$ and the respective eigenvectors are known to be:

$${{\bf{v}}_j} = \left[ {\begin{array}{*{20}{c}}{\sin \left( {\frac{{1j\pi }}{{n + 1}}} \right)}\\{\sin \left( {\frac{{2j\pi }}{{n + 1}}} \right)}\\ \vdots \\{\sin \left( {\frac{{nj\pi }}{{n + 1}}} \right)}\end{array}} \right], \, j=1,...,n$$

Thus you can very easily construct the matrices $F$ and $D$ in your decomposition. Also, since $D$ will always be diagonal, as the matrix $A$ is nonsingular, it's straightforward to compute $e^D$.

To get an idea how to get the expressions I mentioned see, for example:

Quick way of finding the eigenvalues and eigenvectors of the matrix $A=\operatorname{tridiag}_n(-1,\alpha,-1)$

-