#3436: random_matrix() with prescribed density buggy
------------------------------+---------------------------------------------
Reporter: rpw | Owner: was
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.3.1
Component: linear algebra | Keywords:
Author: spancratz | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
------------------------------+---------------------------------------------
Comment(by craigcitro):
Okay, so I'm finally convinced. I just spent some time optimizing
generation of random number field elements, and got something like a ~150X
speedup -- and the resulting randomization for cyclotomic matrices was
'''still''' something like six times slower than the original version. So
I'm going to make a new ticket with that code, but I think the code that
Sebastian's been writing is definitely the winner. (Tom said he was going
to review it in the morning, so I'll let him do that.)
The underlying reason for the speed difference is easy to understand -- we
represent elements of number fields as NTL polynomials, so the process of
randomly generating the matrix entries involves a huge number of copies of
the data: once from sage Integers to NTL integers in generating a random
element of the number field, and then *two* copies (due to the way things
are getting moved around) in moving the values from the NTL polynomial
into the matrix entries. There's just no way this is going to beat code
that just generates entries down the line right in the matrix.
I'll add a note on this ticket once I clean up and post the faster number
field random element code ...
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/3436#comment:26>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
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.
