1 | /* emacs edit mode for this file is -*- C++ -*- */ |
---|

2 | #ifndef CF_HNF_H |
---|

3 | #define CF_HNF_H |
---|

4 | |
---|

5 | /*BEGINPUBLIC*/ |
---|

6 | |
---|

7 | /** |
---|

8 | * |
---|

9 | * The input matrix A is square matrix of integers |
---|

10 | * output: the Hermite Normal Form of A; that is, |
---|

11 | * the unique m x m matrix whose rows span L, such that |
---|

12 | * |
---|

13 | * - lower triangular, |
---|

14 | * - the diagonal entries are positive, |
---|

15 | * - any entry below the diagonal is a non-negative number |
---|

16 | * strictly less than the diagonal entry in its column. |
---|

17 | * |
---|

18 | * @note: uses NTL |
---|

19 | * |
---|

20 | **/ |
---|

21 | |
---|

22 | CFMatrix* cf_HNF(CFMatrix& A); |
---|

23 | |
---|

24 | /** |
---|

25 | * performs LLL reduction. |
---|

26 | * |
---|

27 | * B is an m x n matrix, viewed as m rows of n-vectors. m may be less |
---|

28 | * than, equal to, or greater than n, and the rows need not be |
---|

29 | * linearly independent. B is transformed into an LLL-reduced basis, |
---|

30 | * and the return value is the rank r of B. The first m-r rows of B |
---|

31 | * are zero. |
---|

32 | * |
---|

33 | * More specifically, elementary row transformations are performed on |
---|

34 | * B so that the non-zero rows of new-B form an LLL-reduced basis |
---|

35 | * for the lattice spanned by the rows of old-B. |
---|

36 | * The default reduction parameter is delta=3/4, which means |
---|

37 | * that the squared length of the first non-zero basis vector |
---|

38 | * is no more than 2^{r-1} times that of the shortest vector in |
---|

39 | * the lattice. |
---|

40 | * |
---|

41 | * @note: uses NTL or FLINT |
---|

42 | **/ |
---|

43 | |
---|

44 | CFMatrix* cf_LLL(CFMatrix& A); |
---|

45 | |
---|

46 | /*ENDPUBLIC*/ |
---|

47 | |
---|

48 | #endif |
---|