Jacobi-type Methods for Lattice Basis Reduction
Speaker:Prof. Sanzheng Qiao
Department of Computing and Software
McMaster University, Canada
Date & Time:24 Oct 2013 (Thursday) 15:30
Organized by:Department of Mathematics


Lattice basis reduction has a wide range of applications, such as mathematics, cryptography, wireless communication, and GPS, just to name a few. There are several notions of basis reduction. We propose a completely new approach to lattice reduction: Jacobi-type methods. A Jacobi method has a two dimensional workhorse. In the case of symmetric eigenvalue problem, the workhorse is the two dimensional symmetric eigenvalue decomposition. In our case, the workhorse is the Lagrange algorithm for two dimensional lattice reduction. While the basic idea behind our Jacobi-type methods is simple, the challenge is to prove its convergence and analyze its computational complexity. Jacobi method is attractive, because it is inherently parallel. In this talk, after introducing the background, we present our recent results on the Jacobi-type methods for lattice reduction, including the generic method, the modified methods, the convergence, the computational complexity, a parallel algorithm and its GPU implementation.


Sanzheng Qiao was born in Huangpu District, near People's Square, in Shanghai, China in 1945. He received the B.S. degree from Shanghai Teacher's University, Shanghai, China in 1966, and the M.S. degree in computer science and Ph.D. degree in applied mathematics from Cornell University, Ithaca, NY, in 1986 and 1987 respectively. He was an assistant professor of computer science at Ithaca College, Ithaca, NY from 1987 to 1988. From 1989 to 1993, he was an assistant professor in the Department of Computer Science and Systems at McMaster University, Hamilton, Ontario, Canada, and an associate professor from 1993 to 1999. He is now a professor in Department of Computing and Software at McMaster University. He is a faculty member of Software Quality Research Laboratory (SQRL) at McMaster University. His research interests include numerical linear algebra, distributed/parallel scientific computing, numerical methods for signal processing, and numerical software.