In this dissertation, a fast numerical algorithm for computing the Markov renewal kernel via tight lower and upper bounds is developed. The Markov renewal kernel can then used to solve the well-known Markov renewal equation. Error analysis shows the numerically obtained bounds to be tight. The algorithm design and approximate solution process yield to a fast parallel solution methodology, which has speed-up behavior that is a linear function of the number of processors used. In particular, the parallel algorithm is of order O(k/2), when k is the number of processors used. |