Conversion of libgap data to sage data

[Simon King]

Hi!

I have some files providing GAP readable data, i.e.,
libgap.Read(source)
works. The data consist of a rec(...) (roughly
corresponding to a Python dict), where some of the values
are lists of strings and other simple things, some are
lists of lists of finite field elements, some are other
records.

Gap interpretes the lists of lists as matrices, and in
fact in my code I need to perform arithmetic operations
with it. Unfortunately gap matrix arithmetic is very
slow. Thus, I want to transform the libgap data into the
corresponding Sage data.

Unfortunately, the transition from libgap to Sage is very
slow: Reading the data into libgap takes 16 seconds,
translating the data to Sage takes 3 minutes. Most of that
time is used for the transformation of the matrices. Actually
I am using boilerplate to speed things up, otherwise it
would take a lot longer than 3 minutes.

As an alternative idea, I tried to change the content
of the data file into something that can be evaluated
by sage_eval. But that's a lot worse: Changing the data
format took about one minute, sage_eval consumed an insane
amount of memory.

Can you tell me a different approach to make things faster?
I.e., either to read the data into Sage directly or via
libgap, but not longer than twice the time needed to read
the data into libgap?

Best regards,
Simon

[Nils Bruin]

On Friday, September 15, 2017 at 8:38:37 AM UTC-7, Simon King wrote:

Unfortunately, the transition from libgap to Sage is very
slow: Reading the data into libgap takes 16 seconds,
translating the data to Sage takes 3 minutes. Most of that
time is used for the transformation of the matrices. Actually
I am using boilerplate to speed things up, otherwise it
would take a lot longer than 3 minutes.

It would seem to me that libgap should be able to do the translation pretty efficiently. My first suspicion would be that you hit some generic translation cop-out. Something that reverts to strings or so? I would also do some timings to see how this scales: it should be roughly linear in input. If it seems to be something worse, then that might be an indication there's a wrong algorithm involved somewhere.

How fast is converting your list of matrices to a list of lists in gap? Perhaps GapMatrix->GapList->SageList->SageMatrix is faster.

[Simon King]

Hi Nils,

On 2017-09-15, Nils Bruin <nbr...@sfu.ca> wrote:
> How fast is converting your list of matrices to a list of lists in gap?
> Perhaps GapMatrix->GapList->SageList->SageMatrix is faster.

If I understand correctly, what libgap uses *are* lists. But apparently
gap treats lists of lists as matrices and multiplies them accordingly.

Here are some more details:

1. libgap takes 16 seconds to read the raw data, which comprise about
twenty matrices and some more simple data.
sage: %time libgap.Read("path/to/my/data.gap")
CPU times: user 15.9 s, sys: 64 ms, total: 16 s
Wall time: 16 s
sage: G = libgap.eval('basicalg')
sage: M1 = G['1a4a1']['mat']
sage: M2 = G['4a1a1']['mat']

2. The "matrices" are in fact lists of lists:
sage: M1.IsList()
true
sage: M2.IsList()
true
sage: M2[1].IsList()
true

3. libgap sucks in multiplying the matrices:
sage: %time M = M1*M2
CPU times: user 2min 58s, sys: 20 ms, total: 2min 58s
Wall time: 2min 58s

4. Sage sucks in transforming the lists of lists:
sage: %time L1 = M1.sage()
CPU times: user 6min 55s, sys: 52 ms, total: 6min 55s
Wall time: 6min 55s
sage: %time L2 = M2.sage()
CPU times: user 6min 31s, sys: 96 ms, total: 6min 31s
Wall time: 6min 32s

5. Sage could, I think, do better in transforming a list
of lists into a proper matrix:
sage: K.<a> = GF(8)
sage: %time MS1 = MatrixSpace(K,len(L1),len(L2))(L1)
CPU times: user 4.71 s, sys: 20 ms, total: 4.73 s
Wall time: 4.78 s
sage: %time MS2 = MatrixSpace(K,len(L2),len(L1))(L2)
CPU times: user 4.58 s, sys: 40 ms, total: 4.62 s
Wall time: 4.57 s

6. And here is why I want the transformation:
sage: %time MS = MS1*MS2
CPU times: user 48 ms, sys: 0 ns, total: 48 ms
Wall time: 106 ms

By the way, the matrices aren't particularly large:
sage: MS1.dimensions()
(896, 1984)
sage: MS2.dimensions()
(1984, 896)

