On Sat, Jan 31, 2009 at 11:56 AM, John H Palmieri
<jhpalmier...@gmail.com> wrote:
>
> I'm having some issues with integer matrices. I have a matrix mat:
>
> sage: mat
> 891 x 1559 sparse matrix over Integer Ring
> sage: mat.rank() # this takes a long time
> sage.bin(75404,0xa06be720) malloc: *** mmap(size=447524864) failed
> (error code=12)
> *** error: can't allocate region
> *** set a breakpoint in malloc_error_break to debug
> ---------------------------------------------------------------------------
> PariError Traceback (most recent call
> last)
> ...
> PariError: not enough memory (48)
>
>
> On the other hand:
>
> sage: mat.dense_matrix().rank() # this is pretty quick
> 891
>
> Similarly for elementary divisors: the sparse case makes Sage crash:
>
> sage: mat.elementary_divisors()
> sage.bin(75404,0xa06be720) malloc: *** mmap(size=2097152) failed
> (error code=12)
> *** error: can't allocate region
> *** set a breakpoint in malloc_error_break to debug
> sage.bin(75404,0xa06be720) malloc: *** mmap(size=2097152) failed
> (error code=12)
> *** error: can't allocate region
> *** set a breakpoint in malloc_error_break to debug
>
> ------------------------------------------------------------
> Unhandled SIGBUS: A bus error occured in SAGE.
> This probably occured because a *compiled* component
> of SAGE has a bug in it (typically accessing invalid memory)
> or is not properly wrapped with _sig_on, _sig_off.
> You might want to run SAGE under gdb with 'sage -gdb' to debug this.
> SAGE will now terminate (sorry).
> ------------------------------------------------------------
>
> The dense case finishes successfully and pretty quickly.
>
> I've had some similar issues before; if you have a sparse matrix over
> the integers, it seems as though you should always convert it to a
> dense matrix before doing anything to it. (This doesn't seem true
> over a field; rank works for both dense and sparse matrices, and at
> least for some sparse ones, rank is faster without converting.)
>
> Questions:
>
> 1. for anyone familiar with the code, do these observations make
> sense?
Yes.
> Is it sensible to convert sparse integer matrices to dense
> ones before doing anything else?
It depends what you're doing. If you're using any function in
devel/sage/sage/matrix/matrix_integer_sparse.pyx
then it will be faster and more efficient -- i.e., if you're using
sparse matrices as a storage format for sparse data. Anything not
defined in that file is inherited generic code, and is likely to be
slow.
If you look in
devel/sage/sage/matrix/matrix_integer_dense.pyx
you can see what will be fast for dense integer matrices.
With some work more functionality from linbox for sparse integer
matrices could be wrapped and made faster. And of course more
algorithms could be implemented from scratch. I personally usually
care only about sparse matrices over QQ, so they're pretty faster for
some things.
> 2. Are there any guidelines about how large a matrix Sage (or Pari)
> can handle without barfing?
> For example, if I'm using a Mac with 2GB
> of memory, or if I'm using sage.math?
As much as will fit in ram. If you run out of memory, then lines of
code like this:
self._matrix = <mpz_vector*>
sage_malloc(parent.nrows()*sizeof(mpz_vector))
if self._matrix == NULL:
raise MemoryError, "error allocating sparse matrix"
will of course result in a MemoryError.
For rank in particular, probably your best bet is to change to a dense
matrix over QQ and ask for the rank there. Sage does have fast
sparse rank computation over GF(p) for small p, so you could also try
that to get a heuristic bound on the rank. For example:
sage: a = random_matrix(ZZ,100,density=0.02,sparse=True)
sage: time b = a.change_ring(GF(389))
CPU times: user 0.00 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.02 s
sage: time c = b.rank()
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.05 s
sage: time a.rank()
CPU times: user 7.96 s, sys: 0.88 s, total: 8.84 s
Wall time: 9.47 s
72
sage: c
72
William
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to
sage-support-unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sage-support
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
