Honoris Causa: John Francis, Inventor of the QR Algorithm
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 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!Follow @telescoper