Fast, but approximate, solutions to linear algebra problems have many potential applications, such as in graph partitioning, pre-conditioning, information retrieval, etc. Monte Carlo techniques appear attractive for such needs. While Monte Carlo linear solvers have a long history, their application has been limited due to slow convergence. Despite the development of techniques to improve their accuracy, current methods suffer from the drawback that they are stochastic realizations of inherently poor iterative methods. The reason for such choices is the need for efficient Monte Carlo implementation, which has restricted the splittings that are considered. However, in this paper we demonstrate that such restrictions are not necessarily required, and that efficient Monte Carlo implementations are possible even with splittings that do not appear amenable to it.
展开▼
机译：快速但近似，线性代数问题的解决方案具有许多潜在的应用，例如在图形分区，预处理，信息检索等中。蒙特卡罗技术对于这些需求看起来具有吸引力。虽然Monte Carlo Linear Solvers历史悠久，但由于收敛缓慢，它们的应用受到限制。尽管技术开发了提高其准确性的技术，但目前的方法遭受了缺点，即它们是随机迭代方法的随机实现。此类选择的原因是需要有效的蒙特卡罗实现，这限制了所考虑的分裂。然而，在本文中，我们证明不一定需要这种限制，即使与它没有均匀的分裂器，也可以获得有效的蒙特卡罗实现。
展开▼
