We present the submatrix method, a highly parallelizable method for the approximate calculation of inverse p-th roots of large sparse symmetric matrices which are required in different scientific applications. Following the idea of Approximate Computing, we allow imprecision in the final result in order to utilize the sparsity of the input matrix and to allow massively parallel execution. For an n x n matrix, the proposed algorithm allows to distribute the calculations over n nodes with only little communication overhead. The result matrix exhibits the same sparsity pattern as the input matrix, allowing for efficient reuse of allocated data structures. We evaluate the algorithm with respect to the error that it introduces into calculated results, as well as its performance and scalability. We demonstrate that the error is relatively limited for well-conditioned matrices and that results are still valuable for error-resilient applications like preconditioning even for ill-conditioned matrices. We discuss the execution time and scaling of the algorithm on a theoretical level and present a distributed implementation of the algorithm using MPI and OpenMP. We demonstrate the scalability of this implementation by running it on a high-performance compute cluster comprised of 1024 CPU cores, showing a speedup of 665x compared to single-threaded execution.
Implementations for the calculation of the LU and SV decompositions and matrix inversion are part of LAPACK @cite_28 , a popular software library for numerical linear algebra. For solving large sparse systems and calculation of singular values, ARPACK @cite_9 is a well known library which is based on the Arnoldi iteration . There exist different implementations of these libraries, as well as bindings for many different programming languages. With ScaLAPACK @cite_30 and P @cite_25 , there exist extensions of these libraries targeting parallel execution on distributed memory systems using MPI for message passing.
@cite_28 @cite_9 @cite_25 @cite_30
1964477602 1506690472 2117293168
The goal of the LAPACK project is to design and implement a portable linear algebra library for efficient use on a variety of high-performance computers. The library is based on the widely used LINPACK and EISPACK packages for solving linear equations, eigenvalue problems, and linear least-squares problems, but extends their functionality in a number of ways. The major methodology for making the algorithms run faster is to restructure them to perform block matrix operations (e.g., matrix-matrix multiplication) in their inner loops. These block operations may be optimized to exploit the memory hierarchy of a specific architecture. The LAPACK project is also working on new algorithms that yield higher relative accuracy for a variety of linear algebra problems. > List of figures List of tables Preface 1. Introduction to ARPACK. Important features Getting started Reverse communication interface Availability Installation Documentation Dependence on LAPACK and BLAS Expected performance P_ARPACK Contributed additions Trouble shooting and problems 2. Getting started with ARPACK. Directory structure and contents Getting started An example for a symmetric Eigenvalue problem 3. General use of ARPACK. Naming conventions, Precisions, and types Shift and invert spectral transformation mode Reverse communication structure for shift-Invert Using the computational modes Computational modes for real symmetric problems Postprocessing for Eigenvectors using dseupd Computational modes for real nonsymmetric problems Postprocessing for Eigenvectors Using dneupd Computational modes for complex problems Postprocessing for Eigenvectors Using zneupd 4. The implicitly restarted Arnoldi method: structure of the Eigenvalue problem Krylov subspaces and projection methods The Arnoldi factorization Restarting the Arnoldi method The generalized Eigenvalue problem Stopping Criterion 5. Computational routines. ARPACK subroutines LAPACK routines used by ARPACK BLAS routines used by ARPACK Appendix A. Templates and driver routines Symmetric drivers Real Nonsymmetric drivers Complex drivers Band drivers The singular value decomposition Appendix B. Tracking the progress of ARPACK. Obtaining trace output Check-pointing ARPACK Appendix C. The XYaupd ARPACK Routines. DSAUPD DNAUPD ZNAUPD Bibliography Index. This paper outlines the content and performance of ScaLAPACK, a collection of mathematical software for linear algebra computations on distributed memory computers. The importance of developing standards for computational and message passing interfaces is discussed. We present the different components and building blocks of ScaLAPACK, and indicate the difficulties inherent in producing correct codes for networks of heterogeneous processors. Finally, this paper briefly describes future directions for the ScaLAPACK library and concludes by suggesting alternative approaches to mathematical libraries, explaining how ScaLAPACK could be integrated into efficient and user-friendly distributed systems.