A new iterative Monte Carlo approach for inverse matrix problem. (English) Zbl 0936.65025
The authors present new iterative Monte Carlo algorithms for the inverse matrix problem. The new algorithms are based on special choice of the iteration parameters which allow to control the convergence. They are applicable in the cases when not very accurate solution is needed and in finding special preconditioning matrices in the preconditioned iterative methods. The systematic (truncation) error which depends on the number of iterations and the stochastic (probable) error which depends on the probabilistic nature of the Monte Carlo methods are studied. The algorithms are well parallelized.
Reviewer: K.Georgiev (Sofia)
Keywords:
Monte Carlo algorithms; iterative methods; Markov chain; inverse matrix problem; convergence control; truncation error; stochastic error; preconditioningReferences:
| [1] | Andreev, A.; Dimov, T., Lumped mass approximation for the mixed finite element method, (Advances in Numerical Methods and Applications — \(O(h^3)\). Advances in Numerical Methods and Applications — \(O(h^3)\), Proc.3 Int. Conf. on Numerical Methods and Applications (21-26 August 1994), World Scientific: World Scientific Singapore), 11-18, Sofia · Zbl 0812.65093 |
| [2] | Axelsson, O., Iterative Solution Methods (1994), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0795.65014 |
| [3] | Csanky, L., Fast parallel matrix inversion algorithms, SIAM J. Comput., 5, 4, 618-623 (1976) · Zbl 0353.68063 |
| [4] | Curtiss, J. H., Monte Carlo methods for the iteration of linear operators, J. Math Phys., 32, 4, 209-232 (1954) · Zbl 0055.11301 |
| [5] | Dimov, I.; Tonev, O., Random walk on distant mesh points Monte Carlo methods, J. Statist. Phys., 70, 5/6, 1333-1342 (1993) · Zbl 1081.82579 |
| [6] | Dimov, I.; Tonev, O., Monte Carlo algorithms: performance analysis for some computer architectures, J. Comput. Appl. Math., 48, 253-277 (1993) · Zbl 0802.68020 |
| [7] | Dimov, I. T.; Karaivanova, A. N., Iterative Monte Carlo algorithms for linear algebra problems, (First Workshop on Numerical Analysis and Applications. First Workshop on Numerical Analysis and Applications, Rousse, Bulgaria. First Workshop on Numerical Analysis and Applications. First Workshop on Numerical Analysis and Applications, Rousse, Bulgaria, Numerical Analysis and Its Applications, Springer Lecture Notes in Computer Science (June 24-27, 1996)), 150-160, Ser. 1196 |
| [8] | Ermakov, S. M.; Mikhailov, G. A., Statistical Modeling (1982), Nauka: Nauka Moscow · Zbl 0599.65001 |
| [9] | Halton, J. H., Sequential Monte Carlo techniques for the solution of linear systems, (TR 92-033 (1992), University of North Carolina at Chapel Hill, Department of Computer Science), 46 · Zbl 0479.90079 |
| [10] | Hyafil, L.; Kung, H. T., Parallel algorithms for solving triangular linear systems with small parallelism (Dec.,, 1974 1974), Dept. of Comp. Sci., Carnegie- Mellon Univ |
| [11] | Kolotilina, L. Yu.; Yeremin, A. Yu., Factorized sparse approximate inverse preconditionings I. Theory, SIAM J. Matrix Anal. Appl., 14, 1, 45-58 (1993) · Zbl 0767.65037 |
| [12] | Megson, G.; Aleksandrov, V.; Dimov, I., Systolic matrix inversion using a Monte Carlo method, J. of parallel Algorithms Appl., 3, 3/4, 311-330 (1994) · Zbl 1049.65541 |
| [13] | Metropolis, N.; Ulam, S., The Monte Carlo method, J. Amer. Statist. Assoc., 44, 335-341 (1949) · Zbl 0033.28807 |
| [14] | Roberts, J. E.; Thomas, J. M., Mixed and hybrid methods, (Ciarlet, P. G.; Lions, J. L., Handbook of Numerical Analysis, 2 (1991), North-Holland: North-Holland Amsterdam), 523-639 · Zbl 0875.65090 |
| [15] | Sobol, I. M., Monte Carlo numerical methods (1973), Nauka: Nauka Moscow · Zbl 0289.65001 |
| [16] | Spanier, J.; Gelberd, E. M., Monte Carlo Principles and Neutron Transport problems (1969), Addison-Wesley Publishing Company: Addison-Wesley Publishing Company Reading, MA · Zbl 0244.62004 |
| [17] | Westlake, J. R., A Handbook of Numerical Matrix Inversion and Solution of Linear Equations (1968), Wiley: Wiley New York, London, Sydney · Zbl 0155.19901 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
