Search

The sparse triangular solve kernels, SpTRSV and SpTRSM, are important building blocks for a number of numerical linear algebra routines. Parallelizing SpTRSV and SpTRSM on today's manycore platforms, such as GPUs, is not an easy task since computing a component of the solution may depend on previously computed components, enforcing a degree of sequential processing. As a consequence, most existing work introduces a preprocessing stage to partition the components into a group of level-sets or colour-sets so that components within a set are independent and can be processed simultaneously during the subsequent solution stage. However, this class of methods requires a long preprocessing time as well as significant runtime synchronization overheads between the sets. To address this, we propose in this paper novel approaches for SpTRSV and SpTRSM in which the ordering between components is naturally enforced within the solution stage. In this way, the cost for preprocessing can be greatly reduced, and the synchronizations between sets are completely eliminated. To further exploit the data-parallelism, we also develop an adaptive scheme for efficiently processing multiple right-hand sides in SpTRSM. A comparison with a state-of-the-art library supplied by the GPU vendor, using 20 sparse matrices on the latest GPU device, shows that the proposed approach obtains an average speedup of over two for SpTRSV and up to an order of magnitude speedup for SpTRSM. In addition, our method is up to two orders of magnitude faster for the preprocessing stage than existing SpTRSV and SpTRSM methods. [ABSTRACT FROM AUTHOR]

Abstract: We design, analyse and test a class of incomplete orthogonal factorization preconditioners constructed from Givens rotations, incorporating some dropping strategies and updating tricks, for the solution of large sparse systems of linear equations. Comprehensive accounts about how the preconditioners are coded, what storage is required and how the computation is executed for a given accuracy are presented. A number of numerical experiments show that these preconditioners are competitive with standard incomplete triangular factorization preconditioners when they are applied to accelerate Krylov subspace iteration methods such as GMRES and BiCGSTAB. [Copyright &y& Elsevier]

Describes the Basic Linear Algebra Subprograms (BLAS) for sparse matrices. Goal of the Sparse BLAS standard; Functionalities of the BLAS for dense matrix and vector operations; Procedure for the use of the Sparse BLAS; Routines for the creation of sparse matrices.

Discusses the interface design for the Sparse Basic Linear Algebra Subprograms, the kernels in the standard from the BLAS Technical Forum that are concerned with unstructured sparse matrices. Different ways of storing and accessing the nonzero entries of the sparse matrix; Details of handle-based generic interface; Representation of sparse vectors.

Proposes a set of Level 3 Basic Linear Algebra Subprograms and associated kernels for sparse matrices. Design, implementation and use of subprograms full matrix multiplication; Routines for permuting, data checking, changing of data format and performing diagonal scaling of matrices; Use of Fortran 77.