The University of Birmingham
School of Computer Science
The Cognition and Affect Project

Spartns: a SPARse TeNSor representation library
For Common Lisp
By Jeronimo Pellegrini

http://aleph0.info/spartns/

Features:

• Represents mappings from one dimension onto another using any scheme you want (there are three built-in schemes: array, hash and compressed-vector, but you can roll your own and plug it);
• Flexible: works with any data type;
• Heavily optimized: traversing the tensor is extremely fast (in one specific situation, it was 10 times faster than a naive implementation in C++);
• Fairly portable: works with SBCL, ABCL, CMUCL, Clisp, ECL, GCL, Poplog, LispWorks and Allegro Common Lisp;
• ASDF installable (thanks Slobodan Blazeski!);
• Easy to use, with introductory documentation (not only on-line);
• Comes with description of the internals of the library.

Spartns can represent different dimensions using different "representation schemes".

There are currently three available:

• Dense array, O(1), very small overhead
• Hashtables, O(1), medium overhead
• Compressed vectors, O(lg n), but very optimized

   :representation (array cvector hash hash)
   :element-type   single-float

It is also possible to convert between types (for example, start with all hashes, then convert to compressed vectors).

And finally, there are traversals: methods for traversing the sparse tensor quickly. The difference is that traversing a tensor by repeatedly calling GET (which is O(ln n)) is slow. Spartns takes advantage of the underlying structure and traverses the whole structure in O(K), where K is the number of non-zero elements.

For up to date information and dowloadable sources see the web site, above.