Multiway Monte Carlo method for linear systems

DOI10.1137/18M121527XMaRDI QIDQ5243527zbMATH OpenOpenAlexFDO

Authors Tao Wu, David F. Gleich

Publication date 18 November 2019

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.04361

zbMATH Keywords

linear solverMarkov chain Monte Carlorandomized algorithm

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40) Computational methods for sparse matrices (65F50) Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Abstract: We study the Monte Carlo method for solving a linear system of the form $x=Hx+b$. A sufficient condition for the method to work is $|H|<1$, which greatly limits the usability of this method. We improve this condition by proposing a new multi-way Markov random walk, which is a generalization of the standard Markov random walk. Under our new framework we prove that the necessary and sufficient condition for our method to work is the spectral radius $ho(H^{+})<1$, which is a weaker requirement than $|H|<1$. In addition to solving more problems, our new method can work faster than the standard algorithm. In numerical experiments on both synthetic and real world matrices, we demonstrate the effectiveness of our new method.

Recommendations

• Convergence analysis of Markov chain Monte Carlo linear solvers using Ulam-von Neumann algorithm
• Solving Linear Equations by Monte Carlo Simulation
• Monte Carlo methods for systems of linear equation
• scientific article; zbMATH DE number 5606150
• A new \textit{walk on equations} Monte Carlo method for solving systems of linear algebraic equations

Cites work

• A Monte Carlo method for solving unsteady adjoint equations
• A Monte Carlo synthetic-acceleration method for solving the thermal radiation diffusion equation
• A new \textit{walk on equations} Monte Carlo method for solving systems of linear algebraic equations
• A new iterative Monte Carlo approach for inverse matrix problem
• A Note on the Inversion of Matrices by Random Walks
• A parallel implementation of the direct simulation Monte Carlo method
• Analysis of Monte Carlo accelerated iterative methods for sparse linear systems.
• Blendenpik: Supercharging LAPACK's Least-Squares Solver
• Computational Science – ICCS 2005
• Convergence analysis of Markov chain Monte Carlo linear solvers using Ulam-von Neumann algorithm
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
• Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• scientific article; zbMATH DE number 2087126 (Why is no real title available?)
• Monte Carlo linear solvers with non-diagonal splitting
• Monte Carlo Methods in PageRank Computation: When One Iteration is Sufficient
• Parallel resolvent Monte Carlo algorithms for linear algebra problems
• Robustness and applicability of Markov chain Monte Carlo algorithms for eigenvalue problems
• Scalar and parallel optimized implementation of the direct simulation Monte Carlo method
• Sequential Monto Carlo techniques for the solution of linear systems
• Sparsified Randomization Algorithms for large systems of linear equations and a new version of the Random Walk on Boundary method
• The University of Florida sparse matrix collection

Cited in

(5)

• Solving systems of linear equations with relaxed Monte Carlo method
• Solving systems of equations with multi-stage Monte Carlo optimization
• scientific article; zbMATH DE number 5198379 (Why is no real title available?)
• scientific article; zbMATH DE number 6468196 (Why is no real title available?)
• Regenerative Ulam-von Neumann algorithm: an innovative Markov chain Monte Carlo method for matrix inversion

Describes a project that uses

Uses Software

• Harwell-Boeing sparse matrix collection
• SparseMatrix
• Blendenpik
• MONACO

This page was built for publication: Multiway Monte Carlo method for linear systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5243527)