# smith normal form RAM limits?

I was recently trying to compute the Smith Normal Form or elementary divisors of an approx 500 x 3000 dimensional matrix and got a memory error on my Mac laptop.

Are there known limits on how a big an integer matrix Sage can handle, or is there another method that I should try?

Thanks, Gregg Musiker

edit retag close merge delete

Sort by » oldest newest most voted Have you tried

sage: M2 = CC.differential(2)
sage: M2.elementary_divisors()


The elementary_divisors method seems to be a lot faster, and maybe more memory efficient, than the smith_form method. For example:

sage: timeit('random_matrix(ZZ, 50, 100).smith_form()')
5 loops, best of 3: 137 ms per loop
sage: timeit('random_matrix(ZZ, 50, 100).elementary_divisors()')
25 loops, best of 3: 10.2 ms per loop


Note also that smith_form may fail with sparse matrices:

sage: random_matrix(ZZ, 50, 100, sparse=True).smith_form()


raises an error.

more

Some additional data: On the main Sage development machine, a 24-core Linux server with 128 GB of RAM, I get

sage: m = matrix(ZZ, 500, 3000, [1..500*3000])
sage: m.smith_form()
(500 x 3000 dense matrix over Integer Ring, 500 x 500 dense matrix over Integer Ring, 3000 x 3000 dense matrix over Integer Ring)
sage: get_memory_usage()
8189.71875


for example, after about one hour of crunching. According to top, the python process is using 7.2 GB of memory.

According to m.smith_form?? and m.elementary_divisors??, both methods both use PARI's matsnf function but with different arguments (1 and 0, respectively). Unfortunately, I'm not familiar with the algorithm(s) it uses, the particular implementation(s), or whether they can be parallelized, etc. Please see John Palmieri's answer for a much more practical... answer.

more

Did this Linux machine happen to be the Sage server? :)

Thank for the answer, Mitesh. It is hard to write some sample code since I obtained the matrix in question after applying a few algebraic topology procedures that took about half-an-hour. However, here are the last few lines of code:

sage: M2 = CC.differential(2)

sage: M2

558 x 3224 sparse matrix over Integer Ring (type 'print M2.str()' to see all of the entries)

sage: MSF2 = M2.smith_form()

python(445) malloc: * vm_allocate(size=124502016) failed (error code=3)

python(445) malloc: * error: can't allocate region

python(445) malloc: * set a breakpoint in szone_error to debug

python(445) malloc: * vm_allocate(size=124424192) failed (error code=3)

python(445) malloc: * error: can't allocate region

python(445) malloc: * set a breakpoint in szone_error to debug

python(445) malloc: * vm_allocate(size=124346368) failed (error code=3)

python(445) malloc: * error: can't allocate region

python(445) malloc: * set a breakpoint in szone_error to debug

python(445) malloc: * vm_allocate(size=124268544) failed (error code=3)

python(445) malloc: * error: can't allocate region

python(445) malloc: * set a breakpoint in szone_error to debug

python(445) malloc: * vm_allocate(size=124190720) failed (error code=3)

python(445) malloc: * error: can't allocate region

python(445) malloc: * set a breakpoint in szone_error to debug

python(445) malloc: * vm_allocate(size=124112896) failed (error code=3)

python(445) malloc: * error: can't allocate region

python(445) malloc: * set a breakpoint in szone_error to debug

python(445) malloc: * vm_allocate(size=124035072) failed (error code=3)

python(445) malloc: * error: can't allocate region

python(445) malloc: * set a breakpoint in szone_error to debug

python(445) malloc: * vm_allocate(size=123961344) failed (error code=3)

python(445) malloc: * error: can't allocate region

python(445) malloc: * set a breakpoint in szone_error to debug

python(445) malloc: * vm_allocate(size=123883520) failed (error code=3)

python(445) malloc: * error: can't allocate region

python(445) malloc: * set a breakpoint in szone_error to debug

python(445) malloc: * vm_allocate(size=123805696) failed (error code=3)

python(445) malloc: * error: can't allocate region

python(445) malloc: * set a breakpoint in szone_error to debug

python(445) malloc: * vm_allocate(size=123727872) failed (error code=3)

python(445) malloc: * error: can't allocate region

python(445) malloc: * set a breakpoint in szone_error to debug

python(445) malloc: * vm_allocate(size=123650048) failed (error code=3)

python(445) malloc: * error: can't allocate region

python(445) malloc: * set a breakpoint in szone_error to debug

MemoryError Traceback (most recent call last)

Note that I also tried typing print M2.str() and after a minute, the computer printed the sparse incidence matrix just fine.

more

A parody of cswiercz's comment ;)... more

OK, so maybe I just like that Dilbert on the cover of "Advanced Programming in the UNIX Environment" (hardcover, of course;)