Efficient Parallelization of Lanczos Type Algorithms

Ilya Popovyan

Paper 2011/416 Original: eprint.iacr.org/2011/416 ↗

Efficient Parallelization of Lanczos Type Algorithms

Ilya Popovyan

Abstract

We propose a new parallelization technique for Lanczos type algorithms for solving large sparse linear systems over finite fields on mesh cluster architecture. The algorithm computation time scales as $P^{-1}$ on $P processors, and the communcation times scales as $P^{-1/2}$ for reasonable choice of $P$.

Metadata

Available format(s): PDF
Publication info: Preprint.
History: 2011-08-05: last updated; 2011-08-05: published
Short URL: https://ia.cr/2011/416
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2011/416,
      author = {Ilya Popovyan},
      title = {Efficient Parallelization of Lanczos Type Algorithms},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/416},
      year = {2011},
      url = {https://eprint.iacr.org/2011/416}
}