My research

A few of you have asked me recently about the topic of my PhD thesis. I am always happy to oblige!

The title was “On the Complexity of Matrix Multiplication” and it was concerned with properties of objects called Matrices (singular: matrix).

A matrix is an array of numbers, with a number of rows and columns. Below is an example of a 2 x 3 matrix:

image

A 2 x 3 matrix.

Predictably, a matrix is called square if the number of rows is the same as the number of columns.

Matrices are pretty important objects: they are used in all manner of disciplines such as quantum physics (states of particles are defined by a matrix), computing, probability, statistics, relativity and predicting the outcomes of games of Snakes and Ladders.

One important property is that they can be multiplied together. Multiplying two geometric transformations will result in the two things being done at the same time, fot example a reflection and a rotation.

Unfortunately for large matrices, the standard method for doing this is rather cumbersome, so a quicker method is necessary.

The measurement for the amount of time it takes computer to do a multiplication is called the exponent and for the standard method this has value 3, and lower is better. Due to the number of entries in a matrix, the lowest value it can be is 2.

Reducing it became a possibility when Volker Strassen found that you could turn the matrices into squares and chop them up into other squares- he showed that you could reduce the exponent to 2.81- and further advances were made until 1990 when the exponent stood at 2.375.

That’s where I came in- what I did was utilise the previous method and essentially do it again to show that you could make a shortcut and do the necessary calculations even quicker.

That didn’t work- but I had a hunch that it might work if I did it again- and it did, yielding the following result- a minor improvement but, at the time, a record.

image

It has since been beaten by Virginia Williams at Stanford University using similar methods, but not before a delayed write-up (I wasn’t well) meant that the result wasn’t made public until it had been Williams beat it (she only found my result by chance) resulting in one professor writing a long diatribe against me (which he subsequently withdrew when he found out the cause of the delay) and comments such as the below appearing in his blog:

image

The above comment is now immortalised in a pub quiz team name.

Alas, my algorithm is not useful at present because of technology limitations, but I am hopeful it can be used some time. But really, when has practical use ever concerned a mathematician? I was only ever in it for the pub quiz team name.

Advertisements
This entry was posted in Theology. Bookmark the permalink.

2 Responses to My research

  1. T-Bo says:

    Andy this is great. Fascinating to see what you achieved in academia. Were you tempted to continue? I don’t understand the maths at all but it makes a fascinating read. Why was the diatribe written – because someone thought you were trying to claim to be a record breaker or had copied her work?

  2. The Doctor says:

    I didn’t like the poor job security in academia so thought I shouldn’t stay. He wrote it because I hadn’t publicised it and people were criticising him for not giving me credit. It was a really weird time.

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