06080600

j

06080600 Khorramizadeh, M. Numerical experiments with the LLL-based Hermite normal form algorithm for solving linear Diophantine systems. Int. J. Contemp. Math. Sci. 7, No. 13-16, 599-613 (2012). 2012 Hikari Ltd, Ruse EN lattice basis reduction algorithm linear Diophantine systems Rosser's algorithm

http://www.m-hikari.com/ijcms/ijcms-2012/13-16-2012/index.html

Summary: We are concerned with the practical performance of the LLL-based Hermite normal form algorithm, proposed by {\it G. Havas, B.S. Majewski} and {\it K. R. Mathews} [Exp. Math. 7, No. 2, 125--136 (1998; Zbl 0922.11112)] (LLLHMM) when applied to solve linear Diophantine systems. We first compare the efficiency of the LLLHMM with the algorithm, named LDSSBR, based on the Rosser's idea. The numerical results show that for small problems, the bit length of the longest integer occurring during the execution of the LDSSBR (Bmax) and the computing time are less than those of the LLLHMM. As the size of the problem increases the gap between Bmax and the computing time of both algorithms reduces and for large problems Bmax and the computing time of the LLLHMM are less than those of the LDSSBR. Therefore, in sense of controlling the growth of intermediate results and the computing time for small problems the LDSSBR is more efficient while, for large problems the LLLHMM is more efficient. However, for all test problems the bit length of the maximum absolute value of the components of the particular solution and basis, obtained by using the LLLHMM is significantly less than those of the LDSSBR. Then, by presenting some tables of empirical results we justify the experimental conjecture that if the bit length of the components of the coefficient matrix and the right hand side vector of the Diophantine system are equal to k then the nearest integer to the bit length the maximum absolute value of the components of the particular solution and the basis obtained after an application of the LLLHMM is approximately $mk/(n - m)$, where $m$ denotes the number of equations and $n$ denotes the number of variables of the system.