Category: Computer Science

Matrix multiplication is faster than you expect (part I)

Suppose we’re running a particle physics/neurobiology simulation, or solving some machine learning/data mining problem, and we need to do some linear algebra. Specifically, we want to multiply two real n \times n matrices A, B. To compute the i,j-th entry of the product we go along the ith row of A, multiplying entrywise with the jth column of B, so that for each entry of AB we perform n real multiplications (and n-1 real additions, but this makes no difference to the “average” number of operations needed, so we’ll be slack and gloss over such details until we formalize things in the next few sections). Since there are n^2 entries in the product, this gives a total of n^3 operations required to calculate the product, as one would intuitively expect. As a slightly unrealistic example, let us generously assume that our matrices are small, of dimension n \approx 10^5 (which incidentally is just outside the largest matrix size allowed by GNU Octave on my computer), then assuming the ability to perform 10^{10} operations a second on a “standard” PC processor, one matrix multiplication would take on the order of 10^5 seconds, or slightly over a day. In real-world applications such as high-performance computing or big data problems the dimension gets much bigger, so naive multiplication is still too slow, even given the extra processing power we gain by switching to supercomputers. Continue reading

Advertisements

Avian Flow: Continuum Boid Dynamics

I’m excited for this, if only because of the enormous amount of humorous nomenclature that will come of it. Ok, here we go.

Have you ever heard of Boids? Boids (‘Birds’ with a Brooklyn accent) refers to a certain type of algorithm for simulating the flocking of large numbers of animals – for example, the eponymous birds. The word refers both to the algorithm itself and to the individual elements being simulated, which are rendered onscreen and whose motion through simulated space evolves according to a set of three rules. The particular details of the algorithm may vary from implementation to implementation, but these three main features of the Boids’ are usually the same.

Boids, as entities, possess a position and a velocity, and obey the following physical principles:

  1. Alignment. Boids wish to conform to the flight paths of their neighbours, and so will rotate to align their own velocity with the average velocity of neighbouring boids which are sufficiently close.
  2. Cohesion. Boids like to fly in groups, and they like to be as close to the centre of the group as possible. For this reason they also steer towards the mean position of those sufficiently close neighbours.
  3. Separation. Boids don’t, however, like to collide, so they will actively avoid any of their neighbours that come too close.

If you want to have a look at an actual implementation and some wonderful, in-depth visualisations of all of these things, then you can do no better than this post over at Harry Brundage’s blog. Seriously, go over there and have a play. I’ll wait here.

Neat, huh? But why should we care? Why am I talking about boids? Well, the first thing that came into my head when I learned of boids was:

Why not make this a continuous system?

Continue reading

Quantum Cryptography

[Accompanying notes for Physsoc (University of Canterbury) seminar on 2/8/2013]

Cryptography consists of making and breaking methods to communicate information without third parties which are able to intercept communications being able to gain knowledge of this information.

1. Cryptography before Quantum Mechanics

In the traditional example Alice and Bob wish to communicate privately despite Eve (who wishes to know what Alice and Bob are communicating) being able to intercept their communications. However in reality the situations in which cryptography has been used is for spies when letters are being intercepted, for the military — especially after the invention of radio, and today on the internet when we access online bank accounts and complete other online transactions.

In order to do this Alice and Bob could try to disguise their message (for example invisible ink or microdots), or they can employ a cipher scheme. The problem with a disguised message is that if a third party discovers the method of hiding the message they can immediately read all following messages. A cipher can be seen as an invertible function mapping the plain text to the enciphered text. The recipient can then apply the inverse function to discover this message. (Note: Strictly speaking f does not have to be a function, f^{-1} needs to be a function so it gives a unique message that was sent however the enciphering process can give multiple possible encrypted messages from which one can be randomly chosen.)

However this seems to have the same disadvantage — as soon as the inverse function is discovered messages can immediately be read, so in general we use a function of both the message and a key.  Thus even if the function in question is known, without the key which can be regularly changed it may still be possible to maintain security. However as the next example will show security of the key is not sufficient as this may be derivable from the message.

Example 1: Substitution Cipher

Alice and Bob map each letter of the alphabet to another letter. As there are 26! such bijective mappings this is too many for Eve to go through in any reasonable time. However in the English alphabet not all letters are used in equal frequencies in normal text. Hence if we look at the statistical distribution of the various letters in a large section of cipher text, we can identify this with the statistical distribution of letters in normal English, thus allowing us to find the key (the specific bijection used). Also the frequency of combinations of two or more letters in consecutive order can be used. The English language (or any other natural language) only uses a tiny proportion of all possible sequences of characters, the unique properties of the subspace of character sequences can be used in breaking several encryption schemes.

So we also need a function such that there is no such method to determine the key that is implementable in a the length of time we require the message to be secure for given the computing power at the disposal of Eve.

Example 2: One Time Pad

For simplicity we write the message as a string of zeros and ones. As a key we have a random string of zeros and ones of equal length which we only use for this message and never reuse. Then we apply the AND operation (addition modulo 2) to the nth digits of the key and the message to give the nth digit of the encrypted message. The reason this is unbreakable is that given an encrypted message there is a key such that any message of the correct length could be encrypted to give this message. As the key is random and never reused we can not use the keys that would correspond to given messages to determine which is the actual key used, and hence the actual message sent.

The problem is this requires Alice and Bob to have met before in secret and have exchanged an equal amount of data to that which they will in the future wish to communicate, not to mention the added complexity of generating random numbers — which by definition can not be done algorithmically — all random number generators on computers without specific hardware that uses electronic noise or other physical phenomena to generate random numbers, are only using some algorithm to generate pseudorandom numbers. For application such as internet banking this is clearly not highly feasible.

However in the last century there was a revolution in cryptography — public key cryptography. There are two approaches to this. In this Alice and Bob both create a secret number, transmit partial information about this and use this to create a key known to both parties which can’t be created from the partial information. Continue reading