TY - GEN
T1 - An efficient parallel block-reduction algorithm
AU - Wetzel, Susanne
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1998.
PY - 1998
Y1 - 1998
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84919877298&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84919877298&partnerID=8YFLogxK
U2 - 10.1007/bfb0054872
DO - 10.1007/bfb0054872
M3 - Conference contribution
AN - SCOPUS:84919877298
SN - 3540646574
SN - 9783540646570
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 323
EP - 337
BT - Algorithmic Number Theory - 3rd International Symposium, ANTS-III 1998, Proceedings
A2 - Buhler, Joe P.
T2 - 3rd International Symposium on Algorithmic Number Theory, ANTS 1998
Y2 - 21 June 1998 through 25 June 1998
ER -