REGENERATIVE ULAM-VON NEUMANN ALGORITHM: AN INNOVATIVE MARKOV CHAIN MONTE CARLO METHOD FOR MATRIX INVERSION

This paper presents a regenerative variant of the classical Ulam-von Neumann Markov chain Monte Carlo algorithm for the approximation of the matrix inverse. The algorithm presented in this paper, termed regenerative Ulam-von Neumann algorithm, utilizes the regenerative structure of classical, nontruncated Neumann series defined by a nonsingular matrix and produces an estimator of the matrix inverse via ratios of unbiased estimators of the regenerative quantities. The accuracy of the proposed algorithm depends on a single parameter that controls the total number of simulated Markov transitions, thus avoiding the challenge of balancing between the total number of Markov chain replications and their length as in the classical Ulam-von Neumann algorithm. To efficiently utilize Markov chain transition samples in the calculation of the regenerative variables, the proposed algorithm automatically quantifies the contribution of each Markov transition to all regenerative quantities by a carefully designed updating scheme that utilizes 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 effectiveness of the proposed scheme.