Top

Published in:

2018 | OriginalPaper | Chapter

On Monte Carlo and Quasi-Monte Carlo for Matrix Computations

Authors : Vassil Alexandrov, Diego Davila, Oscar Esquivel-Flores, Aneta Karaivanova, Todor Gurov, Emanouil Atanassov

Published in: Large-Scale Scientific Computing

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper focuses on minimizing further the communications in Monte Carlo methods for Linear Algebra and thus improving the overall performance. The focus is on producing set of small number of covering Markov chains which are much longer that the usually produced ones. This approach allows a very efficient communication pattern that enables to transmit the sampled portion of the matrix in parallel case. The approach is further applied to quasi-Monte Carlo. A comparison of the efficiency of the new approach in case of Sparse Approximate Matrix Inversion and hybrid Monte Carlo and quasi-Monte Carlo methods for solving Systems of Linear Algebraic Equations is carried out. Experimental results showing the efficiency of our approach on a set of test matrices are presented. The numerical experiments have been executed on the MareNostrum III supercomputer at the Barcelona Supercomputing Center (BSC) and on the Avitohol supercomputer at the Institute of Information and Communication Technologies (IICT).

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter On the Regularity of Linear-Quadratic Optimal Control Problems with Bang-Bang Solutions

next chapter On the Parallel Implementation of Quasi-Monte Carlo Algorithms

www.open-mpi.org/.

www.paralution.com/.

Golub, G., Loan, C.: Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (1996)MATH

Straßburg, J., Alexandrov, V.N.: Enhancing Monte Carlo preconditioning methods for matrix computations. In: Proceedings ICCS 2014, pp. 1580–1589 (2014)

Alexandrov, V.N., Esquivel-Flores, O.A.: Towards Monte Carlo preconditioning approach and hybrid Monte Carlo algorithms for matrix computations. CMA 70(11), 2709–2718 (2015)MathSciNet

Carpentieri, B., Duff, I., Giraud, L.: Some sparse pattern selection strategies for robust Frobenius norm minimization preconditioners in electromagnetism. Numer. Linear Algebra Appl. 7, 667–685 (2000)MathSciNetCrossRefMATH

Carpentieri, B., Duff, I., Giraud, L.: Experiments with sparse preconditioning of dense problems from electromagnetic applications, CERFACS, Toulouse, France. Technical report (2000)

Alléon, G., Benzi, M., Giraud, L.: Sparse approximate inverse preconditioning for dense linear systems arising in computational electromagnetics. Num. Algorithms 16(1), 1–15 (1997)MathSciNetCrossRefMATH

Evans, T., Hamilton, S., Joubert, W., Engelmann, C.: MCREX - Monte Carlo Resilient Exascale Project. http://www.csm.ornl.gov/newsite/documents

Benzi, M., Meyer, C., Tůma, M.: A sparse approximate inverse preconditioner for the conjugate gradient method. SIAM J. Sci. Comput. 17(5), 1135–1149 (1996)MathSciNetCrossRefMATH

Huckle, T., Kallischko, A., Roy, A., Sedlacek, M., Weinzierl, T.: An efficient parallel implementation of the MSPAI preconditioner. Parallel Comput. 36(5–6), 273–284 (2010)MathSciNetCrossRefMATH

10.

Grote, M., Hagemann, M.: SPAI: SParse Approximate Inverse Preconditioner. Spaidoc. pdf paper in the SPAI, vol. 3, p. 1 (2006)

11.

Huckle, T.: Factorized sparse approximate inverses for preconditioning. J. Supercomput. 25(2), 109–117 (2003)CrossRefMATH

12.

Strassburg, J., Alexandrov, V.: On scalability behaviour of Monte Carlo sparse approximate inverse for matrix computations. In: Proceedings of the ScalA 2013 Workshop, Article no. 6. ACM (2013)

13.

Vajargah, B.F.: A new algorithm with maximal rate convergence to obtain inverse matrix. Appl. Math. Comput. 191(1), 280–286 (2007)MathSciNetMATH

14.

Hoemmen, M., Vuduc, R., Nishtala, R.: BeBOP sparse matrix converter. University of California at Berkeley (2011)

15.

Boisvert, R.F., Pozo, R., Remington, K., Barrett, R.F., Dongarra, J.J.: Matrix market: a web resource for test matrix collections. In: Boisvert, R.F. (ed.) QNS 1997. IFIPAICT, pp. 125–137. Springer, Boston (1997). https://doi.org/10.1007/978-1-5041-2940-4_9 CrossRef

16.

Davis, T.A., Hu, Y.: The University of Florida sparse matrix collection. ACM Trans. Math. Softw. (TOMS) 38(1), 1 (2011)MathSciNetMATH

17.

Alexandrov, V., Esquivel-Flores, O., Ivanovska, S., Karaivanova, A.: On the preconditioned Quasi-Monte Carlo algorithm for matrix computations. In: Lirkov, I., Margenov, S.D., Waśniewski, J. (eds.) LSSC 2015. LNCS, vol. 9374, pp. 163–171. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-26520-9_17 CrossRef

18.

Karaivanova, A.: Quasi-Monte Carlo methods for some linear algebra problems. Convergence and complexity. Serdica J. Comput. 4, 57–72 (2010)MathSciNetMATH

19.

Atanassov, E., Gurov, T., Karaivanova, A., Ivanovska, S., Durchova, M., Dimitrov, D.: On the parallelization approaches for Intel MIC architecture. In: AIP Conference Proceedings, vol. 1773, p. 070001 (2016). https://doi.org/10.1063/1.4964983

Title: On Monte Carlo and Quasi-Monte Carlo for Matrix Computations
Authors: Vassil Alexandrov
Diego Davila
Oscar Esquivel-Flores
Aneta Karaivanova
Todor Gurov
Emanouil Atanassov
Publisher: Springer International Publishing
Book: Large-Scale Scientific Computing
Print ISBN: 978-3-319-73440-8

Electronic ISBN: 978-3-319-73441-5

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-73441-5_26

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner