An efficient parallel block-reduction algorithm

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

6 Scopus citations

Abstract

In this paper, we present a new parallel block-reduction algorithm for reducing lattice bases which allows the use of an arbitrarily chosen block-size between two and n where n denotes the dimension of the lattice. Thus, we are building a hierarchy of parallel lattice basis reduction algorithms between the known parallel all-swap algorithm which is a parallelization for block-size two and the reduction algorithm for block-size n which corresponds to the known sequential lattice basis reduction algorithm. We show that even though the parallel all-swap algorithm as well as the parallel block-reduction algorithm have the same asymptotic complexity in respect to arithmetic operations in theory, in practice neither block-size two nor block-size n are a priori the best choices. The optimal block-size in respect to minimizing the reduction time rather depends strongly on the used parallel system and the corresponding communication costs.

Original languageEnglish
Title of host publicationAlgorithmic Number Theory - 3rd International Symposium, ANTS-III 1998, Proceedings
EditorsJoe P. Buhler
Pages323-337
Number of pages15
DOIs
StatePublished - 1998
Event3rd International Symposium on Algorithmic Number Theory, ANTS 1998 - Portland, United States
Duration: 21 Jun 199825 Jun 1998

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1423
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference3rd International Symposium on Algorithmic Number Theory, ANTS 1998
Country/TerritoryUnited States
CityPortland
Period21/06/9825/06/98

Fingerprint

Dive into the research topics of 'An efficient parallel block-reduction algorithm'. Together they form a unique fingerprint.

Cite this