On Monte Carlo Methods in Distributed Memory Systems

被引:0
|
作者
Ermakov, S. M. [1 ]
Trosinenko, A. V. [2 ]
机构
[1] St Petersburg State Univ, St Petersburg, Russia
[2] JSC Technol Aviat, St Petersburg, Russia
关键词
Monte Carlo method; parallel computation; asynchronous iterative method;
D O I
10.3103/S1063454116040051
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
The way for solving a system of linear algebraic equations (SLAEs) with computers with distributed memory is presented. It is assumed that there are M computing nodes, each of which has a limited fast memory, and communication between nodes takes considerable time. If the matrix elements and the right side vectors cannot be placed in their entirety in the one node memory, the problem of using equipment efficiently between the exchange, i.e., whether each node is able to use the available information to reduce the total residual, appears. The answer to this question is negative under general assumptions on the system's matrix and the example presented in the Appendix verifies this fact. We examine the case when the system is of sufficiently high order and it is reasonable to use the Monte Carlo method. In this case the matrix is divided between computing nodes on blocks of rows that do not overlap with the same partition into blocks of indices of rows and columns. We also consider a modification of the method of simple iteration based on this partition consisting of two nested iterative processes so that messaging between nodes takes place only in the outer iterations. This iterative process naturally results in a similar process, where the Monte Carlo method is used, and where it is not necessary to save a matrix's full copy at each computing node. The unbiased estimations of linear algebraic equations' solutions for the examined case are studied in the present paper. Under certain additional conditions imposed on the matrix, we prove the sufficient convergence conditions.
引用
收藏
页码:325 / 333
页数:9
相关论文
共 50 条
  • [31] Investigating distributed generation systems performance using Monte Carlo simulation
    El-Khattam, Walid
    Hegazy, Yasser
    Salama, Magdy
    2006 POWER ENGINEERING SOCIETY GENERAL MEETING, VOLS 1-9, 2006, : 2399 - 2399
  • [32] Capacity evaluation of MIMO systems by Monte-Carlo methods
    Wang, C
    Wu, SJ
    Zhang, LR
    Tao, XY
    PROCEEDINGS OF 2003 INTERNATIONAL CONFERENCE ON NEURAL NETWORKS & SIGNAL PROCESSING, PROCEEDINGS, VOLS 1 AND 2, 2003, : 1464 - 1466
  • [33] New sequential Monte Carlo methods for nonlinear dynamic systems
    Guo, D
    Wang, XD
    Chen, R
    STATISTICS AND COMPUTING, 2005, 15 (02) : 135 - 147
  • [34] Quantum Monte Carlo methods for rovibrational states of molecular systems
    Blume, D
    Lewerenz, M
    Whaley, KB
    JOURNAL OF CHEMICAL PHYSICS, 1997, 107 (21): : 9067 - 9078
  • [35] Asymptotic complexity of Monte Carlo methods for solving linear systems
    Danilov, DL
    Ermakov, SM
    Halton, JH
    JOURNAL OF STATISTICAL PLANNING AND INFERENCE, 2000, 85 (1-2) : 5 - 18
  • [36] MONTE-CARLO SIMULATION METHODS FOR ENGINEERED WOOD SYSTEMS
    TAYLOR, SE
    TRICHE, MH
    BENDER, DA
    WOESTE, FE
    FOREST PRODUCTS JOURNAL, 1995, 45 (7-8) : 43 - 50
  • [37] Quantum Monte Carlo methods for strongly correlated electron systems
    Zhang, SW
    THEORETICAL METHODS FOR STRONGLY CORRELATED ELECTRONS, 2004, : 39 - 74
  • [38] New sequential Monte Carlo methods for nonlinear dynamic systems
    Dong Guo
    Xiaodong Wang
    Rong Chen
    Statistics and Computing, 2005, 15 : 135 - 147
  • [39] Analytic approach & Monte Carlo methods for realistic systems analysis
    Dubi, A
    MATHEMATICS AND COMPUTERS IN SIMULATION, 1998, 47 (2-5) : 243 - 269
  • [40] On multilevel Monte Carlo methods for deterministic and uncertain hyperbolic systems
    Hu, Junpeng
    Jin, Shi
    Li, Jinglai
    Zhang, Lei
    JOURNAL OF COMPUTATIONAL PHYSICS, 2023, 475