Ticket #3652 (closed defect: fixed)

Opened 5 months ago

Last modified 4 months ago

[with patch, with positive review] FreeModule(ZZ, 2000).random_element() is far slower than it should be

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

Description

Currently, random_element on a FreeModule constructs a basis, even if we know the basis is trivial. The attached patch fixes this for FreeModule_ambient and subclasses.

Before: 

sage: K = FreeModule(ZZ, 2000)
sage: get_memory_usage()
118.60546875
sage: %time _ = K.random_element()
CPU times: user 1.45 s, sys: 0.12 s, total: 1.57 s
Wall time: 1.57 s
sage: get_memory_usage()
225.56640625

After: 

sage: K = FreeModule(ZZ, 2000)
sage: get_memory_usage()
118.60546875
sage: %time _ = K.random_element()
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
sage: get_memory_usage()
118.60546875
sage: timeit('K.random_element()')
125 loops, best of 3: 2.32 ms per loop

A 600-fold speedup.

Attachments

trac3652-free-module-random-speedup.patch (1.7 kB) - added by cwitty on 07/13/2008 03:21:02 PM.

Change History

07/13/2008 03:21:02 PM changed by cwitty

  • attachment trac3652-free-module-random-speedup.patch added.

08/10/2008 01:14:46 PM changed by ncalexan

  • summary changed from [with patch, needs review] FreeModule(ZZ, 2000).random_element() is far slower than it should be to [with patch, with positive review] FreeModule(ZZ, 2000).random_element() is far slower than it should be.

Applies nicely and does speed up the operation on my system.

08/10/2008 03:52:51 PM changed by mabshoff

  • status changed from new to closed.
  • resolution set to fixed.
  • milestone changed from sage-3.1.1 to sage-3.1.

Merged in Sage 3.1.alpha1