This is the mail archive of the
mailing list for the GSL project.
Re: Sparse matrix extension
- From: Alexis Tantet <alexis dot tantet at gmail dot com>
- To: Patrick Alken <alken at colorado dot edu>
- Cc: "gsl-discuss at sourceware dot org" <gsl-discuss at sourceware dot org>
- Date: Wed, 20 Jan 2016 19:31:49 +0100
- Subject: Re: Sparse matrix extension
- Authentication-results: sourceware.org; auth=none
- References: <CAMWWPT3uJj4Vrn7ut6+F18gY===zd6+1r1UJhz0hcCj--zwtdg at mail dot gmail dot com> <CAMWWPT3Y=x-vYphaV+2gHPb9WZqEfYdDxs4T0KqBq987VjvDQA at mail dot gmail dot com> <569E6C33 dot 1090505 at colorado dot edu> <CAMWWPT2kMe=R0qUz4P6n_xzG+oW-8pOFwCtBuaritZ5MF6jzAg at mail dot gmail dot com> <569EA1A9 dot 2080101 at colorado dot edu>
I've cloned gsl.git, made my modifications to spmatrix/ and spblas/
and pushed them to master at:
This time, I've tried to modify the code as little as possible. I've
usually added comments labelled "AT" with each modification.
I also have a few questions about the code which I've labelled "?AT".
Finally, I've added the corresponding tests to both test.c (successful
on my machine).
I see that duplicates are handled for the triplet format by replacing.
Thus, I removed the function taking care of sorting and summing
duplicates that I had added to _compress (the trick was to transpose
with copy to reorder first, transpose back and remove the duplicates
then, taken from Eigen C++). Instead, I have added an option to sum
the duplicates (useful e.g. when counting links of a graph or
transitions of a Markov chain). One may need the third option of
repeating the triplets, but then avl_insert should also be modified.
However, if I've understood well, no sorting of the inner indices is
performed right now. This could be problematic in the future (e.g. in
functions such as _equal).
For _spdgemm for CRS matrices, I've used the trick (A B)^t = B^t A^t
to convert the problem to CSC. I've tested it successfully but you may
not like the coding style.
I hope that helps,
On Tue, Jan 19, 2016 at 9:50 PM, Patrick Alken <email@example.com> wrote:
> On 01/19/2016 12:55 PM, Alexis Tantet wrote:
>> Hi Patrick,
>> Thanks for the quick reply! I wanted to be sure that this contribution
>> is useful before to spend time on the merging with the latest version.
>> I will create the gsl.git repository and work on it during the week.
>> I had already had a look at the documentation but did not know about
>> the iterative solvers (a link between each modules would be useful).
>> My contribution indeed fits in the sparse matrix module + the update
>> of the dgemm and dgemv functions to support CRS (an update may also be
>> needed for the solvers).
> The solvers only call dgemv (as far as I remember) so they shouldn't need an
> update once dgemv is updated.
>> I have also developed a simple C++ object allowing to use gsl_spmatrix
>> as a user-defined matrix in ARPACK++ (a maintained fork of ARPACK++
>> can be found at https://github.com/m-reuter/arpackpp), allowing to
>> avoid having to use other libraries such as superLU. It could be
>> useful to others, maybe as an extension. Now that I think about it,
>> the iterative solvers could also be used to support the shift and
>> invert modes (see ARPACK++ documentation). What do you think (I could
>> work on it)?
> I've never used ARPACK, but if you want to make an extension to interface
> GSL/ARPACK its fine with me - such an extension would never be added to the
> main GSL code since GSL tries to be as standalone as possible.
>> If you have major comments, the sooner the better, so that I can work
>> on them while merging.
>> Thank you for your interest,
>> On Tue, Jan 19, 2016 at 6:02 PM, Patrick Alken <firstname.lastname@example.org> wrote:
>>> Hi Alexis,
>>> This looks like very good work! Adding compressed row storage has been
>>> my todo list for a while. The 'gslsp' extension is unfortunately very out
>>> date, and the current git contains newer code (including a GMRES
>>> linear solver). I removed the gslsp extension from the web page a while
>>> to reflect this. You can browse the latest manual to see the current
>>> matrix capabilities (http://www.gnu.org/software/gsl/manual/gsl-ref.pdf)
>>> there are 3 chapters: sparse matrices, sparse blas and sparse linear
>>> - it looks like your contributions will fit into the sparse matrices
>>> Would you be able to verify that your changes are compatible with the
>>> current gsl.git repository? This will make it much easier for me to merge
>>> everything into the git when ready. It would be best if you made a new
>>> branch of gsl.git, and add your changes so I can then pull them from
>>> or somewhere. I will try to find some time in the next few days to look
>>> your code.
>>> Thanks again,
>>> On 01/19/2016 09:43 AM, Alexis Tantet wrote:
>>>> Dear GSLers,
>>>> As a scientist rather than a developer, I have developed an extension
>>>> of the sparse matrix module (CRS, I/O, manipulation, see below), which
>>>> I have tested. These modifications conserve the structure of the
>>>> original module and be useful for a large number of sparse matrices
>>>> I'm not familiar with the contributing process here. My repository can
>>>> be found there:
>>>> Unfortunately, I did not know of the gsl.git repository and I forked it
>>>> https://github.com/drjerry/gslsp ,
>>>> which seems to be a bit older than gsl.git.
>>>> How can I push/merge to gsl.git ? Should it be as an update or another
>>>> extension? Is it necessary to adapt to the newest version of the code
>>>> Best regards,
>>>> Alexis Tantet
>>>> Extension of the sparse matrix module of GSL
>>>> Usages of sparse matrices are numerous in scientific computing.
>>>> When numerical linear algebra problems become large, sparse
>>>> matrices become necessary to avoid memory overload and unnecessary
>>>> computations, at the cost of element access and matrix construction.
>>>> As a result, most large scale linear solvers or eigen solvers perform
>>>> on sparse matrices.
>>>> Fortunately, a very useful sparse matrix module has recently been
>>>> introduced to GSL.
>>>> However, important features are still lacking, such has
>>>> Compressed Row Storage (CRS) matrices, input/output functions and
>>>> other matrix properties and manipulation functions.
>>>> This new version attempts to address this, conserving the original
>>>> structure of the module and conventions.
>>>> Major changes
>>>> * Add CRS format and update functions manipulating compressed matrices :
>>>> - additional flag GSL_SPMATRIX_CRS and macro GSLSP_ISMATRIX (
>>>> gsl_spmatrix.h )
>>>> - additional members innerSize and outerSize used to iterate
>>>> matrix elements ( gsl_spmatrix.h )
>>>> - rename some variables for coherence ( gsl_spmatrix.h , *.c )
>>>> - update all functions on compressed matrices ( *.c )
>>>> * Allow to sum duplicate elements when compressing ( spcompress.c ) :
>>>> - modify gsl_spmatrix_compress
>>>> - add gsl_spmatrix_sum_duplicate
>>>> * CCS <-> CRS and fast transpose inplace in spswap.c :
>>>> - add gsl_spmatrix_switch_major
>>>> - add gsl_spmatrix_transpose
>>>> * Add printing and scanning functions in spio.c :
>>>> - add gsl_spmatrix_fprintf
>>>> - add gsl_spmatrix_fscanf
>>>> * Add manipulation functions in spmanip.c (particularly useful for
>>>> Markov chain transition matrices) :
>>>> - add gsl_spmatrix_get_rowsum : get vector of sum over row
>>>> - add gsl_spmatrix_get_colsum : get vector of sum over column
>>>> - add gsl_spmatrix_div_rows : divide all elements of each row
>>>> by a vector element
>>>> - add gsl_spmatrix_div_cols : divide all elements of each
>>>> column by a vector element
>>>> * Add test functions in atprop.c :
>>>> - add gsl_spmatrix_gt_elements : greater than test for each
>>>> - add gsl_spmatrix_ge_elements : greater or equal than test for
>>>> each matrix element
>>>> - add gsl_spmatrix_lt_elements : lower than test for each matrix
>>>> - add gsl_spmatrix_le_elements : lower or equal than test for
>>>> each matrix element
>>>> - add gsl_spmatrix_any : test if any non-zero element in
>>>> Other minor changes have been made, such as error tests.
>>>> test.c has also been updated to test new features.