On Feb 27, 5:41 am, Santanu Sarkar <[email protected]>
wrote:
> No since in matrix dimension is (200,200). And entries are of the order of
> 2^500.
> So using just LLL algorithm takes much time. Hence I want to use Damien
> Stehle’s fpLLL
> (currently the world’s best).
Have you read the docstring of A.LLL? To quote the algorithm keyword
- ``algorithm`` - string (default: "fpLLL:wrapper")
one of the algorithms mentioned below
And this refers to the "AVAILABLE ALGORITHMS" section:
AVAILABLE ALGORITHMS:
- ``NTL:LLL`` - NTL's LLL + fp
- ``fpLLL:heuristic`` - fpLLL's heuristic + fp
- ``fpLLL:fast`` - fpLLL's fast
- ``fpLLL:wrapper`` - fpLLL's automatic choice
(default)
And there is is clearly mentioned that fpLLL is used *per default*
when doing a LLL reduction.
Cheers,
Michael
In detail for your reading please:
Returns LLL reduced or approximated LLL reduced lattice R
for this
matrix interpreted as a lattice.
A lattice `(b_1, b_2, ..., b_d)` is
`(delta, eta)` -LLL-reduced if the two following
conditions hold:
- For any `i>j`, we have `|mu_{i, j}| <= eta`,
- For any `i<d`, we have
`delta |b_i^*|^2 <= |b_{i + 1}^* + mu_{i + 1, i} b_i^* |
^2`,
where `mu_{i,j} = <b_i, b_j^*>/<b_j^*,b_j^*>` and
`b_i^*` is the `i`-th vector of the Gram-Schmidt
orthogonalisation of `(b_1, b_2, ..., b_d)`.
The default reduction parameters are `delta=3/4` and
`eta=0.501`. The parameters `delta` and
`eta` must satisfy: `0.25 < delta <= 1.0` and
`0.5 <= eta < sqrt(delta)`. Polynomial time
complexity is only guaranteed for `delta < 1`.
The lattice is returned as a matrix. Also the rank (and
the
determinant) of self are cached if those are computed
during the
reduction. Note that in general this only happens when
self.rank()
== self.ncols() and the exact algorithm is used.
INPUT:
- ``delta`` - parameter as described above (default:
3/4)
- ``eta`` - parameter as described above (default:
0.501), ignored by NTL
- ``algorithm`` - string (default: "fpLLL:wrapper")
one of the algorithms mentioned below
- ``fp``
- None - NTL's exact reduction or fpLLL's
wrapper
- ``'fp'`` - double precision: NTL's FP or fpLLL's
double
- ``'qd'`` - quad doubles: NTL's QP
- ``'xd'`` - extended exponent: NTL's XD or fpLLL's
dpe
- ``'rr'`` - arbitrary precision: NTL'RR or fpLLL's
MPFR
- ``prec`` - precision, ignored by NTL (default: auto
choose)
- ``early_red`` - perform early reduction, ignored by
NTL (default: False)
- ``use_givens`` - use Givens orthogonalization
(default: False) only applicable to approximate
reductions and NTL.
This is more stable but slower.
Also, if the verbose level is = 2, some more verbose
output is
printed during the calculation if NTL is used.
AVAILABLE ALGORITHMS:
- ``NTL:LLL`` - NTL's LLL + fp
- ``fpLLL:heuristic`` - fpLLL's heuristic + fp
- ``fpLLL:fast`` - fpLLL's fast
- ``fpLLL:wrapper`` - fpLLL's automatic choice
(default)
OUTPUT: a matrix over the integers
EXAMPLE::
sage: A = Matrix(ZZ,3,3,range(1,10))
sage: A.LLL()
[ 0 0 0]
[ 2 1 0]
[-1 1 3]
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-support
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
