#1346: [with patch, needs review] fpLLL doctests don't test fpLLL
--------------------------------+-------------------------------------------
Reporter: cwitty | Owner: was
Type: defect | Status: new
Priority: major | Milestone: sage-3.2
Component: algebraic geometry | Resolution:
Keywords: |
--------------------------------+-------------------------------------------
Comment (by malb):
Damien Stehlé suggested three ways to check for LLL reduction off-list:
{{{
In order to checking the LLL-reducedness of a basis, I have three ideas.
1) One could think that LLL on a LLL-reduced basis should not do
anything. So one idea would be
to run another (reliable) LLL routine on the output, and see if it
actually does nothing. That
should be easy in SAGE, since you have an easy access to several LLLs. You
have to pay attention
to the LLL parameters (delta and eta), which could be annoying since eta
is not specified in NTL
(though it is >1/2).
You also have to pay attention to the precision if you use fp-arithmetic
(it should be high
enough). In any case, it is going to be dirty and provide bugs or
inconsistences between the
different codes. And on top of it, a LLL may actually do something on an
already-reduced basis,
as long as it provides another reduced basis. Due to fp-errors, this may
actually occur.
Furthermore, there are portability issues. fplll is not portable between
32 bit and 64 bit
machine (for efficiency reasons). I know inputs for which it answers
something
different on 32 and 64 bit machines.
2) Compute the Gram-Schmidt Orthogonalisation with rational arithmetic and
check if the LLL
conditions are satisfied. Easy, but slow on large examples.
3) Use Gilles Villard's paper that tries to do the same as 2), but with
fp-arithmetic.
Certification of the QR factor R and of lattice basis reducedness. ISSAC
2007: 361-368
}}}
I do 2) in the above patch.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/1346#comment:5>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
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-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