Using boilerplate (accessing libgap finite field elements standing
in a list with libGAP_ELM_PLIST and make_GapElement_FiniteField,
only doing a transformation if the element is nonzero, using
set_unsafe to define the elements of the matrix in Sage), I can
transform the libgap list of lists into a Sage matrix in about
20 seconds - still longer than reading *all* data into libgap from
a long string (the data file has more than 2.7*10^6 lines and
204*10^6 characters)!

An ideal solution for me would be either of the following:
- A way to make libgap use a matrix implementation that is as fast
as Sage matrices and is certainly a lot faster than treating
matrices as lists of lists. I was told long ago that GAP has
faster matrix implementations, but I don't know how to invoke
them.
- A way to transform a list of lists as above from libgap into
a sage matrix in about 1 sec.
- A way to make a gap-readable file sage-readable and read it
into sage in less than 30 seconds; I can make the file sage-readable,
but sage_eval apparently is not appropriate to actually read it.

Best regards,
Simon

[Simon King]

On 2017-09-16, Simon King <simon...@uni-jena.de> wrote:
> An ideal solution for me would be either of the following:
> - A way to make libgap use a matrix implementation that is as fast
> as Sage matrices and is certainly a lot faster than treating
> matrices as lists of lists. I was told long ago that GAP has
> faster matrix implementations, but I don't know how to invoke
> them.

I thought I was told about faster matrices by my former boss, David
Green, but by searching my mails I found that I was pointed to
ImmutableMatrix by Dima Pasechnik.

Let's see if that's fast enough...

[Simon King]

It is an improvement, but not good enough:

sage: %time libgap.Read("path/to/my/modified_data.gap")
CPU times: user 30 s, sys: 224 ms, total: 30.3 s
Wall time: 32.6 s

sage: G = libgap.eval('basicalg')
sage: M1 = G['1a4a1']['mat']
sage: M2 = G['4a1a1']['mat']

sage: M1
< immutable compressed matrix 896x1984 over GF(8) >

sage: %time M = M1*M2

CPU times: user 2.48 s, sys: 0 ns, total: 2.48 s
Wall time: 2.48 s

So, time for reading into gap was almost doubled, and the time
for multiplication, though clearly faster than the original
version, still is much more than the few milliseconds that
Sage needs for multiplying those matrices. Moreover, the conversion
of ImmutableMatrix from libgap to Sage takes ages and doesn't give
the correct result:
sage: %time MS1 = M1.sage()
CPU times: user 8min 24s, sys: 88 ms, total: 8min 24s
Wall time: 8min 25s
sage: type(MS1)
<type 'list'>

What to do? As sage_eval sucks, I should probably just try to
write the code into a (python) file and use sage.repl.load.load.
Provided that sage.repl.load.load is faster: Should perhaps
sage_eval by default write the to-be-evaluated code (if it exceeds
a certain length) into a temporary file and sage.repl.load.load it?
If "yes", then I will open a ticket for it.

Best regards,
Simon

[Simon King]

On 2017-09-16, Simon King <simon...@uni-jena.de> wrote:
> What to do? As sage_eval sucks, I should probably just try to
> write the code into a (python) file and use sage.repl.load.load.

No, it is as bad as sage_eval, i.e., makes my laptop use swap
very quickly.

[Vincent Delecroix]

Hi Simon,

It would be nice if matrices had (lib)gap conversion (which fast
implementation for specialized types). Something along

sage: m = matrix(ZZ, 100)
sage: X = my_gap_matrix()
sage: m.set_from_gap(X)

This has to be done for each matrix type in order to be efficient. One
problem of the .sage() on (lib)gap matrices is that it corresponds to
the generic GapElement_List one. It would be better to provide an extra
argument "parent" to it in order to build vectors/matrices
appropriately. If that is the case we could have the alternative to the
example above

sage: X = my_gap_matrix()
sage: X.sage(parent=MatrixSpace(ZZ, 100))

Please put me in cc if you start opening trac tickets about it!

Best
Vincent

[slelievre]

Could py-openmath or py-scscp help with that?

- py-openmath

  https://github.com/OpenMath/py-openmath

  https://pypi.python.org/pypi/openmath

- py-scscp

  https://github.com/OpenMath/py-scscp

  https://pypi.python.org/pypi/scscp

- sage #19970: Provide an OpenMath interface

  https://trac.sagemath.org/ticket/19970

- sage #19971: Provide an SCSCP interface

  https://trac.sagemath.org/ticket/19971