Creating large matrix hangs

[Cary Cherng]

I have a sage script that ultimately creates a python list called MMv
of length 35354. Each element is a list of length 55. This is in
effect a 35354 by 55 matrix. Print statements show that when I run my
script with "load two.sage" it gets stuck at taking this list and
creating a matrix. I am using the following to try to create the
matrix.
MM = matrix(ZZ, MMv)

Is there a way I can debug or understand why the matrix creation isn't
returning?

[Robert Bradshaw]

Can you run top() and see (1) how much CPU it's using and (2) how much
memory it's using (compared to your free memory).

[Simon King]

Hi Robert!

On 23 Okt., 10:18, Robert Bradshaw <rober...@math.washington.edu>
wrote:

> Can you run top() and see (1) how much CPU it's using and (2) how much
> memory it's using (compared to your free memory).

I doubt that memory is the problem. The following is on sage.math
(thus, with plenty of memory):

sage: %time L = [[ZZ.random_element() for _ in range(55)] for __ in
range(35354)]
CPU times: user 1.28 s, sys: 0.13 s, total: 1.41 s
Wall time: 1.41 s

But I interrupted
sage: %time M=Matrix(ZZ,L)
after several minutes.

BTW: Ctrl-C did not work!! I had to kill the Sage process.

Other attempts to solve it:
sage: MS = MatrixSpace(ZZ,35354,55)
sage: %time M = MS(L)
Again, I had to kill the Sage process

But this works:
sage: MS = MatrixSpace(ZZ,35354,55)
sage: M = MS(0)
sage: %time for i in range(35354*55): M[int(i/55),i
%55]=ZZ.random_element()
CPU times: user 14.52 s, sys: 0.01 s, total: 14.53 s
Wall time: 14.53 s

Or, even better:
sage: %time for i in range(35354): M[i]=L[i]
CPU times: user 0.31 s, sys: 0.00 s, total: 0.31 s
Wall time: 0.30 s

So, one should create an empty matrix and then insert the elements row
by row.

It surprises me that this is not done in the matrix constructor.
Should be a known problem...

Cheers,
Simon

[Simon King]

Hi!

On 23 Okt., 11:59, Simon King <simon.k...@nuigalway.ie> wrote:
> So, one should create an empty matrix and then insert the elements row
> by row.

It it also more efficient on a smaller skale (and does the right
thing):

sage: MS = MatrixSpace(ZZ,100,50)
sage: L = [[ZZ.random_element() for _ in range(50)] for __ in
range(100)]
sage: timeit('M = MS(0)\nfor i in range(len(L)): M[i]=L[i]')
625 loops, best of 3: 602 µs per loop
sage: timeit('M = Matrix(ZZ,L)')
125 loops, best of 3: 2.81 ms per loop
sage: M = MS(0)
sage: for i in range(len(L)): M[i]=L[i]
....:
sage: M == Matrix(ZZ,L)
True

Cheers,
Simon

[Yann]

In the matrix constructor (matrix in sage/matrix/constructor.py):

entries = sum([list(v) for v in args[0]], []) <--- this is bad
(quadratic in the length of argv[0] which is the number of rows here)

Yann

[Yann]

> In the matrix constructor (matrix in sage/matrix/constructor.py):
>
> entries = sum([list(v) for v in args[0]], [])    <--- this is bad
> (quadratic in the length of argv[0] which is the number of rows here)

and to be complete, this could be replaced by:

entries = []
for v in args[0]: entries.extend(v)

Yann

[Simon King]

Hi Yann!

On 23 Okt., 13:32, Yann <yannlaiglecha...@gmail.com> wrote:
> ...

> In the matrix constructor (matrix in sage/matrix/constructor.py):
>
> entries = sum([list(v) for v in args[0]], [])    <--- this is bad
> (quadratic in the length of argv[0] which is the number of rows here)

I guess this line will only be executed if the input is a list of
lists (or tuple or iterable perhaps). Instead, one should probably
have the row by row insertion.

Can someone open a ticket for this, please? I am in the middle of a
relocation, and *if* I'll find time, I will work on categories.

Best regards,
Simon

[Yann]

this is now ticket #10158

Yann

[Simon King]

On 23 Okt., 14:15, Yann <yannlaiglecha...@gmail.com> wrote:
> this is now ticket #10158

Thanks!
Simon

[Yann]

And ready for review...

Yann