#10281: Multimodular echelon form over cyclotomic fields fails
------------------------------+---------------------------------------------
Reporter: mraum | Owner: jason, was
Type: defect | Status: new
Priority: major | Milestone:
Component: linear algebra | Keywords: cyclotomic, echelon
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
------------------------------+---------------------------------------------
Comment(by was):
This turned out to be easier to resolve than it might have otherwise been,
since Burcin Erocal and Martin Albrecht had improved matrices modn so they
can now handle a modulus up to 2^23. However, they hadn't adapted the
chinese remainder theorem infrastructure to take this into account.
I've written code that makes it so for dense linear algebra we have all
the primes up to 2^23 at our disposal, instead of just the primes up to
46341. There are more, bigger, and better primes up to 2^23:
{{{
sage: n = prod(prime_range(46431))
sage: len(str(n))
20025
sage: time n = prod(prime_range(2^23))
Time: CPU 0.90 s, Wall: 0.90 s
sage: len(str(n))
3641670
sage: prime_pi(2^23)
564163
sage: prime_pi(46431)
4797
sage: prime_pi(2^23)//prime_pi(46431)
117
}}}
The upshot is that in various contexts we can deal with answers with up to
3.5 million digits, instead of only 20,025 digits, which was pretty
feeble. Moreover, since the linear algebra is just as fast or faster,
and we start with the biggest prime we can, certain linear algebra
computations should be much faster with this new code.
I did *not* fix anything for sparse matrices, except avoiding introducing
a major bug (caught by doctests). See #12679 for sparse matrices, as this
should be another ticket.
Also, obviously, this fix is only a partial fix, and we'll someday have to
deal with running out of primes on huge problems. But it'll take around
150 times as long to ever reach such problems, for what it is worth.
Note that it would probably be trivial to change the *old*
matrix_modn_dense code to use 64-bit ints, hence support a modulus up to
2^31. However the new Erocal-Albrecht code can't go beyond 2^23. So that
code -- which they deprecated -- should probably be resurrected. That's a
project for later.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10281#comment:2>
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.
