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.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 & 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.
    2. 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.
    3. 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.
    4. Norets, Andriy & Shimizu, Kenichi, 2024. "Semiparametric Bayesian estimation of dynamic discrete choice models," Journal of Econometrics, Elsevier, vol. 238(2).
    5. Szabolcs Lorincz, 2005. "Persistence Effects in a Dynamic Discrete Choice Model - Application to Low-End Computer Servers," CERS-IE WORKING PAPERS 0510, Institute of Economics, Centre for Economic and Regional Studies.
    6. 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.
    7. Jiaqiao Hu & Michael C. Fu & Vahid R. Ramezani & Steven I. Marcus, 2007. "An Evolutionary Random Policy Search Algorithm for Solving Markov Decision Processes," INFORMS Journal on Computing, INFORMS, vol. 19(2), pages 161-174, May.
    8. Dietmar P.J. Leisen, 1997. "The Random-Time Binomial Model," Finance 9711005, University Library of Munich, Germany, revised 29 Nov 1998.
    9. Alexei Onatski & Noah Williams, 2003. "Modeling Model Uncertainty," Journal of the European Economic Association, MIT Press, vol. 1(5), pages 1087-1122, September.
    10. John Rust, 2014. "The Limits of Inference with Theory: A Review of Wolpin (2013)," Journal of Economic Literature, American Economic Association, vol. 52(3), pages 820-850, September.
    11. 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.
    12. 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.
    13. Judd, Kenneth L. & Maliar, Lilia & Maliar, Serguei & Valero, Rafael, 2014. "Smolyak method for solving dynamic economic models: Lagrange interpolation, anisotropic grid and adaptive domain," Journal of Economic Dynamics and Control, Elsevier, vol. 44(C), pages 92-123.
    14. Hugo Benítez-Silva & Moshe Buchinsky & Hiu Man Chan & Sofia Cheidvasser & John Rust, 2004. "How large is the bias in self-reported disability?," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 19(6), pages 649-670.
    15. Ralph Stinebrickner & Todd Stinebrickner, 2014. "Academic Performance and College Dropout: Using Longitudinal Expectations Data to Estimate a Learning Model," Journal of Labor Economics, University of Chicago Press, vol. 32(3), pages 601-644.
    16. 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.
    17. Ayşe Kabukçuoğlu & Enrique Martínez-García, 2021. "A Generalized Time Iteration Method for Solving Dynamic Optimization Problems with Occasionally Binding Constraints," Computational Economics, Springer;Society for Computational Economics, vol. 58(2), pages 435-460, August.
    18. 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.
    19. 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.
    20. 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.

    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.