matrix invert routine

[Tom Christiansen]

In article <1989Nov9.233341.14788 at world.std.com> bzs at world.std.com (Barry Shein) writes:

|>I have "spreadsheet-like" data that looks like this:
|>	a1 b1 c1
|>	a2 b2 c2
|>	a3 b3 c3
|>and I want to get it in a form like:
|>	a1 a2 a3
|>	b1 b2 b3
|>	c1 c2 c3
|

|Assume you have 3 columns as shown:
|
|	#!/bin/sh
|	cp /dev/null outfile
|	for i in 1 2 3
|	do
|		cut -f$i datafile | tr '\012' '\011' >> outfile
|		echo '' >> outfile
|	end
|	ed - outfile <<'EOF'
|	1,$s/.$//
|	w
|	q
|	EOF

I had to change the "end" to "done" (too much csh, barry?  :-)
and add "-d' '" to the cut line to make this work.  This is a nice
example of using small, dedicated UNIX tools to do your job.  It
is also a good example of why doing this is terribly slow.  

Here's the perl version.  It's bit more general than the sh version
because it doesn't have to be hacked to work for different sized
matrices or different files, but does basically the same thing:

    #!/usr/local/bin/perl

    $[ = 1;    # array should start at 1 not 0

    while (<>) {
	split;
	$rows++;
	$cols = $#_ if $#_ > $cols;
	for ($j = 1; $j <= $#_; $j++) {
	    $matrix{$rows,$j} = $_[$j];
	} 
    } 

    for ($i = 1; $i <= $rows; $i++) {
	for ($j = 1; $j <= $cols; $j++) {
	    print $matrix{$j,$i}, " ";
	} 
	print "\n";
    } 


Here are the timings for the original dataset.  I ran both tests
twice to get everything in memory.  All timings were run on a Convex-C1.  

% /bin/time xpose.sh 
        2.2 real        0.2 user        1.6 sys
% /bin/time xpose.perl < mat > outfile
        0.4 real        0.0 user        0.2 sys

That's of 5.5 times longer on real time, call it twice as long system,
and 8 times as long on system for the sh version.

This is not a great test because of the resolution.  Let's
try it on this dataset:

% cat mat2
00 01 02 03 04 05 06 07 08 09 
10 11 12 13 14 15 16 17 18 19 
20 21 22 23 24 25 26 27 28 29 
30 31 32 33 34 35 36 37 38 39 
40 41 42 43 44 45 46 47 48 49 
50 51 52 53 54 55 56 57 58 59 
60 61 62 63 64 65 66 67 68 69 
70 71 72 73 74 75 76 77 78 79 
80 81 82 83 84 85 86 87 88 89 
90 91 92 93 94 95 96 97 98 99 

Now I'll go hack on xpose.sh to make it work for square matrices of
order 10 (and coming from file mat2 not mat) and rerun the timings.

% /bin/time xpose.sh   
        6.6 real        0.8 user        4.4 sys
% /bin/time xpose.perl < mat2 > outfile
        0.9 real        0.5 user        0.2 sys

That's more than 7.3x the real, 1.6x the user, and 22x on system
time for the sh version.

'Nuff said.

--tom

    Tom Christiansen                       {uunet,uiucdcs,sun}!convex!tchrist 
    Convex Computer Corporation                            tchrist at convex.COM
		 "EMACS belongs in <sys/errno.h>: Editor too big!"