We present quasi-Monte Carlo analogs of Monte Carlo methods for some linear algebra problems: solving systems of linear equations, computing extreme eigenvalues, and matrix inversion. Reformulating the problems as solving integral equations with a special kernels and domains permits us to analyze the quasi-Monte Carlo methods with bounds from numerical integration. Standard Monte Carlo methods for integration provide a convergence rate of O(N^(−1/2)) using N samples. Quasi-Monte Carlo methods use quasirandom sequences with the resulting convergence rate for numerical integration as good as O((logN)^k)N^(−1)). We have shown theoretically and through numerical tests that the use of quasirandom sequences improves both the magnitude of the error and the convergence rate of the considered Monte Carlo methods. We also analyze the complexity of considered quasi-Monte Carlo algorithms and compare them to the complexity of the analogous Monte Carlo and deterministic algorithms.
The tightened energy requirements when designing state-of-the-art high performance computing systems lead to the increased use of computational accelerators. Intel introduced the Many Integrated Core (MIC) architecture for their line of accelerators and successfully competes with NVIDIA on basis of price/performance and ease of development. Although some codes may be ported successfully to Intel MIC architecture without significant modifications, in order to achieve optimal performance one has to make the best use of the vector processing capabilities of the architecture. In this work we present our implementation of Quasi-Monte Carlo methods for matrix computations specifically optimised for the Intel Xeon Phi accelerators. To achieve optimal parallel efficiency we make use of both MPI and OpenMP.