Drunk on English, c. 2004

The problem with me and the English language is that I get power-drunk. Imagine going from shoddily translated fantasy to original Tolkien; from indifferent Finnish novels to pure and deliciously colloquial (and, to a Finn, exotic) Stephen King, from badly translated TV shows to understanding the actual English and the actual untranslatable jokes.

Then imagine noting that, hey, you can write in that rich language yourself!

The results of this can flare up, even after many a year, in the weirdest places.

For an example of getting a bit too uppity because of “Wheee! I’m writeing in teh Englishes!” see below the textual parts of a 2004 math homework from a course that happened to be lectured in English (exchange students), which I took as a clue to return the voluntary homework in it, too.

While I got a very good grade (three-minus out of the maximum of three, in ye aulde system) out of that course, occasionally these homeworks bombed spectacularly, mostly because doing an exercise like this cold isn’t the best way to learn Matlab. And when things went in that direction, I squirmed, since you can report on an algorithm even if it doesn’t do what it, er, was constructed to do.

Remember: returned to a math professor as an answer to a very dry extra-credit problem.

* * *

homework associated with problem set 6

Strassen’s algorithm

The general form of Strassen’s algorithm for more efficient computation of the matrix product AB = C is

long boring algorithm removed

This way there are more addition flops than in the ‘normal’ way of multiplying two matrices, but the amount of multiplication flops is lesser — there is one multiplication flop less, to be exact.

Now for 2 x 2 matrices this method is novel indeed but useless; Strassen’s algorithm shows its strength only when applied to biggest matrices, where each cell in the above formulae is considered to be another matrix – for whose computation the algorithm can be, recursively, used. In the case we are now considering — matrices of size 2^k \times 2^k — this recursion finally brings us back to 2 x 2 matrices and individual cells, and enables us to do the entire process of multiplication by using only Strasen’s algorithm. For big matrices, this is quicker and more efficient than using the standard method, since there are less multiplication flops which are, as well known, rather cumbersome.

After some frustrating programming and debugging, which made one really appreciate the worth of having studied some computer science, the algorithm took the following shape: (some additional line breaks were inserted to divide the lined defining recursive p_1, p_6 and p_7 into blocks that fit into the page.)

an even longer boring algorithm, and in Matlab code, too! cut away

Testing this algorithm for a few small cases (2^2 and 2^3) seems to indicate it works; at least it gives the same results as Matlab’s ‘standard’ process.

It should be noted that this algorithm is ‘dumb programming’ and would instantly raise loud cries of protest from any computer science major. Mathematically it is, of course, sound. The problem is that the algorithm does not check whether the initial matrices are, in fact, of size 2^k \times 2^k. If they are not, the algorithm will crash.

To compare the performance of this algorithm and Matlab’s standard algorithm (whatever that might be) we construct the following small programlet:

a short boring program redacted

This gives us the matrix t with the following results on time used by the two methods :

monotone results snipped away; Strassen bombs and takes 300 times as long, on the average, as standard.

It seems that 2^6 \times 2^6 or 64 \times 64 matrices are not big enough for Strassen’s algorithm to take effect. If we change the k [the power of 2] of the testing algorithm to 7 instead of 6 we get the following results in t:

more results disblogolated; Strassen takes some 3000 times longer than standard; a more aware person would have thought something might be wrong, but not I!

Still no improvement. Bigger matrices would probably even the odds and then, finally, make Strassen’s algorithm more efficient. That is, if Matlab didn’t switch to a variant of Strassen itself — what it would, most probably, do. Besides, trying to run the above algorith with 2^{10} \times 2^{10} or 1024 \times 1024 matrices did not end well, as Matlab went comatose and could only be reawakened using moderate violence.

* * *

Verdict: Too much linguistic bling; not enough mathematical savvy.

Wouldn’t return something like that today; don’t know if that is timidity or wisdom. (Representative lines from the other reports: rhetorical question “How do we extract the matrix Q out of the above ungodly mess?” and a statement on the constructed algorithm soundly failing to do what it was supposed to do: “This is clearly a problem.”)

Also, that Matlab-crashing used to happen a lot. (“Why, I’ll add one more zero and try again — hey, why’s the mouse not moving?”) As I haven’t used the program lately, I don’t remember enough to figure out now if my algorithm had some embarrassing flaw (“Also, there will be some Matlab exercises.” — “Er, what’s a maatlaab?”) or if my weaseling was, in fact, correct.

I am not going to dig into my folders, either, to find if I got the print-out of this back, and with what comments if I did. This just illustrates what I think is the result of… being so drunken on English that you return stuff like this to a poor, no doubt rather confused math professor. (“I’m a Finn; he’s a Finn; why is he doing this to me?”)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s