I have finished testing basic large densely parallel matrix multiplication on 4 gpu's ,and have done work on TSLU and TSQR on cpu's based on mpi. I am going to continue working on the theory of parallel computation of sparse matrices. As far as I know, there are compression formats for sparse matrices like CSR, and there are also methods based on graph partitioning. Are these two methods two separate approaches and which one is more advantageous?e.g., sparse matrix multiplication, sparse matrix factorisation, and solver.Could you give me some papers or links?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
your question is too general. It is very to hard to give specific advice. I will suggest you two books that you can use as first references, but they may not help much in terms of GPU computing for sparse matrices.
First book is Yousef Saad's "Iterative Methods for Sparse Linear Systems", which you can download from his website for free. This book covers some fundamentals of sparse linear algebra, and gives a very detailed description of some iterative methods.
Second book is Timothy Davis' "Direct Methods for Sparse Linear Systems". This is harder to get your hands onto. If you are a student (undergrad or grad), your university library will have access to it; otherwise you may check your library or buy it. It is a good reference to have if you are going to stay in this field for a long time. This book is also a good primer, and Tim Davis is one of the handful people who has a performance sparse linear solver on GPUs (https://developer.nvidia.com/cholmod). You can search for "GPU acceleration of CHOLMOD" and you will find many articles.
If Tim Davis' book is too dense (which honestly has very big ideas summarized in so few pages sometimes), I can suggest "Computer Solution of Sparse Linear Systems" by George and Liu as a preliminary. Note that this book is quite old, but it was written at a time when people were trying to figure out how to sparse linear algebra efficiently, so it is quite verbose.
answered Oct 30 at 6:13
-
$\begingroup$ Thank you for your answer, because I have to design the program interface based on the theory of sparse algebra, so the question will be very exemplary and complete, I have completed the design of datastorage for distributed sparse matrix multiplication, I will refer to these bibliographies for the solver of sparse matrices. $\endgroup$ Oct 30 at 8:03
-
$\begingroup$ At the moment I think sparse matrix distributed computation (add,mul) involves matrix slice and collective communication of sparse structures, but matrix factorization and iterative solvers I'm not familiar with yet.Supporting a heterogeneous collective communication backend this looks like it will require some amount of work.But this can design distributed and sparse matrix computations separately.Obtaining a generalized distributed sparse matrix computation pipeline $\endgroup$ Oct 30 at 8:06
-
$\begingroup$ This means that the distributed is decoupled from the sparse matrix structure and only deals with sparse matrices uniformly sliced and aggregated communication strategies. The different sparse structures and the operations between them are defined externally $\endgroup$ Oct 30 at 8:09
-
$\begingroup$ You can take a look at the MA86/87/97 papers, SuperLU papers and also Pardiso papers, they are quite complete on how they implement parallel sparse factorization. Parallel matvec operations (especially on GPUs) is an open research area as the current methods do not scale very well. $\endgroup$ Oct 31 at 6:40
-