Wednesday, June 3, 2015

On Matrix Inversion in Python

In the introductory programming course that I lecture, the big programming project that I set for the students involved writing a number of matrix operations in pure Python (that is, using built-in functions only - I specifically disallowed the use of any imported modules like NumPy). Transposition and matrix multiplication are fairly simple to do, but the challenge is in writing a function to invert a matrix.

Of course, Gauss-Jordan elimination (which should be covered in any first year algebra course) is one of the easier ways to do this. I wrote a fairly long but simple-to-understand function to give out to the students as a model solution at the end of the project, but I was wondering, how short could a working matrix inversion function be?

I came up with the function below, complete with partial pivoting, which seems to work correctly. It could probably be even shorter, but I think I achieved what I set out to do:

The input argument A is simply a nested list, such as
    A = [[1,2,3],[1,5,9],[7,5,2]]

Line 3 simply augments the matrix with the identity matrix. The for loop on line 4 loops through each row, and sets the element on the main diagonal to 1, and every element above and below that element to zero. This happens in three steps. The first step, on line 5, is a simple pivoting step. It sorts all of the remaining rows such that the current row will be divided by the number with the largest possible magnitude (to avoid division by zero, and improve the accuracy if the matrix contains very small numbers). The second step (line 6) is to divide each element in the row by the element on the main diagonal, leaving a 1 on the main diagonal. The third step (line 7) is a little more complicated. For each row that is not the current row, we subtract the current row multiplied by the element in the column index equal to the index of the current row. This will set each element in the current column to zero, except for the element in the current row, which remains 1.

The net result is that the left hand side of the augmented matrix becomes the identity matrix, while the right hand side becomes the inverse. All that's left is to separate the two, and return the inverse. This happens on line 8.

I don't know who would find this post useful, because it's better to just use numpy, but it is certainly a fun exercise.

If you enjoyed this post, then don't forget to like, tweet, +1, or upvote on reddit. If you have any questions, comments or complaints, post them using the form below.
. . . . . . . . . . . . . . . . . . . . . . . .

Tuesday, September 2, 2014

On My 13 Favourite Pieces of Metal Music

The music I listen to falls mainly into the genres of metal and classical music. A while ago, I put together a list of my 13 favourite pieces of classical music, so I decided it was about time to put together a list of my favourite metal music. Funnily enough, I find that classical music gets me worked up, and if I want to relax, no other music works quite as well as metal. I'm not very good at having favourites, so I should probably point out that there may be some more deserving songs out there that were accidentally overlooked, and my favourites change from day to day. However, these are the ones that I'd have to consistently include near the top of a list like this, but they are in no particular order. Once again, I have limited myself to one song per artist, and I have not listed songs that have made lists on this blog before.

    1. Moonsorrow - Raunioilla

Moonsorrow is my all-purpose music. No matter what mood I'm in, I'm in the mood for Moonsorrow. It's my first choice when I have to concentrate on work, or when I want to sit back and relax, or when I'm stressed, or sad, or really happy.

    2. Rhapsody of Fire - Queen of the Dark Horizons

Rhapsody of Fire's album Rain of a Thousand Flames is considered a filler album, as it only plays a small side role in the epic story they tell through their music. Still, it contains some of their best work, and Queen of the Dark Horizons is easily my favourite song of theirs. It is a perfect mix of symphonic and power metal, and I love every second of its 13 and a half minutes.

    3. Cradle of Filth - Nymphetamine (Fix)

My brother went through a phase where he listened to nothing but Cradle of Filth. Musically, I think they are brilliant, but I never liked Dani Filth's screaming. With exposure though, I did grow accustomed to it eventually. The one song that stood out was Nymphetamine (perhaps because Liv Kristine sings a large portion of the song), from the album of the same name. The song appears twice on the album, but the first version (the overdose) has a mismatched intro and outro which just don't fit in with the rest of the song. For that reason, I prefer just the fix.

    4. Deathstars - Razor End

While I had heard a little of the Deathstars' music before I met my girlfriend, I had never heard Razor End. We'd been dating for just a couple of weeks when she had my taste in music completely figured out. She burned me a CD, which had this song on. It's a pity it's not on any Deathstars album, because I feel it's easily their best work. Four and a half years later, it was still one of the easiest songs to choose when I started putting together this list.

    5. Anathema - Eternity, Part I

I've always had a taste for depressing doom metal, and that's what led me to Anathema. I enjoy almost all of Anathema's music, from their work in the early 90's, up to their latest albums. Listening to all of their albums in order and hearing the progression in style from doom metal to through to alternative rock is a fascinating experience in itself. Eternity, Part I is the first of three parts, and is written in a rather heavy doom metal style. The second part is a soft instrumental piece, and the third part closes off the first with a more progressive style, and cleaner vocals. I encourage you to listen to all three parts, but the first is definitely my favourite.

    6. In Flames - Come Clarity

