#4237: [with patch; needs review] magma -- finite field matrix conversions
-------------------------+--------------------------------------------------
Reporter: was | Owner: was
Type: enhancement | Status: assigned
Priority: major | Milestone: sage-3.2.2
Component: interfaces | Resolution:
Keywords: |
-------------------------+--------------------------------------------------
Changes (by was):
* summary: [with patch; half done] magma -- finite field matrix
conversions => [with patch; needs review] magma
-- finite field matrix conversions
Comment:
The second patch adds support for much faster conversions of matrices over
GF(2) to Magma. Now sage can convert your 10000x10000 GF(2) matrix in
about 45 seconds, instead of the 149 seconds it used to take (so over 3
times faster). The intermediate memory usage is also better on the Sage
side.
BEFORE:
{{{
sage: w = random_matrix(GF(2),10000)
sage: time k = w._magma_init_(magma)
CPU times: user 49.64 s, sys: 2.20 s, total: 51.84 s
Wall time: 52.75 s
sage: time a = magma(k)
CPU times: user 1.94 s, sys: 2.69 s, total: 4.63 s
Wall time: 97.84 s
sage: 52 + 97
149
}}}
AFTER:
{{{
sage: w = random_matrix(GF(2),10000)
sage: time k = w._magma_init_(magma)
CPU times: user 1.22 s, sys: 0.63 s, total: 1.85 s
Wall time: 1.85 s
sage: time a = magma(k)
CPU times: user 1.70 s, sys: 2.30 s, total: 4.00 s
Wall time: 44.15 s
}}}
Now the time is totally dominated by the time Magma spends in the function
StringToIntegerSequence.
I tried the 2*10^4 example. With the new code, Sage does create a 5GB
string in memory, then writes it to a 763MB file:
{{{
w...@sage:~/.sage/temp/sage/22977/interface$ ls -lh
total 764M
-rw-r--r-- 1 was was 763M 2008-12-12 11:12 tmp22977
}}}
Then Sage frees all that memory. Then Magma reads in the string to
memory, which
takes over 5GB again (not surprisingly):
{{{
23012 was 25 0 5772m 5.1g 2796 R 100 8.0 2:41.25
magma.exe.x86_6
}}}
Converts that to a string over integers (which also takes a lot of RAM),
then creates a mod-2 matrix.
It would in theory be possible to do this via a series of chunks as you
suggest, but support for that does not exist in the Magma/Sage interface
(or any interface) at all, and would probably be particular hard to get
right when Magma isn't even running locally (I think now one could have
the magma run on a different machine and that 763MB file above would get
copied via scp, maybe...)
If only Magma had any support WHATEVER for bit manipulation. Then we
could send the whole data over as a single integer or other format and
extract it. But Magma doesn't. At present it seems that by far the
fastest way to get a mod-2 matrix over to Magma is to do what I've
implemented in patch 2, which is pretty bad memory-wise in the limit. It
does complete your 2*10^4 example on sage.math in 192 seconds, which is an
improvement:
{{{
sage: A = random_matrix(GF(2),2*10^4,2*10^4)
sage: time B = magma(A)
CPU times: user 16.28 s, sys: 14.38 s, total: 30.65 s
Wall time: 192.45 s
}}}
Anyway, for something more memory efficient, what I just wrote could be
the base case. Maybe you could try sending a big matrix over GF(2) to
magma by breaking it into smaller matrices, sending each of those (with
the new code I just wrote), then reassembling the result in Magma. Can
magma do things like stack matrices (like Sage's A.stack)?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4237#comment:12>
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
-~----------~----~----~----~------~----~------~--~---
