On Fri, 3 Apr 2009, Ricardo Brazileiro wrote:

i'm refering a graphs, for study models in complex networks. it's necessary uses matrix....

I don't think anything in Pd handles sparse matrices of any kind, but I could be wrong. In that case, you will have to use ordinary matrices. If you have very very large numbers of nodes, it can take a lot of room (quadratic room) but especially a lot of time (cubic time).

AFAIK, the only tool that has int matrices and byte matrices is GridFlow, so, anything else would use t_float for that (?), but that only saves on space.

Probably computation time is the biggest issue. There are some upsides to using ordinary matrices: for example, you can compute some fabulous shortcuts using eigendecomposition (valór e vector proprio, aka autovalores). But if you have some thousand vertices, the computation time is still quite prohibitive.

So if you need something better, you will need some kind of sparse matrix or some non-matrix graph representation. If I were you, I'd try to find something that can be processed as a matrix, so that I have a greater variety of operations to pick from.

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

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