John Francis y uno de los 10 algoritmos más importantes del siglo XX

Dibujo20090809_qr_code_url_this_pageEste año se cumplen 50 años del desarrollo del algoritmo de Francis para el cálculo de autovalores de matrices desarrollado por John Francis en octubre de 1959. En el año 2000, ningún experto mundial en métodos numéricos había visto en persona a John Francis, era como un fantasma. Gene Golub, uno de los grandes genios de los métodos numéricos durante el s. XX, y Frank Uhlig decidieron encontrar a la persona detrás del nombre “John Francis.” Al final, ambos juntos lograron encontrarlo en 2007, con 74 años. Francis no tenía ni idea de la repercusión de su algoritmo. Golub nos lo contó en Gene H. Golub, “John Francis, Co-Inventor of QR,” NA Digest V. 07, #34, 19 Aug 2007. Gene Golub logró encontrar a J.G.F. Francis gracias a una búsqueda intensa en Google (cuyo algoritmo PageRank utiliza el algoritmo QR de Francis) y a los recuerdos personales del, ya fallecido, Erin Brent. Golub murió en 2007. Uhlig cogió el testigo y decidió organizar un minisimposio en honor de Francis en la XXIII Biennial Conference on Numerical Analysis, June 23rd-26th 2009, en Glasgow, donde Francis impartió una conferencia invitada contando su historia y la historia de su algoritmo. Nos lo contó y anunció Frank Uhlig, “John Francis of QR found,” NA Digest, V. 09, #13, 25 Mar 2009.

John Francis nació en 1934.  En 1954 se puso a trabajar en la empresa National Research Development Corp (NRDC) donde asistió a cursos de computación impartidos por Christopher Strachey, quien le animó a estudiar una carrera universitaria. Se matriculó en Cambridge durante los cursos 1955 y 1956, pero no llegó a acabar su carrera universitaria. Tras su fallido paso por la universidad volvió a NRDC como asistente de Strachey hasta 1961. Junto a él desarrolló el algoritmo más utilizado para el cálculo de autovalores de matrices, el algoritmo QR de Francis, así como importantes avances en el método iterativo del gradiente conjugado para resolver sistemas lineales. Tras 1961 trabajó para varias empresas de lo que hoy llamaríamos informática, aunque nunca más en temas relacionados con el cálculo numérico.

Los artículos originales de Francis son J.G.F. Francis, “The QR Transformation A Unitary Analogue to the LR Transformation—Part 1,” The Computer Journal 4: 265-271, 1961, y “The QR Transformation—Part 2,” The Computer Journal 4: 332-345, 1962. El algoritmo QR de Francis fue desarrollado simultáneamente y de forma independiente en la Unión Soviética por Vera Kublanovskaya. Más detalles sobre la historia de este algoritmo en Gene Golub, Frank Uhlig, “The QR algorithm: 50 years later its genesis by John Francis and Vera Kublanovskaya and subsequent developments,” IMA Journal of Numerical Analysis 29:467-485 June 8, 2009.

“Los grandes algoritmos son como la poesía de la computación,” Francis Sullivan.

El listado de los 10 algoritmos más importantes de la historia (del s. XX) los podéis encontrar en “Algorithms for the Ages,” Science 287: 799, 4 Feb 2000. Los editores que se encargaron de confeccionar esta lista fueron los geniales Jack Dongarra y Francis Sullivan. Muchas fuentes se hicieron eco de este listado. A mí me gusta Barry A. Cipra, “The Best of the 20th Century: Editors Name Top 10 Algorithms,” SIAM News 33, May 16, 2000 [pdf gratis].

Anuncios