Ticket #723 (closed enhancement: fixed)

Opened 1 year ago

Last modified 1 year ago

[with patch] Make Sage's LLL faster: Magma seems to totally blow Sage (i.e., NTL) away for large-ish problems.

Reported by: was Assigned to: was
Priority: major Milestone: sage-2.8.8
Component: linear algebra Keywords:
Cc:

Description (Last modified by was)

Magma's LLL is... way way way faster than the one in NTL. E.g., (this requires patch #325) 

sage: a = random_matrix(ZZ,200)
sage: time b=a.lll()
CPU times: user 8.74 s, sys: 0.08 s, total: 8.83 s
Wall time: 8.85

sage: m = magma(a)
sage: time c=m.LLL()
Wall time: 1.02

sage: a = random_matrix(ZZ,400)
sage: time b=a.lll()
CPU times: user 202.89 s, sys: 1.54 s, total: 204.44 s
Wall time: 206.16
sage: time c=magma(a)
CPU times: user 0.24 s, sys: 0.02 s, total: 0.26 s
Wall time: 0.38
sage: time d=c.LLL()
Wall time: 13.23

It would also be good to benchmark PARI's LLL and compare. Make sure to use the 1 option, so it knows the matrix is integral: 

sage: a = random_matrix(ZZ,100)
sage: time b=a.lll()
CPU times: user 0.53 s, sys: 0.00 s, total: 0.53 s
Wall time: 0.53
sage: c = pari(a)
sage: time d=c.qflll(1)
CPU times: user 0.47 s, sys: 0.00 s, total: 0.47 s
Wall time: 0.47
sage: a = random_matrix(ZZ,200)
sage: time b=a.lll()
CPU times: user 9.02 s, sys: 0.06 s, total: 9.08 s
Wall time: 9.14
sage: c = pari(a)
sage: time d=c.qflll(1)
CPU times: user 9.88 s, sys: 0.05 s, total: 9.93 s
Wall time: 9.95

Attachments

ntls-fp-lll.patch (18.2 kB) - added by malb on 09/21/2007 04:33:59 PM.

Change History

09/21/2007 12:46:53 PM changed by was

David Kohel had by far the most interesting response on sage-devel to this ticket: 

David Kohel <drkohel@gmail.com> 		 hide details	 6:00 am (6 hours ago) 
	reply-to		sage-devel@googlegroups.com	 
	to		sage-devel <sage-devel@googlegroups.com>	 
	date		Sep 21, 2007 6:00 AM	 
	subject		[sage-devel] Re: LLL	 
	mailed-by		googlegroups.com	 

Since LLL and LLLGram in Magma V2.13 are written by Damien Stehle,
using his asymptotically better algorithm.  The previous version was
not
even mathematically correct (adhoc "improvements" or post-processing
could destroy the LLL reduction condition).

Damien provides C code under GPL and can be found on his web page:

http://perso.ens-lyon.fr/damien.stehle/english.html

It might take some art to decide on optimal parameters, but linking it
into
SAGE should provide the same asymptotic performance as in Magma.

--David
- Show quoted text -

09/21/2007 12:47:01 PM changed by was

  • milestone changed from sage-wishlist to Sage-2.10.

09/21/2007 04:33:40 PM changed by malb

The attached patch exposes NTL's floating point LLL implementations which are significantly faster than the exact one. However, these are approximates only.

09/21/2007 04:33:59 PM changed by malb

  • attachment ntls-fp-lll.patch added.

09/21/2007 04:41:07 PM changed by malb

after patch:

double precision vs. MAGMA: 

sage: a = random_matrix(ZZ,200)
sage: time b=a.LLL(algorithm="NTL:LLL_FP")
Time: CPU 0.91 s, Wall: 0.93 s

sage: m = magma(a)
sage: time c=m.LLL()
Wall: 1.33 s

