IDEAS home Printed from https://ideas.repec.org/a/bpj/mcmeap/v15y2009i3p257-284n5.html
   My bibliography  Save this article

Sparsified Randomization Algorithms for large systems of linear equations and a new version of the Random Walk on Boundary method

Author

Listed:
  • Sabelfeld K.

    (Institute of Computational Mathematics and Mathem. Geophysics, Russian Acad. Sci., Lavrentieva str., 6, 630090 Novosibirsk, Russia. Email: karl@osmf.sscc.ru)

  • Mozartova N.

    (Novosibirsk State University, Pirogova str., 2, 630090 Novosibirsk, Russia. Email: nmozartova@mail.ru)

Abstract

Sparsified Randomization Monte Carlo (SRMC) algorithms for solving large systems of linear algebraic equations are presented. We construct efficient stochastic algorithms based on a probabilistic sampling of small size sub-matrices, or a randomized evaluation of a matrix-vector product and matrix iterations via a random sparsification of the matrix. This approach is beyond the standard Markov chain based Neumann–Ulam method which has no universal instrument to decrease the variance. Instead, in the new method, first, the variance can be decreased by increasing the number of the sampled columns of the matrix in play, and second, it is free of the restricted assumption of the Neumann–Ulam scheme that the Neumann series converges. We apply the developed methods to different stochastic iterative procedures. Application to boundary integral equation of the electrostatic potential theory is given where we develop a SRMC algorithm for solving the approximated system of linear algebraic equations, and compare it with the standard Random Walk on Boundary method.

Suggested Citation

  • Sabelfeld K. & Mozartova N., 2009. "Sparsified Randomization Algorithms for large systems of linear equations and a new version of the Random Walk on Boundary method," Monte Carlo Methods and Applications, De Gruyter, vol. 15(3), pages 257-284, January.
    • Handle: RePEc:bpj:mcmeap:v:15:y:2009:i:3:p:257-284:n:5
    DOI: 10.1515/MCMA.2009.015
    as

    Download full text from publisher

    File URL: https://doi.org/10.1515/MCMA.2009.015
    Download Restriction: For access to full text, subscription to the journal or payment for the individual article is required.
    File URL: https://libkey.io/10.1515/MCMA.2009.015?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Sabelfeld, K.K. & Mozartova, N.S., 2011. "Sparsified Randomization algorithms for low rank approximations and applications to integral equations and inhomogeneous random field simulation," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 82(2), pages 295-317.
    2. Sabelfeld, Karl K., 2018. "Stochastic projection methods and applications to some nonlinear inverse problems of phase retrieving," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 143(C), pages 169-175.
    3. Sabelfeld Karl K., 2016. "Splitting and survival probabilities in stochastic random walk methods and applications," Monte Carlo Methods and Applications, De Gruyter, vol. 22(1), pages 55-72, March.
    4. Sabelfeld Karl K., 2016. "Vector Monte Carlo stochastic matrix-based algorithms for large linear systems," Monte Carlo Methods and Applications, De Gruyter, vol. 22(3), pages 259-264, September.
    5. Sabelfeld, Karl K., 2018. "A random walk on spheres based kinetic Monte Carlo method for simulation of the fluctuation-limited bimolecular reactions," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 143(C), pages 46-56.
    6. Sabelfeld Karl & Mozartova Nadezhda, 2012. "Stochastic boundary collocation and spectral methods for solving PDEs," Monte Carlo Methods and Applications, De Gruyter, vol. 18(3), pages 217-263, September.
    7. Sabelfeld Karl & Loshchina Nadja, 2010. "Stochastic iterative projection methods for large linear systems," Monte Carlo Methods and Applications, De Gruyter, vol. 16(3-4), pages 343-359, January.
    8. Grigoriu Mircea, 2014. "An efficient Monte Carlo solution for problems with random matrices," Monte Carlo Methods and Applications, De Gruyter, vol. 20(2), pages 121-136, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:bpj:mcmeap:v:15:y:2009:i:3:p:257-284:n:5. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Peter Golla (email available below). General contact details of provider: https://www.degruyter.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.