| On Randomized Lanczos Algorithms (1997) | |||||||||||||||||
Abstract | |||||||||||||||||
| Las Vegas algorithms that are based on Lanczos's method for solving symmetric linear systems are presented and analyzed. These are compared to a similar randomized Lanczos algorithm that has been used for integer factorization, and to the (provably reliable) algorithm of Wiedemann. The analysis suggests that our Lanczos algorithms are preferable to several versions of Wiedemann's method for computations over large fields, especially for certain symmetric matrix computations. 1 Introduction Sparse or structured systems of linear equations over fields arise in a variety of applications; for example, many methods for integer factorization require the solutions of large, sparse systems over finite fields. Several algorithms have been proposed for this computation over the years. Until recently, the algorithm of Wiedemann [15] was the only such algorithm known to be provably efficient and reliable for computations for arbitrary fields --- particularly, over small finite fields. However, o... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||