sage: a = random_matrix(ZZ,400)
sage: time b=a.LLL(algorithm="NTL:LLL_FP")
Time: CPU 6.75 s, Wall: 6.94 s

sage: c=magma(a)
sage: time d=c.LLL()
Wall: 20.41 s

quad float precision vs. MAGMA: 

sage: a = random_matrix(ZZ,200)
sage: time b=a.LLL(algorithm="NTL:LLL_QP")
Time: CPU 2.56 s, Wall: 2.60 s

sage: m = magma(a)
sage: time c=m.LLL()
Wall: 1.34 s

sage: a = random_matrix(ZZ,400)
sage: time b=a.LLL(algorithm="NTL:LLL_QP")
Time: CPU 31.36 s, Wall: 32.00 s

sage: c=magma(a)
sage: time d=c.LLL()
Wall: 20.13 s

However: 

sage: B = MatrixSpace(IntegerRing(), 50, 51)(0
sage: for i in range(50): B[i,0] = ZZ.random_element(2**10000)
sage: for i in range(50): B[i,i+1] = 1;  

sage: B.LLL(algorithm="NTL:LLL_FP")
LLL_FP: numbers too big...use LLL_XD
...
<type 'exceptions.RuntimeError'>

sage: time B.LLL(algorithm="NTL:LLL_XD")
50 x 51 dense matrix over Integer Ring
CPU time: 43.55 s,  Wall time: 44.73 s

sage: M = magma(B)
sage: time C = M.LLL()
Wall: 15.53 s

10/01/2007 07:21:46 PM changed by malb

fpLLL as mentioned above is patched into SAGE by the patch found at

http://sage.math.washington.edu/home/malb/fplll.patch

. Using this code, we can achieve a quite good performance. 

sage:  = MatrixSpace(IntegerRing(), 50, 51)(0)
sage: for i in range(50): B[i,0] = ZZ.random_element(2**10000)
....:
sage: for i in range(50): B[i,i+1] = 1
....:
sage: time C = B.LLL('fpLLL:fast')
CPU times: user 9.54 s, sys: 0.00 s, total: 9.54 s
Wall time: 9.56

sage: C.is_LLL_reduced()
True

sage: BM = B._magma_()
sage: time CM = BM.LLL()
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 15.20

sage: time magma.eval("CM := LLL(%s:Fast:=1)"%BM.name())
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 11.68

10/03/2007 01:36:45 PM changed by mhansen

  • summary changed from Make Sage's LLL faster: Magma seems to totally blow Sage (i.e., NTL) away for large-ish problems. to [with patch] Make Sage's LLL faster: Magma seems to totally blow Sage (i.e., NTL) away for large-ish problems..

10/18/2007 06:44:41 AM changed by mabshoff

  • milestone changed from Sage-2.10 to sage-2.8.8.

10/18/2007 06:49:23 PM changed by was

  • description changed.

10/18/2007 06:55:22 PM changed by was

This patch has fplll.c, which is Cython autogenerated code. Please make a clean new patch that doesn't have fplll.c or any other autogenerated code in it.

10/18/2007 06:56:37 PM changed by was

I *have* applied ntls-fp-lll.patch. The patch that isn't clean is

http://sage.math.washington.edu/home/malb/fplll.patch

10/18/2007 06:58:58 PM changed by was

  • summary changed from [with patch] Make Sage's LLL faster: Magma seems to totally blow Sage (i.e., NTL) away for large-ish problems. to [with patch that needs work] Make Sage's LLL faster: Magma seems to totally blow Sage (i.e., NTL) away for large-ish problems..

10/19/2007 10:32:05 AM changed by was

  • status changed from new to closed.
  • resolution set to fixed.
  • summary changed from [with patch that needs work] Make Sage's LLL faster: Magma seems to totally blow Sage (i.e., NTL) away for large-ish problems. to [with patch] Make Sage's LLL faster: Magma seems to totally blow Sage (i.e., NTL) away for large-ish problems..

The Damien part has been moved to ticket 929.