Structured Markov Chains in Applied Probability and Numerical Analysis

About thirty years ago, Quasi-Birth-and-Death processes and Skip-Free Markov chains came to the attention of applied probabilists. One of their prominent features is that their analysis requires the resolution of nonlinear equations, involving matrix-polynomial or matrix power series. At first, these were tackled 'in-house' and very soon several algorithms appeared which had their justification grounded, to a large extent, in probabilistic thinking. Soon, these equations caught the attention of numerical analysts who brought to bear their own special way of thinking about such problems and, not surprisingly, obtained improved algorithms in terms of convergence speed or numerical accuracy. The interaction between the two lines of approach are very exciting and this is an attempt to illustrate how the one meshes into the other.