This is the mail archive of the
gsl-discuss@sourceware.org
mailing list for the GSL project.
switched sparse format to binary trees
- From: Patrick Alken <patrick dot alken at Colorado dot EDU>
- To: "gsl-discuss at sourceware dot org" <gsl-discuss at sourceware dot org>
- Date: Sun, 27 Apr 2014 19:32:48 -0600
- Subject: switched sparse format to binary trees
- Authentication-results: sourceware.org; auth=none
I received a bug report from someone who found that the
gsl_spmatrix_set() function did not properly detect duplicate elements
(ie it could set the same (i,j) matrix element to more than 1 value).
This was related to the linear array scheme I had originally
implemented, which made it very infefficient to find duplicates (ie: a
linear search was required each time).
So I've changed the storage scheme for the triplet representation to a
binary tree (specifically the AVL balanced binary tree). I took code
from the GNU libavl library for the tree manipulation stuff.
This actually makes a huge speed improvement in duplicate detection and
element retrieval for large sparse matrices. There may however be a
performance hit since a new tree node must be allocated each time an
element is added to the matrix. But I believe the tradeoff is worth it.
Anyone using gsl_spmatrix in their code will need to recompile since the
binary format of that struct has changed.
Patrick