**
Spartns: a SPARse TeNSor representation library
**

For Common Lisp

By Jeronimo Pellegrini

This package is available here
http://aleph0.info/spartns/

**Summary**
Spartns is a SPARse TeNSor representation library (if you don't know
what a tensor is, think of it as a matrix with any number of
dimensions, not just two). Spartns is distributed under the LLGPL
license.
**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

You can define a sparse tensor type using combinations of these:
:representation (array cvector hash hash)
:element-type single-float

means that the tensor will be an array of compressed vectors of
hashtables of hashtables of single-float. Functions and macros will
be defined with type declarations for very fast access to this
structure.
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.