THECOMPUTATIONOF
        EIGENVALUES AND EIGENVECTORS
        OFVERYLARGESPARSEMATRICES
                       by
             Christopher Conway Paige, B.Sc., B.E., Dip.N.A.
             London University Institute of Computer Science
                Thesis submitted for the degree of
                   Doctor of Philosophy
                   University of London
                     April 1971
                                              2
          Dedication
          To Fran¸coise
                                              3
          Acknowledgments
          The author is very grateful to his supervisor Dr. M.J.M. Bernal for his thoughtful
          guidance and encouragement. He would also like to thank his friends at the Institute
          of Computer Science for their help and discussions, and in particular he would like
          to thank Christine Fair, Mary Della-Valle, and Mrs. M. McCluskey for the excellence
          of their typing.
          2012 Addendum
          Chris Paige is also very grateful to Ivo Panayotov for LaTeXing the original thesis
          during 2011–2012 in order to provide this much improved version. He corrected errors
          and improved the format. Some extra ‘newpage’ commands have now been entered
          so that the pages of this version roughly correspond to those of the original.
                                              4
          Abstract
          Several methods are available for computing eigenvalues and eigenvectors of large
          sparse matrices, but as yet no outstandingly good algorithm is generally known. For
          the symmetric matrix case one of the most elegant algorithms theoretically is the
          method of minimized iterations developed by Lanczos in 1950. This method reduces
          the original matrix to tri-diagonal form from which the eigensystem can easily be
          found. The method can be used iteratively, and here the convergence properties and
          different possible eigenvalue intervals are first considered assuming infinite precision
          computation. Next rounding error analyses are given for the method both with
          and without re-orthogonalization. It is shown that the method has been unjustly
          neglected, in fact a particular computation algorithm for the method without re-
          orthogonalization is shown to have remarkably good error properties. As well as
          this the algorithm is very fast and can be programmed to require very little store
          compared with other comparable methods, and this suggests that this variant of the
          Lanczos process is likely to become an extremely useful algorithm for finding several
          extreme eigenvalues, and their eigenvectors if needed, of very large sparse symmetric
          matrices.