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

Por Francisco R. Villatoro, el 10 agosto, 2009. Categoría(s): Ciencia • Historia • Informática • Matemáticas • Mathematics • Noticias • Prensa rosa • Science ✎ 12

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 1The Computer Journal 4: 265-271, 1961, y «The QR Transformation—Part 2The 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].



12 Comentarios

  1. A mi me pareció un código muy interesante y lo apliqué en mi programación, pero no parece que en España lo use nadie. Al menos en Japón le tienen más afecto y hay más de 30 millones de usuarios de los códigos QR. Sigo pensando que es el mejor método para pasar información al móvil. Hace dos años, cuando presenté mi aplicación a inversores en Estados Unidos, mostrándoles los beneficios del QR code, me miraban escépticos y ahora lo está utilizando Adidas, Nike y hasta los McDonnald’s en sus ofertas en sus locales.

  2. Y yo me pregunto, ¿qué tiene que ver un código QR (Quick Response) con la descomposición QR de matrices (Q es una matriz ortogonal y R una triangular)?

  3. Gracias a todos por los comentarios. No he encontrado ninguna foto de John Francis en la web, ni siquiera en el congreso NA de Glasgow. Así que se me ocurrió la «pijada» de poner un código QR, que obviamente no tiene nada que ver ni con la descomposición QR (trabajo de Householder y otros, no de Francis) ni con el algoritmo de Francis para autovalores.

    No tiene nada que ver, o mucho, ya que es autorreferente, el url de la entrada, como muy bien ya notó MiGUi en #1, quizás sin ningún lector de códigos qr (aunque en #2 afirma que lo utilizó, ¿para confirmar su conjetura?), ya que el nombre del fichero de las imágenes en este blog explica la imagen (en inglés), básicamente para que los buscadores de Google sepan qué contiene y los lectores interesados también.

Deja un comentario