Abstract:
This article presents a way to significantly increase the performance of lattice basis reduction algorithms (hundredfold to three hundred times) by replacing recursive orthogonalization Gram–Schmidt algorithm by parallel QR algorithms. The paper contains a comparison between implementation of serial column-major Gram–Schmidt and parallel algorithms on NVIDIA CUDA GPU framework using Givens rotation, multicore CPU Intel Math Kernel library, and Householder transformation.