Matrix constructor runs out of memory

asked 2022-01-13 19:01:24 +0200

PatrickKinnear gravatar image

I am trying to construct a matrix with entries in $\mathbb{Q}(q)$, from a list of Sage vectors. I do this using

A = matrix(QQ['q'].fraction_field(), relations)

where the vectors in the list relations are Sage vectors over QQ['q'].fraction_field().

The list relations is generated by a subroutine involving some randomness, and in many cases the above works fine but sometimes my script uses too much memory and is killed by the operating system. Tracing the memory allocation it is clear that the problem occurs at the given line where I construct the matrix from the list of vectors.

The sorts of matrices for which the script fails are tend to have about 100 columns and 50-100 rows. They are sparse (each row has <= 4 nonzero entries) and the nonzero entries are of the form -2/q^x + 2 where x is in the range 10000 - 100000.

It seems clear that when some combination of the order of magnitude of the exponents x and the matrix size is reached, then the matrix constructor uses too much memory. I wondered if there is a solution anyone can suggest, or even just explain a bit more about why this constructor seems to max out on memory?

(P.S. I plan to re-implement things using sparse matrices, and maybe this will help, though I'd still like to understand better why the dense version fails.)

edit retag flag offensive close merge delete

Comments

I'm curious: does the construction succeed with smaller matrices?

John Palmieri gravatar imageJohn Palmieri ( 2022-01-13 21:55:40 +0200 )edit

Stupid question : did you try to pass sparse=True to matrix ? And to the construction of FractionField(PolynomialRing(QQ, "q")) and the construction of the vectors ? Ditto for immutable.

Large degree dense polynomials can be unmanageable beasts... OTOH, sparse polynomials may be way slower.

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2022-01-13 23:10:48 +0200 )edit

Hi John: yes, the computation works when the matrices are smaller. The size of the exponent tends to grow as the matrix size does, and having tried Emmanuel's suggestion I think this was the real issue.

PatrickKinnear gravatar imagePatrickKinnear ( 2022-01-14 16:28:42 +0200 )edit
1

Hi Emmanuel, thanks for your suggestion. Adding sparse=True to the matrix constructor didn't do much, but adding this to the polynomial ring constructor made a huge improvement. Thanks!

The constructor does eventually run out of memory still but now for much larger matrices, so I think I should be able to get enough data for my application.

I added immutable=True to the matrix constructor and didn't see huge improvements on top of those coming from using sparse polynomials. I also couldn't seem to pass this keyword to the FractionField or PolynomialRing constructors. I'm not familiar with this parameter or using immutables for memory management: what's the idea behind this?

PatrickKinnear gravatar imagePatrickKinnear ( 2022-01-14 16:33:24 +0200 )edit

I'm not familiar with this parameter or using immutables for memory management: what's the idea behind this?

From matrix? :

  • "immutable" -- (boolean) make the matrix immutable. By default, the output matrix is mutable.

This saves you one level of indirection. Sometimes comes handy... and may point you to bugs (!).

I recommend reading this free book to get a better understanding of Sage and its underlying design...

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2022-01-15 09:25:42 +0200 )edit
add a comment