IDEAS home Printed from https://ideas.repec.org/a/bpj/mcmeap/v22y2016i3p259-264n4.html
   My bibliography  Save this article

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 search for a different version of it.

    References listed on IDEAS

    as
    1. 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.
    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.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.
    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. 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.
    5. Alexei Onatski & Noah Williams, 2003. "Modeling Model Uncertainty," Journal of the European Economic Association, MIT Press, vol. 1(5), pages 1087-1122, September.
    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. 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.
    9. Kristensen, Dennis & Mogensen, Patrick K. & Moon, Jong Myun & Schjerning, Bertel, 2021. "Solving dynamic discrete choice models using smoothing and sieve methods," Journal of Econometrics, Elsevier, vol. 223(2), pages 328-360.
    10. 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.
    11. Geweke, J. & Joel Horowitz & Pesaran, M.H., 2006. "Econometrics: A Bird’s Eye View," Cambridge Working Papers in Economics 0655, Faculty of Economics, University of Cambridge.
    12. 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.
    13. Aguirregabiria, Victor & Ho, Chun-Yu, 2012. "A dynamic oligopoly game of the US airline industry: Estimation and policy experiments," Journal of Econometrics, Elsevier, vol. 168(1), pages 156-173.
    14. 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.
    15. Mercedes Esteban-Bravo & Jose M. Vidal-Sanz & Gökhan Yildirim, 2014. "Valuing Customer Portfolios with Endogenous Mass and Direct Marketing Interventions Using a Stochastic Dynamic Programming Decomposition," Marketing Science, INFORMS, vol. 33(5), pages 621-640, September.
    16. 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.
    17. 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.
    18. O. Linton & E. Mammen, 2005. "Estimating Semiparametric ARCH(∞) Models by Kernel Smoothing Methods," Econometrica, Econometric Society, vol. 73(3), pages 771-836, May.
    19. Oliver Linton & E. Mammen & J. Nielsen & C. Tanggaard, 1998. "Estimating Yield Curves by Kernel Smoothing Methods," Cowles Foundation Discussion Papers 1205, Cowles Foundation for Research in Economics, Yale University.
    20. Arvid Raknerud & Rolf Golombek, 2000. "Exit Dynamics with Rational Expectations," Discussion Papers 291, Statistics Norway, Research Department.

    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.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.