From: Patrick Alken <patrick.alken@Colorado.EDU>
To: "gsl-discuss@sourceware.org" <gsl-discuss@sourceware.org>
Subject: switched sparse format to binary trees
Date: Mon, 28 Apr 2014 01:32:00 -0000 [thread overview]
Message-ID: <535DAFC0.8090402@colorado.edu> (raw)
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
next reply other threads:[~2014-04-28 1:32 UTC|newest]
Thread overview: 16+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-04-28 1:32 Patrick Alken [this message]
2014-04-28 22:35 ` Gerard Jungman
2014-04-29 1:13 ` Patrick Alken
2014-04-29 8:40 ` Frank Reininghaus
2014-04-29 19:15 ` Gerard Jungman
2014-04-29 19:52 ` Patrick Alken
2014-04-29 22:07 ` Gerard Jungman
2014-05-01 18:46 ` Patrick Alken
2014-05-01 23:21 ` Gerard Jungman
2014-05-02 1:48 ` GSL containers (switched sparse format to binary trees) Gerard Jungman
2014-05-02 1:56 ` Gerard Jungman
2014-05-02 8:29 ` Rhys Ulerich
2014-05-02 8:33 ` Rhys Ulerich
2014-05-02 8:52 ` Rhys Ulerich
2014-05-02 15:02 ` Patrick Alken
2014-05-13 21:59 ` Gerard Jungman
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=535DAFC0.8090402@colorado.edu \
--to=patrick.alken@colorado.edu \
--cc=gsl-discuss@sourceware.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).