[PD] complex network

Mathieu Bouchard matju at artengine.ca
Sat Apr 4 18:35:47 CEST 2009


On Fri, 3 Apr 2009, Frank Barknecht wrote:

> The last paragraph explains sparse matrices or rather, why you often 
> don't need to treat them specially in Lua.

Well, you better treat them specially in Lua, else you'd implement a 
nonspecial matrix product using three for-loops as usual, and then the 
result of two sparse matrices will be a nonsparse matrix. What do you do 
with that? No, you need to treat them specially, because assigning a bunch 
of zeroes in a lua table will take RAM. Furthermore, I just tried Lua, and 
you do need to treat every nil value specially, because you can't perform 
arithmetic on nil (which is quite normal). This is fixed by defining a 
method for the __index selector (using [] sends a __index message to the 
table).

And then their triangle matrix gimmick... the very fact that those tables 
are actually hashtables instead of anything like pd float tables, make 
them take usually twice RAM or more (perhaps 3 or 4 depending on their 
implementation) if you just use all slots, so if you only use half of the 
slots then you're not saving any RAM at all compared to pd's float tables.

That page is not outright lying, but it's definitely not telling the 
truth.

Hashtables of pairs are one way to represent sparse matrices, but if you 
ever need to lookup complete rows or columns, then you need a hashtable of 
hashtables for rows, columns, or both (twice the same data transposed).

Depending on how sparse the nonzero data is supposed to be and how 
clustered the nonzero data is supposed to be and how you need to be 
accessing/transforming the data, some other representations may be more 
attractive than the hash or the hash-of-hashes. For example:

  * matrix-of-matrix: a 400x400 matrix could be cut into 20x20 pieces put
    into a 20x20 matrix and so every 20x20 piece that is completely filled
    with 0 is not allocated and instead replaced by a nil or zero. You can
    tune the size of the pieces depending on what goes well with the data
    set.

  * quadtree: make a 2x2 matrix of 2x2 matrices of 2x2 matrices of 2x2
    matrices of 2x2 matrices of 2x2 matrices of ... and just don't allocate
    any piece that only contains zeroes.

Here I suppose that this is using "ordinary arrays" as you can find in 
Python, Ruby, C/C++, Tcl, etc., and apparently not Lua (?). But you could 
do quite similar things with Lua anyway. In any case, each of those 
representations needs algorithms customised for them, unless you can 
figure out a generic design that is efficient with several 
representations, perhaps using a "foreachnonzero" loop operation as the 
central concept.

  _ _ __ ___ _____ ________ _____________ _____________________ ...
| Mathieu Bouchard - tél:+1.514.383.3801, Montréal, Québec


More information about the Pd-list mailing list