Ask Your Question
2

smith normal form RAM limits?

asked 2010-10-16 14:16:06 -0500

gregg gravatar image

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 flag offensive close merge delete

4 answers

Sort by » oldest newest most voted
3

answered 2010-10-18 10:10:22 -0500

updated 2010-10-18 10:14:20 -0500

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.

edit flag offensive delete link more
1

answered 2010-10-16 16:55:05 -0500

Mitesh Patel gravatar image

updated 2010-10-18 17:15:01 -0500

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.

edit flag offensive delete link more

Comments

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

cswiercz gravatar imagecswiercz ( 2010-10-18 08:12:31 -0500 )edit

if you mean - the one that runs this forum, then yes.

Evgeny gravatar imageEvgeny ( 2010-10-18 08:43:17 -0500 )edit
1

answered 2010-10-17 08:10:39 -0500

gregg gravatar image

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.

edit flag offensive delete link more
0

answered 2010-10-19 02:40:52 -0500

ccanonc gravatar image

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

alt text

edit flag offensive delete link more

Comments

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

ccanonc gravatar imageccanonc ( 2010-10-19 02:45:13 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2010-10-16 14:16:06 -0500

Seen: 728 times

Last updated: Oct 19 '10