Re: An efficient, scalable matrix transformation algorithm

From your description what you need to do is:

  A1 = F1(a1, a2, a3, ...., an)
  B1 = F2(b1, b2, b3, ...., bn)
  C1 = F3(c1, c2, c3, ...., cn)

on the face of it, that doesn't appear to be O(n^2). You transpose the original matrix so that (a1, a2, ...) etc. are Perl arrays, presumably for the convenience of F1 etc. -- which seems reasonable, though the work to pull a column into a row seems about the same as processing the column directly (unless elements are accessed more than once by the respective Fn.

I assume the issue here is scale. But I regret this humble engineer is struggling to understand where to look for improvement. (Assuming a multi-core processor I can see that processing columns in parallel makes sense -- especially if the original matrix were in shared memory !) You don't say where the matrix comes from... I wonder if it's possible to transpose it as it's read in ?

So... can you post some code ? Preferrably reduced to show the key logic... and give some idea of the true scale ?

Of course, the general advice is to profile what you have, to identify where the time is really being spent.

Comment on Re: An efficient, scalable matrix transformation algorithm

Replies are listed 'Best First'.
Re^2: An efficient, scalable matrix transformation algorithm by Luftkissenboot (Novice) on Jan 28, 2009 at 11:58 UTC
Ah, sorry, you're right. It would be O(n*m) (where m is the number of reduction functions, and n is the number of records). Indeed, the issue is scale. The original data comes in by sampling various parameters of numerous biological electronic sampling devices over time, and so each record keeps a timestamp. The "a" column would, in this case, be a timestamp, and the others would be, say, averages, maxes, minimums for that time window. This needs to be done for a huge number of devices in parallel, or at least in a linear fashion that won't introduce delays, as this has to happen inline with the sampling before it gets archived. The reason for the transformation is for the purpose of re-scaling the granularity of the data. A good example would be: time+microseconds AVGTEMP MAXTEMP MINTEMP STARTTEMP ENDTEMP In order to rescale this type of data to a larger time granularity (say, 5 second chunks, 1 minute chunks, etc.), you need to perform the different functions on each column to make them reflect the proper averages, maximums, minimums, etc. for the new time window. (I forgot to mention that I also considered RRD for this, but it doesn't have enough consolidation functions included, and adding new ones is far from trivial. Will update the original node). Ok, that's all verbose. Here's a code sample, as simple as I can make it and still have it work: Read more... (2 kB)	[reply] [d/l]
Re^3: An efficient, scalable matrix transformation algorithm by dHarry (Abbot) on Jan 28, 2009 at 13:42 UTC
I am still not convinced you have to transpose the matrix but maybe I am having an off-day, i.e. to blind to see it;-) When I read to your post the first thing that jumps into mind is the use of a database., especially since your "reduce functions" are simple. However, assuming you insist on transposing, you might be able to speed things up. The case N != M is more difficult then N = M. The approach you take right now is the straightforward approach but this can give poor performance (as you have probably noticed). In general: depending on circumstances, things like how much storage you have available and more importantly how M relates to N (\|N-M\| small or gcd(N,M) is not small) you can improve by using a more refined algorithm. (This I have taken from the Wiki, already suggested in my earlier response.) You can find pointers there to articles on the subject of in-place matrix transposition. I don’t know of any Perl implementations but the pointers on the Wiki also contain source code so you should be able to rewrite that into Perl if needed. HTH, dHarry	[reply]
Re^4: An efficient, scalable matrix transformation algorithm by Luftkissenboot (Novice) on Jan 28, 2009 at 14:05 UTC
Well, this source is the degenerate case where the objects holding the records are turned into simple arrayrefs, to illustrate the algorithm. I'm willing and able to refactor, though, of course. The transposition happens because the reductions need to be applied to columns, and the functions sum(), avg(), etc. operate on lists. The only alternative to the full transposition I can see would be a column splice -> list/array, which essentially results in the same thing. i.e. I don't see a way to avoid the transposition, one way or another ... ? Maybe it's me that's missing something?	[reply]
Re^5: An efficient, scalable matrix transformation algorithm by dHarry (Abbot) on Jan 28, 2009 at 14:46 UTC
Re^3: An efficient, scalable matrix transformation algorithm by gone2015 (Deacon) on Jan 28, 2009 at 14:20 UTC
I used Devel::Profile and found that 84.74% of the running time is in the `main::transpose` function. I don't know how the data in `@records` actually arrives there, but I would consider capturing it in an array of columns rather than an array of rows -- eliminating the transpose operation completely. I tried replacing the `downsample()` function and the functions themselves, to operate directly on the columns. (The code for that is included below.) In order to get some timings I expanded the sample `@records` by the simple expedient of `@records = (@records) x 100_000`. On my machine, operating directly on the columns downsampled the records in 1.1s, where your code took 12.8s. Mind you, I doubt whether you `downsample` this many samples at once, so these timings will overstate the impact of improving the inside of the `downsample` function. Finally, depending on how the data is input, I would consider combining the downsampling with the input -- avoiding construction of the `@records` array altogether... Read more... See the code (1463 Bytes)	[reply] [d/l] [select]
Re^4: An efficient, scalable matrix transformation algorithm by gone2015 (Deacon) on Jan 28, 2009 at 18:05 UTC
FWIW, this transpose runs ~3.5 times faster than the loop you had (on my machine, anyway). The message here is that the trick with Perl is to replace a `for` or `while` by `map` or `grep` if possible ! `sub transpose_gmch { my ($matrix) = shift ; my @result = () ; my $lc = $#{$matrix->[0]} ; for my $col (0..$lc) { push @result, [map $_->[$col], @$matrix] ; } ; return( \@result ); }` [download]	[reply] [d/l] [select]
Re^5: An efficient, scalable matrix transformation algorithm by Luftkissenboot (Novice) on Jan 29, 2009 at 07:37 UTC
Re^4: An efficient, scalable matrix transformation algorithm by Luftkissenboot (Novice) on Jan 28, 2009 at 15:21 UTC
Wonderful! Indeed, this is what dHarry was getting at, too. Clearly the transpose() step is extraneous, but I guess I was blinded by the way in which my object structure was currently set up to see a manner to address the individual columns. (But that's my own issue, and is clear now.) Thank you both!	[reply]