Abstract
In this paper we present a quasi-Monte Carlo Sparse Approximate Inverse (SPAI) preconditioner. In contrast to the standard deterministic SPAI preconditioners that use the Frobenius norm, Monte Carlo and quasi-Monte Carlo preconditioners rely on stochastic and hybrid algorithms to compute a rough matrix inverse (MI). The behaviour of the proposed algorithm is studied. Its performance is measured and compared with the standard deterministic SPAI and MSPAI (parallel SPAI) approaches and with the Monte Carlo approach. An analysis of the results is also provided.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alexandrov, V.N., Karaivanova, A.: Parallel monte carlo algorithms for sparse SLAE using MPI. In: Margalef, T., Dongarra, J., Luque, E. (eds.) PVM/MPI 1999. LNCS, vol. 1697, pp. 283–290. Springer, Heidelberg (1999)
Allèon, G., Benzi, M., Giraud, L.: Sparse approximate inverse preconditioning for dense linear systems arising in computational electromagnetics. Numer. Algorithm. 16(1), 1–15 (1997)
Atanassov, E.I., Durchova, M.K.: Generating and testing the modified halton sequences. In: Dimov, I., Lirkov, I., Margenov, S., Zlatev, Z. (eds.) NMA 2002. LNCS, vol. 2542, pp. 91–98. Springer, Heidelberg (2003)
Atanassov, E., Karaivanova, A., Ivanovska, S.: Tuning the generation of sobol sequence with Owen scrambling. In: Lirkov, I., Margenov, S., Waśniewski, J. (eds.) LSSC 2009. LNCS, vol. 5910, pp. 459–466. Springer, Heidelberg (2010)
Benzi, M., Meyer, C., Tuma, M.: A sparse approximate inverse preconditioner for the conjugate gradient method. SIAM J. Sci. Comput. 5, 1135–1149 (1996)
Branford, S.: The parallel hybrid Monte Carlo algoritm. Master’s thesis, Schools of Systems Engineering, The Univerity of Reading (2003)
Branford, S.: Hybrid Monte Carlo methods for linear algebra problems. Ph.D. thesis, School of Systems Engineering, The University of Reading, April 2009
Branford, S., Weihrauch, C., Alexandrov, V.N.: A sparse parallel hybrid Monte Carlo algorithm for matrix computations. In: Sunderam, V.S., van Albada, G.D., Sloot, P.M.A., Dongarra, J. (eds.) ICCS 2005. LNCS, vol. 3516, pp. 743–751. Springer, Heidelberg (2005)
Caflisch, R.: Monte Carlo and quasi-Monte Carlo methods. Acta Numerica 7, 1–49 (1998)
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)
Carpentieri, B., Giraud, L., et al.: Experiments with sparse preconditioning of dense problems from electromagnetic applications. Technical report, CERFACS, Toulouse, France (2000)
Fathi, B., Liu, B., Alexandrov, V.N.: Mixed Monte Carlo parallel algorithms for matrix computation. In: Sloot, P.M.A., Tan, C.J.K., Dongarra, J., Hoekstra, A.G. (eds.) ICCS-ComputSci 2002, Part II. LNCS, vol. 2330, pp. 609–618. Springer, Heidelberg (2002)
Grote, M., Hagemann, M.: Spai: sparse approximate inversepreconditioner. Spaidoc.pdf paper in the SPAI 3:1 (2006)
Huckle, T.: Factorized sparse approximate inverses for preconditioning. J. Supercomput. 25(2), 109–117 (2003)
Huckle, T., Kallischko, A., Roy, A., Sedlacek, M., Weinzierl, T.: An efficient parallel implementation of the MSPAI preconditioner. Parallel Comput. 36(56), 273–284 (2010). Parallel Matrix Algorithms and Applications
Karaivanova, A.: Quasi-Monte Carlo methods for some linear algebra problems. Convergence and complexity. Serdica J. Comput. 4, 58–72 (2010). ISSN: 1312–6555
Niederreiter, H.: Random Number Generation and Quasi-Monte Carlo Methods. SIAM, Philadelphia (1992)
Strassburg, J., Alexandrov, V.: Enhancing Monte Carlo preconditioning methods for matrix computations. Procedia Comput. Sci. 29, 1580–1589 (2014)
Acknowledgment
The research work reported in the paper is partly supported by the Bulgarian NSF grant Grant DFNI-I02/8, and second author would like to thank CONACYT-Mexico for supporting potsdoctoral position in BSC.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Alexandrov, V., Esquivel-Flores, O., Ivanovska, S., Karaivanova, A. (2015). On the Preconditioned Quasi-Monte Carlo Algorithm for Matrix Computations. In: Lirkov, I., Margenov, S., Waśniewski, J. (eds) Large-Scale Scientific Computing. LSSC 2015. Lecture Notes in Computer Science(), vol 9374. Springer, Cham. https://doi.org/10.1007/978-3-319-26520-9_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-26520-9_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-26519-3
Online ISBN: 978-3-319-26520-9
eBook Packages: Computer ScienceComputer Science (R0)