IDEAS home Printed from https://ideas.repec.org/a/bpj/mcmeap/v22y2016i3p259-264n4.html

Vector Monte Carlo stochastic matrix-based algorithms for large linear systems

Author

Listed:
  • Sabelfeld Karl K.

    (Institute of Computational Mathematics and Mathematical Geophysics, Russian Academy of Sciences, Novosibirsk, Russian Federation)

Abstract

In this short article we suggest randomized scalable stochastic matrix-based algorithms for large linear systems. The idea behind these stochastic methods is a randomized vector representation of matrix iterations. In addition, to minimize the variance, it is suggested to use stochastic and double stochastic matrices for efficient randomized calculation of matrix iterations and a random gradient based search strategy. The iterations are performed by sampling random rows and columns only, thus avoiding not only matrix matrix but also matrix vector multiplications. Further improvements of the methods can be obtained through projections by a random gaussian matrix.

Suggested Citation

  • 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.
    • Handle: RePEc:bpj:mcmeap:v:22:y:2016:i:3:p:259-264:n:4
    DOI: 10.1515/mcma-2016-0112
    as

    Download full text from publisher

    File URL: https://doi.org/10.1515/mcma-2016-0112
    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-2016-0112?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

    for a different version of it.

    References listed on IDEAS

    as
    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. John Rust, 1997. "Using Randomization to Break the Curse of Dimensionality," Econometrica, Econometric Society, vol. 65(3), pages 487-516, May.
    3. 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.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. 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.
    2. 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.
    3. 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.
    4. Norets, Andriy & Shimizu, Kenichi, 2024. "Semiparametric Bayesian estimation of dynamic discrete choice models," Journal of Econometrics, Elsevier, vol. 238(2).
    5. Nikolaj Malchow-Møller & Michael Svarer, 2003. "Estimation of the multinomial logit model with random effects," Applied Economics Letters, Taylor & Francis Journals, vol. 10(7), pages 389-392.
    6. Zéphyr, Luckny & Lang, Pascal & Lamond, Bernard F. & Côté, Pascal, 2017. "Approximate stochastic dynamic programming for hydroelectric production planning," European Journal of Operational Research, Elsevier, vol. 262(2), pages 586-601.
    7. Jiarui Han & Tze Lai & Viktor Spivakovsky, 2006. "Approximate Policy Optimization and Adaptive Control in Regression Models," Computational Economics, Springer;Society for Computational Economics, vol. 27(4), pages 433-452, June.
    8. Ertian Chen, 2025. "Model-Adaptive Approach to Dynamic Discrete Choice Models with Large State Spaces," Papers 2501.18746, arXiv.org, revised Mar 2026.
    9. John Rust & Joseph Traub & Henryk Wozniakowski, 1999. "No Curse of Dimensionality for Contraction Fixed Points Even in the Worst Case," Computational Economics 9902001, University Library of Munich, Germany.
    10. Janssen, Marco A. & Anderies, John M. & Walker, Brian H., 2004. "Robust strategies for managing rangelands with multiple stable attractors," Journal of Environmental Economics and Management, Elsevier, vol. 47(1), pages 140-162, January.
    11. Schirmer, Andreas & Riesenberg, Sven, 1997. "Parameterized heuristics for project scheduling: Biased random sampling methods," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 456, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    12. Ji, Yongjie & Rabotyagov, Sergey & Kling, Catherine L., 2014. "Crop Choice and Rotational Effects: A Dynamic Model of Land Use in Iowa in Recent Years," 2014 Annual Meeting, July 27-29, 2014, Minneapolis, Minnesota 170366, Agricultural and Applied Economics Association.
    13. Andrew Ching & Susumu Imai & Masakazu Ishihara & Neelam Jain, 2012. "A practitioner’s guide to Bayesian estimation of discrete choice dynamic programming models," Quantitative Marketing and Economics (QME), Springer, vol. 10(2), pages 151-196, June.
    14. Aruoba, S. Boragan & Fernandez-Villaverde, Jesus & Rubio-Ramirez, Juan F., 2006. "Comparing solution methods for dynamic equilibrium economies," Journal of Economic Dynamics and Control, Elsevier, vol. 30(12), pages 2477-2508, December.
    15. O. Linton & E. Mammen, 2005. "Estimating Semiparametric ARCH(∞) Models by Kernel Smoothing Methods," Econometrica, Econometric Society, vol. 73(3), pages 771-836, May.
    16. Arvid Raknerud & Rolf Golombek, 2000. "Exit Dynamics with Rational Expectations," Discussion Papers 291, Statistics Norway, Research Department.
    17. Andriy Norets, 2009. "Inference in Dynamic Discrete Choice Models With Serially orrelated Unobserved State Variables," Econometrica, Econometric Society, vol. 77(5), pages 1665-1682, September.
    18. Blom Västberg, Oskar & Karlström, Anders & Jonsson, Daniel & Sundberg, Marcus, 2016. "Including time in a travel demand model using dynamic discrete choice," MPRA Paper 75336, University Library of Munich, Germany, revised 11 Nov 2016.
    19. Christian Belzil & Jörgen Hansen, 2004. "Earnings Dispersion, Risk Aversion And Education," Research in Labor Economics, in: Accounting for Worker Well-Being, pages 335-358, Emerald Group Publishing Limited.
    20. Isaiah Hull & Or Sattath & Eleni Diamanti & Göran Wendin, 2024. "Quantum Technology for Economists," Contributions to Economics, Springer, number 978-3-031-50780-9, February.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:22:y:2016:i:3:p:259-264:n:4. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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.degruyterbrill.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.