Pacific national university Main page Bulletin of Pacific national university

UDC 519.644.7+511.9

© V. A. Bykovskii, S. V. Gassan, 2011

ALGORITHM FOR CALCULATING LOCAL MINIMA OF INTEGRAL LATTICES AND ITS APPLICATIONS

In the paper we consider the algorithm for finding local minima of integral lattices. We discuss the details of the software implementation and the ways of optimization. We also propose the modification of the algorithm allowing to calculate elliptic minima and consider the application of these algorithms to computing parameters from the theory of multidimensional qadrature formulas.

Keywords: integral lattices, local minima, reduced quadratic forms.

References:

  1. Korobov N. M. O priblizhennom vychislenii kratnykh integralov // Dokl. AN SSSR. 1959. - T. 124. - N. 6. - S. 1207-1210.
  2. Bykovskiy V. A. Algoritm vychisleniya lokal`nykh minimumov reshe-tok. // Dokl. RAN. - 2004. - T. 399, N.5. - S. 587-589.
  3. Voronoy G. F. Sobranie sochineniy. - T. 1. - Kiev: 1952.
  4. H. Minkowski. Generalisation de la theorie des fractions continues, Ann. de lEcole Norm. (3), 13:2 (1896), 41-60.
  5. H. Cohen. A Course in Computational Algebraic Number Theory, Graduate Texts in Math., vol. 138, Springer-Verlag, Berlin Heidelberg, 1993. (Algorithm 1.3.14.).
  6. B. Vallee. Une approche g?om?trique des algorithmes de r?duction en petite dimension, Thesis, Univ. of Caen, 1986.
  7. A. K. Lenstra, H. W. Lenstra and L. Lov?sz. Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515-534.
  8. Ryshkov S. S. K teorii privedeniya polozhitel`nykh kvadratichnykh form po Ermitu-Minkovskomu, Issledovaniya po teorii chisel // 2, Zap. nauchn. sem. LOMI, 33, Nauka, L., 1973. - S. 37-64.
  9. U. Fincke and M. Pohst. Improved methods for calculating vectors of short length in a lattice, including a complexity analysis, Math. Comp. 44 (1985), 463-471.
  10. http://www.shoup.net/ntl/
  11. http://www.mcs.anl.gov/research/projects/mpi/

Download Download article (224.1 Kb)

Сontents Сontents