  This paper presents an extension of the classical Ulan-von Neumann Markov
chain Monte-Carlo algorithm for the computation of the matrix inverse. The
algorithm presented in this paper, termed as \emph{regenerative Ulam-von
Neumann algorithm}, utilizes the regenerative structure of classical,
non-truncated Neumann series defined by a non-singular matrix and produces an
unbiased estimator of the matrix inverse. Furthermore, the accuracy of the
proposed algorithm depends on a single parameter that controls the total number
of Markov transitions simulated thus avoiding the challenge of balancing
between the total number of Markov chain replications and its corresponding
length as in the classical Ulam-von Neumann algorithm. To efficiently utilize
the Markov chain transition samples in the calculation of the regenerative
quantities, the proposed algorithm quantifies automatically the contribution of
each Markov transition to all regenerative quantities by a carefully designed
updating scheme that utilized three separate matrices containing the current
weights, total weights, and regenerative cycle count, respectively. A
probabilistic analysis of the performance of the algorithm, including the
variance of the estimator, is provided. Finally, numerical experiments verify
the qualitative effectiveness of the proposed scheme.
