Cutting-Edge Monte Carlo Framework: Novel “Walk on Equations” Algorithm for Linear Algebraic Systems
In this paper, we introduce the “Walk on Equations” (WE) Monte Carlo algorithm, a novel approach for solving linear algebraic systems. This algorithm shares similarities with the recently developed WE MC method by Ivan Dimov, Sylvain Maire, and Jean Michel Sellier. This method is particularly effect...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-01-01
|
| Series: | Axioms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2075-1680/13/1/53 |
| _version_ | 1797344642948136960 |
|---|---|
| author | Venelin Todorov Ivan Dimov |
| author_facet | Venelin Todorov Ivan Dimov |
| author_sort | Venelin Todorov |
| collection | DOAJ |
| description | In this paper, we introduce the “Walk on Equations” (WE) Monte Carlo algorithm, a novel approach for solving linear algebraic systems. This algorithm shares similarities with the recently developed WE MC method by Ivan Dimov, Sylvain Maire, and Jean Michel Sellier. This method is particularly effective for large matrices, both real- and complex-valued, and shows significant improvements over traditional methods. Our comprehensive comparison with the Gauss–Seidel method highlights the WE algorithm’s superior performance, especially in reducing relative errors within fewer iterations. We also introduce a unique dominancy number, which plays a crucial role in the algorithm’s efficiency. A pivotal outcome of our research is the convergence theorem we established for the WE algorithm, demonstrating its optimized performance through a balanced iteration matrix. Furthermore, we incorporated a sequential Monte Carlo method, enhancing the algorithm’s efficacy. The most-notable application of our algorithm is in solving a large system derived from a finite-element approximation in constructive mechanics, specifically for a beam structure problem. Our findings reveal that the proposed WE Monte Carlo algorithm, especially when combined with sequential MC, converges significantly faster than well-known deterministic iterative methods such as the Jacobi method. This enhanced convergence is more pronounced in larger matrices. Additionally, our comparative analysis with the preconditioned conjugate gradient (PCG) method shows that the WE MC method can outperform traditional methods for certain matrices. The introduction of a new random variable as an unbiased estimator of the solution vector and the analysis of the relative stochastic error structure further illustrate the potential of our novel algorithm in computational mathematics. |
| first_indexed | 2024-03-08T11:05:42Z |
| format | Article |
| id | doaj.art-c39013038e0c4df88ce553e771ffb9fd |
| institution | Directory Open Access Journal |
| issn | 2075-1680 |
| language | English |
| last_indexed | 2024-03-08T11:05:42Z |
| publishDate | 2024-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Axioms |
| spelling | doaj.art-c39013038e0c4df88ce553e771ffb9fd2024-01-26T15:03:52ZengMDPI AGAxioms2075-16802024-01-011315310.3390/axioms13010053Cutting-Edge Monte Carlo Framework: Novel “Walk on Equations” Algorithm for Linear Algebraic SystemsVenelin Todorov0Ivan Dimov1Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, Acad. G. Bonchev Str. Bl. 8, 1113 Sofia, BulgariaInstitute of Information and Communication Technologies, Bulgarian Academy of Sciences, Acad. G. Bonchev Str. Bl. 25A, 1113 Sofia, BulgariaIn this paper, we introduce the “Walk on Equations” (WE) Monte Carlo algorithm, a novel approach for solving linear algebraic systems. This algorithm shares similarities with the recently developed WE MC method by Ivan Dimov, Sylvain Maire, and Jean Michel Sellier. This method is particularly effective for large matrices, both real- and complex-valued, and shows significant improvements over traditional methods. Our comprehensive comparison with the Gauss–Seidel method highlights the WE algorithm’s superior performance, especially in reducing relative errors within fewer iterations. We also introduce a unique dominancy number, which plays a crucial role in the algorithm’s efficiency. A pivotal outcome of our research is the convergence theorem we established for the WE algorithm, demonstrating its optimized performance through a balanced iteration matrix. Furthermore, we incorporated a sequential Monte Carlo method, enhancing the algorithm’s efficacy. The most-notable application of our algorithm is in solving a large system derived from a finite-element approximation in constructive mechanics, specifically for a beam structure problem. Our findings reveal that the proposed WE Monte Carlo algorithm, especially when combined with sequential MC, converges significantly faster than well-known deterministic iterative methods such as the Jacobi method. This enhanced convergence is more pronounced in larger matrices. Additionally, our comparative analysis with the preconditioned conjugate gradient (PCG) method shows that the WE MC method can outperform traditional methods for certain matrices. The introduction of a new random variable as an unbiased estimator of the solution vector and the analysis of the relative stochastic error structure further illustrate the potential of our novel algorithm in computational mathematics.https://www.mdpi.com/2075-1680/13/1/53Monte Carlo methodsMarkov chainlinear algebraic systems |
| spellingShingle | Venelin Todorov Ivan Dimov Cutting-Edge Monte Carlo Framework: Novel “Walk on Equations” Algorithm for Linear Algebraic Systems Axioms Monte Carlo methods Markov chain linear algebraic systems |
| title | Cutting-Edge Monte Carlo Framework: Novel “Walk on Equations” Algorithm for Linear Algebraic Systems |
| title_full | Cutting-Edge Monte Carlo Framework: Novel “Walk on Equations” Algorithm for Linear Algebraic Systems |
| title_fullStr | Cutting-Edge Monte Carlo Framework: Novel “Walk on Equations” Algorithm for Linear Algebraic Systems |
| title_full_unstemmed | Cutting-Edge Monte Carlo Framework: Novel “Walk on Equations” Algorithm for Linear Algebraic Systems |
| title_short | Cutting-Edge Monte Carlo Framework: Novel “Walk on Equations” Algorithm for Linear Algebraic Systems |
| title_sort | cutting edge monte carlo framework novel walk on equations algorithm for linear algebraic systems |
| topic | Monte Carlo methods Markov chain linear algebraic systems |
| url | https://www.mdpi.com/2075-1680/13/1/53 |
| work_keys_str_mv | AT venelintodorov cuttingedgemontecarloframeworknovelwalkonequationsalgorithmforlinearalgebraicsystems AT ivandimov cuttingedgemontecarloframeworknovelwalkonequationsalgorithmforlinearalgebraicsystems |