Результаты поиска по 'Markov chain Monte Carlo':
Найдено статей: 3
  1. Editor’s note
    Computer Research and Modeling, 2023, v. 15, no. 2, pp. 229-233
  2. Prokhorov I.V., Zhuplev A.S.
    On the efficiency of the maximum cross section method in radiation transport theory
    Computer Research and Modeling, 2013, v. 5, no. 4, pp. 573-582

    We consider two versions of the maximum cross section method for the solutions of the stationary equation of radiative transfer in dimensional inhomogeneous medium. Both are based on the application Monte-Carlo method to the summation of the Neumann series for the solution transport equation. First modification is traditional and second is based on the use of branching Markov chains. We carried out numerical comparison of these algorithms.

    Keywords: radiation transfer equation, Monte-Carlo algorithms, maximum cross section method.
    Views (last year): 4. Citations: 2 (RSCI).
  3. Skachkov D.A., Gladyshev S.I., Raigorodsky A.M.
    Experimental comparison of PageRank vector calculation algorithms
    Computer Research and Modeling, 2023, v. 15, no. 2, pp. 369-379

    Finding PageRank vector is of great scientific and practical interest due to its applicability to modern search engines. Despite the fact that this problem is reduced to finding the eigenvector of the stochastic matrix $P$, the need for new algorithms is justified by a large size of the input data. To achieve no more than linear execution time, various randomized methods have been proposed, returning the expected result only with some probability close enough to one. We will consider two of them by reducing the problem of calculating the PageRank vector to the problem of finding equilibrium in an antagonistic matrix game, which is then solved using the Grigoriadis – Khachiyan algorithm. This implementation works effectively under the assumption of sparsity of the input matrix. As far as we know, there are no successful implementations of neither the Grigoriadis – Khachiyan algorithm nor its application to the task of calculating the PageRank vector. The purpose of this paper is to fill this gap. The article describes an algorithm giving pseudocode and some details of the implementation. In addition, it discusses another randomized method of calculating the PageRank vector, namely, Markov chain Monte Carlo (MCMC), in order to compare the results of these algorithms on matrices with different values of the spectral gap. The latter is of particular interest, since the magnitude of the spectral gap strongly affects the convergence rate of MCMC and does not affect the other two approaches at all. The comparison was carried out on two types of generated graphs: chains and $d$-dimensional cubes. The experiments, as predicted by the theory, demonstrated the effectiveness of the Grigoriadis – Khachiyan algorithm in comparison with MCMC for sparse graphs with a small spectral gap value. The written code is publicly available, so everyone can reproduce the results themselves or use this implementation for their own needs. The work has a purely practical orientation, no theoretical results were obtained.

    Keywords: Grigoriadis – Khachiyan, Markov chain Monte Carlo, PageRank.

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"

Copyright © 2009–2024 Institute of Computer Science