ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 19 Oct 2010 09:45:13 +0200smith normal form RAM limits?https://ask.sagemath.org/question/7730/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 Sat, 16 Oct 2010 21:16:06 +0200https://ask.sagemath.org/question/7730/smith-normal-form-ram-limits/Answer by John Palmieri for <p>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.</p>
<p>Are there known limits on how a big an integer matrix Sage can handle, or is there another method that I should try?</p>
<p>Thanks,
Gregg Musiker </p>
https://ask.sagemath.org/question/7730/smith-normal-form-ram-limits/?answer=11743#post-id-11743Have 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.Mon, 18 Oct 2010 17:10:22 +0200https://ask.sagemath.org/question/7730/smith-normal-form-ram-limits/?answer=11743#post-id-11743Answer by Mitesh Patel for <p>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.</p>
<p>Are there known limits on how a big an integer matrix Sage can handle, or is there another method that I should try?</p>
<p>Thanks,
Gregg Musiker </p>
https://ask.sagemath.org/question/7730/smith-normal-form-ram-limits/?answer=11736#post-id-11736Some 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][1] 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.
[1]: http://pari.math.u-bordeaux.fr/dochtml/html/Vectors,_matrices,_linear_algebra_and_sets.html#matsnfSat, 16 Oct 2010 23:55:05 +0200https://ask.sagemath.org/question/7730/smith-normal-form-ram-limits/?answer=11736#post-id-11736Comment by Evgeny for <p>Some additional data: On the main Sage development machine, a 24-core Linux server with 128 GB of RAM, I get</p>
<pre><code>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
</code></pre>
<p>for example, after about one hour of crunching. According to <code>top</code>, the <code>python</code> process is using 7.2 GB of memory.</p>
<p>According to <code>m.smith_form??</code> and <code>m.elementary_divisors??</code>, both methods both use PARI's <a href="http://pari.math.u-bordeaux.fr/dochtml/html/Vectors,_matrices,_linear_algebra_and_sets.html#matsnf">matsnf</a> 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.</p>
https://ask.sagemath.org/question/7730/smith-normal-form-ram-limits/?comment=22554#post-id-22554if you mean - the one that runs this forum, then yes.Mon, 18 Oct 2010 15:43:17 +0200https://ask.sagemath.org/question/7730/smith-normal-form-ram-limits/?comment=22554#post-id-22554Comment by cswiercz for <p>Some additional data: On the main Sage development machine, a 24-core Linux server with 128 GB of RAM, I get</p>
<pre><code>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
</code></pre>
<p>for example, after about one hour of crunching. According to <code>top</code>, the <code>python</code> process is using 7.2 GB of memory.</p>
<p>According to <code>m.smith_form??</code> and <code>m.elementary_divisors??</code>, both methods both use PARI's <a href="http://pari.math.u-bordeaux.fr/dochtml/html/Vectors,_matrices,_linear_algebra_and_sets.html#matsnf">matsnf</a> 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.</p>
https://ask.sagemath.org/question/7730/smith-normal-form-ram-limits/?comment=22555#post-id-22555Did this Linux machine happen to be the Sage server? :)Mon, 18 Oct 2010 15:12:31 +0200https://ask.sagemath.org/question/7730/smith-normal-form-ram-limits/?comment=22555#post-id-22555Answer by ccanonc for <p>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.</p>
<p>Are there known limits on how a big an integer matrix Sage can handle, or is there another method that I should try?</p>
<p>Thanks,
Gregg Musiker </p>
https://ask.sagemath.org/question/7730/smith-normal-form-ram-limits/?answer=11744#post-id-11744A parody of cswiercz's comment ;)...
![alt text][1]
[1]: /upfiles/12874920071741598.jpgTue, 19 Oct 2010 09:40:52 +0200https://ask.sagemath.org/question/7730/smith-normal-form-ram-limits/?answer=11744#post-id-11744Comment by ccanonc for <p>A parody of cswiercz's comment ;)...</p>
<p><img alt="alt text" src="/upfiles/12874920071741598.jpg"/></p>
https://ask.sagemath.org/question/7730/smith-normal-form-ram-limits/?comment=22551#post-id-22551OK, so maybe I just like that Dilbert on the cover of "Advanced Programming in the UNIX Environment" (hardcover, of course;)Tue, 19 Oct 2010 09:45:13 +0200https://ask.sagemath.org/question/7730/smith-normal-form-ram-limits/?comment=22551#post-id-22551Answer by gregg for <p>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.</p>
<p>Are there known limits on how a big an integer matrix Sage can handle, or is there another method that I should try?</p>
<p>Thanks,
Gregg Musiker </p>
https://ask.sagemath.org/question/7730/smith-normal-form-ram-limits/?answer=11737#post-id-11737Thank 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.
Sun, 17 Oct 2010 15:10:39 +0200https://ask.sagemath.org/question/7730/smith-normal-form-ram-limits/?answer=11737#post-id-11737