Parallel Block Lanczos for solving large binary systems

Date

2006-08

Journal Title

Journal ISSN

Volume Title

Publisher

Texas Tech University

Abstract

The Lanczos algorithm is very useful in solving a large, sparse linear system A x = y and then finding vectors in the kernel of A. Such a system may arise naturally through number factoring algorithms for example. In this thesis, we present a variant of the binary Lanczos algorithm that directly finds vectors in the kernel of A without first solving the system. The number factoring algorithms ultimately require us to find such vectors. Our adaptation combines ideas of Peter Montgomery and Don Coppersmith. We also discuss implementation issues, including parallelization.

Description

Citation