Archive for Sanjeev Bhaskar

Honoris Causa: John Francis, Inventor of the QR Algorithm

Posted in The Universe and Stuff with tags , , , , , , on July 18, 2015 by telescoper

It’s been yet another busy week, trying to catch up on things I missed last week as well as preparing for Thursday’s graduation ceremony for students from the School of Mathematical and Physical Sciences. At this year’s ceremony, as well as reading out the names of graduands from the School of which I am Head, I also had the pleasant duty of presenting mathematician John G.F. Francis for an Honorary Doctorate of Science.

The story of John Francis is a remarkable one which I hope you will agree if you read the following brief account which is adapted from the oration I delivered at the ceremony. It was a special pleasure to asked to present this award because you could never wish to meet a more modest or self-effacing individual. Indeed, when I asked him at the lunch following the ceremony, what he thought of the work for which he had been awarded a degree honoris causa he shrugged it off, and said that he thought it was an obvious thing to do and anyone else could have done it had they thought of it. Maybe that’s true in hindsight, but the point is that “they” didn’t and “he” did. The fact that it has taken over fifty years for him to be recognized for something so important is regrettable to say the least, but I am glad to have been there to see him justifiably honoured. Great thanks are due to Drs Omar Lakkis and Anotida Madzvamuse of the Department of Mathematics at the University of Sussex for bringing his case to the attention of the University as eminently suitable for such an honour. So impressed were the graduating students that a number shook his hand as they passed him on the stage during their own part of the ceremony. I’ve never seen that happen before!

John Francis receiving his Honorary Doctorate from the Chancellor, Sanjeev Bhaskar.

John Francis receiving his Honorary Doctorate from the Chancellor, Sanjeev Bhaskar.

John Francis is a pioneer in the field of mathematical computation where his name is more-or-less synonymous with the so-called “QR algorithm”, an ingenious factorization procedure used to calculate the eigenvalues and eigenvectors of linear operators (represented as matrices).

Before I go on it’s probably worth explaining that the letters ‘QR’ don’t stand for any words in particular. The algorithm involves decomposing the matrix whose eigenvalues are required into the product of an orthogonal matrix (which Francis happened to call Q) and an upper-triangular matrix (which Francis happened to call R). In fact in his original manuscript, the orthogonal matrix was called O but it was subsequently changed to avoid confusion with ‘O’. At any rate, certainly has nothing to do with research funding!

The mathematics and physics graduates in the audience were probably well aware of the importance of eigenvalue problems, which crop up in a huge variety of contexts in these and other scientific disciplines, from geometry to graph theory to quantum mechanics to geology to molecular structure to statistics to engineering; the list is almost endless. Indeed here can be few people working in such fields who haven’t at one time or another turned to the QR algorithm in the course of their calculations. I know I have, in my own field of astrophysics! It has become a standard component of any theoretician’s mathematical toolkit because of its numerical stability.

The algorithm was first derived by John Francis in two papers published in 1959 and, independently a couple of years later, by the Russian mathematician Vera Kublanovskaya (who passed away in 2012). You can find both the papers online: here and here. Interestingly, the problem that John Francis was trying to solve when he devised the QR algorithm concerned the “flutter” or vibrations of aircraft wings.

But it is in the world of the World Wide Web that the QR algorithm has had perhaps its greatest impact. Many of us who were using the internet in 1998 were astonished when Google arrived on the scene because it was so much faster and more effective than all the other search engines available at the time. The secret of this success was the PageRank algorithm (named after Larry Page, one of the founders of Google) which involved applying the QR decomposition to calculate numerical factors expressing the relative “importance” of elements within a linked set (such as pages on the World Wide Web) measured by the nature of their links to other elements. The QR algorithm is not the only technique exploited by Google, but it is safe to say that it is what gave Google its edge.

The achievements of John Francis are indeed impressive, even more so when you read his biography, for he did all this pioneering work in numerical analysis without even having an undergraduate degree in Mathematics.

John Francis actually left school in 1952 and obtained a place at Christ’s College, Cambridge for entry in 1955, after two years of National Service during which he served in Germany and Korea with the Royal Artillery. On leaving the army in 1954 he worked for a time at the National Research Development Corporation which was set up in 1948 by the Attlee government in order to facilitate the transfer of new technologies developed during World War 2 into the private sector in an effort to boost British commerce and industry. Among the priority areas covered by the NRDC was computing, and it was there that John Francis cut his teeth in the field of numerical analysis. He went to University as planned but did not complete his degree, instead returning to the NRDC in 1956 after less than a year of study. It was while working there in 1958 and 1959 that he devised the QR algorithm.

He left the NRDC in 1961 to work at Ferranti Ltd after which, in 1967, he moved to Brighton and took up a position at the University of Sussex in the Laboratory of Experimental Psychology, helping to devise a new computer language for running experiments. He left the University in 1972 to work in various private sector computer service companies in Sussex. He has now retired but still lives locally, in Hove.

Having left the field of numerical analysis in the 1960s, John Francis had absolutely no idea of the impact his work on the QR algorithm had had, nor was he aware that it was widely recognized as one of the Top Ten Algorithms of the Twentieth Century, until he was traced and contacted in 2007 by the organizers of a mini-symposium that was being planned to celebrate 50 years of the QR algorithm; he was the opening speaker at that meeting in Glasgow when it took place in 2009.

More recently still, in 2011, after what he describes as “sporadic” study over many years, John Francis was awarded an undergraduate degree from the Open University, 56 years after he started one at Cambridge.  I am very glad that there was no similar delay in him proceeding to a Doctorate!

Advertisements

Rites of Passage

Posted in Brighton, Education with tags , , , on January 28, 2014 by telescoper

Just back home from the drinks reception that followed today’s Winter Graduation Ceremony at the University of Sussex at the Dome, in Brighton. And a very nice event it was too!

The Winter Graduation ceremony is primarily taken up with postgraduate degrees, and within School of Mathematical and Physical Sciences the largest proportion of those are in Mathematics, especially in the MSc courses in Financial Mathematics and Corporate and Financial Risk Management on which we have a large number of overseas students, e.g. From China. My first graduation ceremony as Head of School therefore presented me with some pronunciation challenges as I read out the names of the graduands. I was a bit nervous beforehand, not because I’m afraid of making a fool of myself but because these days everything is captured on video for posterity and I didn’t want to ruin anyone’s record of their Big Day. I practised quite a lot actually, and think it was OK.

I am always impressed at students who have the courage to travel halfway around the world to study in a foreign land. Graduation is a rite of passage for all students, but it must be of even greater significance for students from abroad.

I’ve attended graduation ceremonies at a number of other universities, and the big difference with Sussex is how much less formal it is. A great deal of credit for that must go to the Chancellor, the brilliantly funny and approachable Sanjeev Bhaskar, who ran the show in inimitable style. He also has a lovely head of hair.

Sanjeev always had a word with the graduands as they crossed the stage, often a hug, and very allowed them to take a selfie, once sitting in the Chancellor’s chair! I found it all very amusing, which helped me relax before my turn at the podium with the list of names. I’ve sat through a large number of dull and stuffy graduation ceremonies in my time, and much prefer the Sussex style!

Also graduating with top marks in our MSc in Cosmology was Mateja Gosenca, who is now my PhD student. Here we are at the drinks party after the graduation ceremony; Mateja is looking very happy holding her certificate as winner of the Sir William McCrea Prize for the best student on the MSc programme!

That one was taken with my Blackberry; here’s a much nicer version taken with a proper camera:

Mateja_again