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
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.
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.
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()
About 10 minutes later:
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.
A parody of cswiercz's comment ;)...
Asked: 2010-10-16 21:16:06 +0100
Seen: 1,509 times
Last updated: Oct 19 '10
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