In Flames is a band I have mixed feelings about. There are many of their songs that I thoughroughly enjoy, and then there are others that I cannot stand. Come Clarity is one of their softer songs, and I'm not sure what it is about the song that makes me love it so much.

    7. Wintersun - Death and the Healing

There are a couple songs from Wintersun which were strong contenders for this list. Beautiful Death was probably at the top, but it has already been listed on this blog as part of the soundtrack for the end of the world. Instead, I chose Death and the Healing. The slower pace and clean vocals make the song really stand out from the melodic black metal that makes up the rest of the album.

    8. Metallica - No Leaf Clover

When Metallica reached 30 years old, I compiled a list of my 30 favourite Metallica songs. Of them, 27 were released in the first 15 years of their career, and only 3 in the second 15 years. Also, I really don't like live music. It's rather funny then that my absolute favourite Metallica song was only released in the band's 19th year, and only ever as a live recording. I think it has something to do with the symphonic elements. I just wish there was a studio recording of the song.

    9. Nightwish - Phantom of the Opera

For a long time, Nightwish was my favourite band. For the last few years, however, there just seems to be something missing from their music (I wonder what it could be?) Even though it's not an original song, Phantom of the Opera seems to epitomise everything I loved about the band when they were at the peak of their career.

    10. Lordi - It Snows in Hell

The piano intro to this song is really simple to pick up and play, and really catchy, and I'm constantly getting the chorus stuck in my head. There's also something about the guitar solo that makes me think of a lazy Sunday afternoon.

    11. Bathory - The Lake

Although the album Blood on Ice was written in the late 80's, it wasn't released because the band were worried that it was too different to any of their other music. At the time, Bathory was known for their fast-paced black metal. Through the first half of the 90's, they changed their style, and began to define the Viking metal genre. In 1996, the band finally decided that they were ready to releace Blood on Ice. The Lake was the first song on the album that I heard, and remains my favourite to this day.

    12. Therion - To Mega Therion

Therion is the metal band that has experimented (mostly successfully) with more styles than any other band I have heard. To Mega Therion is from their album Theli, which was the first album to drop their death metal roots entirely. To Mega Therion features a full orchestra and choir, interspersed with raspy male vocals and catchy guitar and keyboard solos.

    13. Green Carnation - Light of Day, Day of Darkness

Yes, this song (if it can be called that) is just over an hour long. When I first heard about it, I expected it to be drawn out and repetitive, but it is far from it. The style and tempo of the music varies throughout the song, so that it easily maintains my interest for the full hour. I once heard a shortened version in which the song had been cut to ten minutes, and even though the editing had been done extremely well, and the transitions fitted in perfectly, I found that the song was seriously lacking. The full hour needs to be heard in one go. In my opinion, not a single second can be cut out.

Legal notice: I obviously don't claim to own any of the songs or videos in this post. Copyrights belong to the respective publishers.

If you enjoyed this post, then don't forget to like, tweet, +1, or upvote on reddit. If you have any questions, comments or complaints, post them using the form below.
. . . . . . . . . . . . . . . . . . . . . . . .

Wednesday, July 9, 2014

On Rubik's Cube

I love Rubik's cube. It's a puzzle that many people associate with intelligence, mathematical ability, and good problem solving skills, but being able to solve it actually has nothing to do with any of those. The only things you need are basic pattern recognition and muscle memory - both of which everyone has anyway.

    1. My first cubes

My first Rubik's cube was even older than I am. My dad bought two of them (one with standard colours, and one with pictures of fruit) some time in the early 80's when they first became popular, together with a short book explaining how to solve them. I found the book in 1996, shortly after we'd moved house. I asked my dad about it, and he found the two cubes for me. Not wanting to cheat, I scrambled one and tried solving it myself. It didn't take long to figure out how to solve one side, but I quickly realised that any turn inevitably messed up four sides, got frustrated, and moved on.

I came back to them a couple years later. This time, I actually tried reading the book. The first chapter was all about the internal mechanism, and how to take the cube apart. Naturally, I stopped reading there and did exactly that. I took them both apart, and put them back together in a solved state, and began to look at how various turns affected the faces. Whenever I got stuck in a position that I couldn't solve, I would take the cube apart, and put it back together. After a while, the core of one of the cubes broke while I was taking it apart. Having made very slow progress, and having lost a cube, my 12 year old brain decided it had more interesting things to do, so I moved on.

    2. Solving the damn thing

Once again, I came back the the cube a few years later. I think I was about 17 years old this time, and far more patient. I only had the cube with the fruit stickers left, so I had to be more careful. I decided to read the book, and I approached it the same way I would approach a school text book. I took a notepad and a pencil, and began to take notes.

