Computing the fundamental matrix for a nonirreducible Markov chain

We present a new partitioning algorithm for computing the fundamental matrix for a nonirreducible Markov chain. The algorithm, called matrix reduction, has three steps: (1) augmentation; (2) stochastic complementation; and (3) a backward pass. We show that matrix reduction is equivalent to performing matrix inversion with Gaussian elimination to compute the fundamental matrix. We execute matrix reduction without subtractions to enhance numerical stability. We apply matrix reduction to a small example problem modeling patient flow in a hospital.