Francis’s algorithm

Abstract. John Francis’s implicitly shifted QR algorithm turned the problem of matrix eigen-value computation from difficult to routine almost overnight about fifty years ago. It was named one of the top ten algorithms of the twentieth century by Dongarra and Sullivan, and it deserves to be more widely known and understood by the general mathematical community. This article provides an efficient introduction to Francis’s algorithm that follows a novel path. Efficiency is gained by omitting the traditional but wholly unnecessary detour through the basic QR algorithm. A brief history of the algorithm is also included. It was not a one-man show; some other important names are Rutishauser, Wilkinson, and Kublanovskaya. Francis was never a specialist in matrix computations. He was employed in the early computer indus-try, spent some time on the problem of eigenvalue computation and did amazing work, and then moved on to other things. He never looked back, and he remained unaware of the huge impact of his work until many years later. 1. INTRODUCTION.