The book described a very simple layer-by-layer method for solving the cube. You would start by inserting the four edges on the top face, and then execute a simple algorithm until they cycled into the correct positions. Then you would insert the four corners of that face, then the four edges of the middle layer. At this point, the top two layers of the cube were solved. To finish the last layer, you had to switch some corner pieces in the bottom layer to get them in the correct position, then execute an algorithm over and over until they were oriented correctly. Then, you would execute an algorithm to cycle the last four edges, until they were in the correct position, and finally you would execute one of three algorithms to flip them into the correct orientation. The book claimed that the method required an average of about 120 moves to solve the cube. There were a total of nine algorithms to learn, and it only took a couple of days to memorise them all (it's surprisingly easy if you just let muscle memory take over).

The catch was the centres. The book assumed that the cube had stickers with a solid colour, but my cube had little pictures of fruits. All of them would point the same direction except for the centres. I later learned that a cube like this is called a supercube, and some people draw arrows (or buy stickers with arrows) to turn their Rubik's cubes into supercubes. I was not content having my centres pointing the wrong way, so I sat down and figured out a couple of algorithms myself that would allow me to orient five of the six centres while solving the cube. I noticed that a couple of the algorithms I already knew rotated one or two centres if I repeated them three times, and with that, I could solve the cube, centres included.

Solving a Rubik's cube is a very relaxing task. It takes very little brain power, and is actually very meditative. Apart from occasionally glancing down to see which algorithm you need to execute next, you don't even really have to watch what you're doing. I used to solve my cube several times a week, just to meditate and relax.

    3. Moving on: new Cubes and new methods

My fruit cube lasted a surprisingly long time. After several years, it began to lock up occasionally. A couple years after that, pieces began to pop out every now and then. By late 2012, the pieces became so loose that it reached a stage where it would lock up on almost every turn, and it became almost impossible to solve without the whole thing exploding in my hands. I needed a new cube, so I bought one: a cheap Chinese cube from a flea market stall. The stickers lasted less than two weeks, and it was less than a month before one of the edges broke in half.

It was then that I decided to take things seriously. I went online and did some research, and discovered the fascinating world of speedcubing. I discovered that the world record at the time was less than six seconds, and that more than a thousand people around the world can solve a Rubik's cube in under fifteen seconds almost all the time! It put my two and a half minutes to shame.

I found out what makes of cube were actually considered good quality, and found a stickerless DaYan GuHong on sale. While waiting for my new cube to arrive (it took two months, thanks to a useless Postal service), I found a Rubik's 2x2 cube in a local toy store. I could solve it by adapting the 3x3 method, but it felt very slow and inefficient. I learnt to solve it using the Ortega method, which is a much faster method specially developed for 2x2 cubes, which is also fairly light on algorithms (you actually only need two of them, but learning up to eleven makes things faster).

Conveniently, my GuHong arrived the day before I left for America to present a paper a conference. A 15 hour plane flight is absolutely perfect for learning a new method. I made a short cheat sheet with the algorithms for the ZZ method, and between the two plane flights, I managed to memorize them.

    4. Speedcubing: attempt #1

Last month, a toy store near my girlfriend's house held a Rubik's cube competition. When I had first looked in 2013, there were only six South Africans ranked by the World cube Association, and speedcubing in the country seemed pretty much non-existent. I was fairly surprised to see an actual competition. I checked the World Cube Association website, only to see that the first official competition had been held a few months before, and more than thirty people had attended, two of whom had managed to set times under fifteen seconds.

It led me to find, a South African online store that stocks a range of the world's leading speed cube brands. I told myself that if I could solve my cube ten times with an average time less than 90 seconds (a minute faster than a year before), then I would allow myself to buy a new cube. I made it, but only just. In ten solves, my best time was 1:22, with an average of 1:29.8.

I ordered my new cube, a DaYan ZhanChi (since my stickerless GuHong is technically not competition legal), as well as a new 2x2 (my Rubik's brand one had a cracked core), and a 4x4 cube. With these new cubes, together with a couple of key rings, I can officially say that I have begun a bit of a collection.

I thoroughly enjoyed my first competition. By some miracle, I actually won the 2x2 category with an average of just over 16 seconds (my five solves took 13, 15, 15, 18 and 32 seconds). In the 3x3 category, I came nowhere near the winning average of 45 seconds. My best time was 53 seconds, and I averaged just over a minute.

    5. Next goal: An official WCA ranking

There's going to be an official WCA ranking event in Johannesburg on 23 November, and one in Cape Town on 30 November. This leaves me four and a half months to practice and get my times down. My goal is to set at least one time less than 30 seconds at that event. I'm improving fairly quickly. As of 30 June, my average time over 100 timed solves was 1:15.62. By 8 July, my average time over 100 solves had dropped to 57.93 seconds, and my current personal best is 42.65 seconds. 30 seconds may seem ambitious, but I'm fairly confident that I will be able to do it.

If you enjoyed this post, then don't forget to like, tweet, +1, or upvote on reddit. If you have any questions, comments or complaints, post them using the form below.
. . . . . . . . . . . . . . . . . . . . . . . .