Opened 12 years ago

Closed 8 years ago

#10095 closed defect (fixed)

Linear algebra with large integer matrices fails with RuntimeError

Reported by: fredrik.johansson Owned by: jason, was
Priority: major Milestone: sage-6.2
Component: linear algebra Keywords:
Cc: Merged in:
Authors: Travis Scrimshaw Reviewers: Marc Mezzarobba
Report Upstream: N/A Work issues:
Branch: 3a88167 (Commits, GitHub, GitLab) Commit: 3a881677e4a83e4d4de51b95778fabadb5f4e7eb
Dependencies: Stopgaps:

Status badges

Description

On my laptop (Ubuntu 64 bit, Intel T4400 CPU), integer matrices (solving, calculating determinant, etc.) appear to be broken when they get sufficiently large. I can't reproduce the problem on sage.math.

With a fresh install of the 4.5.3 release:

sage: MatrixSpace(ZZ,20,20)(1) \ MatrixSpace(ZZ,20,1).random_element()
20 x 1 dense matrix over Rational Field
sage: MatrixSpace(ZZ,200,200)(1) \ MatrixSpace(ZZ,200,1).random_element()
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)

/home/fredrik/sage-4.5.3-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/<ipython console> in <module>()

/home/fredrik/sage-4.5.3-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/local/lib/python2.6/site-packages/sage/misc/preparser.py in __mul__(self, right)
   1358             (0.0, 0.5, 1.0, 1.5, 2.0)
   1359         """
-> 1360         return self.left._backslash_(right)
   1361 
   1362 

/home/fredrik/sage-4.5.3-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/local/lib/python2.6/site-packages/sage/matrix/matrix2.so in sage.matrix.matrix2.Matrix._backslash_ (sage/matrix/matrix2.c:2641)()

/home/fredrik/sage-4.5.3-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/local/lib/python2.6/site-packages/sage/matrix/matrix2.so in sage.matrix.matrix2.Matrix.solve_right (sage/matrix/matrix2.c:3550)()

/home/fredrik/sage-4.5.3-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/local/lib/python2.6/site-packages/sage/matrix/matrix_rational_dense.so in sage.matrix.matrix_rational_dense.Matrix_rational_dense.rank (sage/matrix/matrix_rational_dense.c:20600)()

/home/fredrik/sage-4.5.3-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/local/lib/python2.6/site-packages/sage/matrix/matrix_integer_dense.so in sage.matrix.matrix_integer_dense.Matrix_integer_dense.rank (sage/matrix/matrix_integer_dense.c:24534)()

/home/fredrik/sage-4.5.3-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/local/lib/python2.6/site-packages/sage/matrix/matrix_integer_dense.so in sage.matrix.matrix_integer_dense.Matrix_integer_dense._rank_modp (sage/matrix/matrix_integer_dense.c:24821)()

RuntimeError: 

Change History (10)

comment:1 Changed 12 years ago by jason

What does your memory usage look like?

comment:2 Changed 12 years ago by jason

The example above works fine for me on OSX 10.6 sage 4.6.alpha1+some patches

comment:3 Changed 12 years ago by fredrik.johansson

Memory usage grows to a few hundred megabytes (which is strange, but not necessarily a bug by itself), but I have 3GB of RAM so it shouldn't be a problem.

I wonder if this might be related:

sage: A = MatrixSpace(RDF,1000,1000).random_element()
sage: B = MatrixSpace(RDF,1000,1000).random_element()
sage: C = A * B

Program received signal SIGSEGV, Segmentation fault.
0x00007fffeca1470d in ATL_dJIK40x40x40TN40x40x0_a1_b0 () from /home/fredrik/sage/local/lib/libatlas.so

comment:4 follow-up: Changed 11 years ago by rbeezer

All the examples above work just fine for me (repeatedly). 64-bit Ubuntu 10.04 on new-ish Intel i7 with 4.6.1.rc1.

comment:5 in reply to: ↑ 4 Changed 11 years ago by sivaldimarsson

I want to report similar problems on 64-bit ubuntu 10.04 with sage 4.6.1. The error will sometimes appear as Runtime Error and other times as SGISEGV (depending on matrices) and in borderline cases it will not appear consistently eventhough the same matrix is used

siv@siv-desktop:~/sage/sage-4.6.1-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux$ uname -a
Linux siv-desktop 2.6.32-28-generic #55-Ubuntu SMP Mon Jan 10 23:42:43 UTC 2011 x86_64 GNU/Linux
siv@siv-desktop:~/sage/sage-4.6.1-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux$ lsb_release -a
LSB Version:    core-2.0-amd64:core-2.0-noarch:core-3.0-amd64:core-3.0-noarch:core-3.1-amd64:core-3.1-noarch:core-3.2-amd64:core-3.2-noarch:core-4.0-amd64:core-4.0-noarch:cxx-3.0-amd64:cxx-3.0-noarch:cxx-3.1-amd64:cxx-3.1-noarch:cxx-3.2-amd64:cxx-3.2-noarch:cxx-4.0-amd64:cxx-4.0-noarch:desktop-3.1-amd64:desktop-3.1-noarch:desktop-3.2-amd64:desktop-3.2-noarch:desktop-4.0-amd64:desktop-4.0-noarch:graphics-2.0-amd64:graphics-2.0-noarch:graphics-3.0-amd64:graphics-3.0-noarch:graphics-3.1-amd64:graphics-3.1-noarch:graphics-3.2-amd64:graphics-3.2-noarch:graphics-4.0-amd64:graphics-4.0-noarch:printing-3.2-amd64:printing-3.2-noarch:printing-4.0-amd64:printing-4.0-noarch:qt4-3.1-amd64:qt4-3.1-noarch
Distributor ID: Ubuntu
Description:    Ubuntu 10.04.1 LTS
Release:        10.04
Codename:       lucid
siv@siv-desktop:~/sage/sage-4.6.1-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux$ ./sage
----------------------------------------------------------------------
| Sage Version 4.6.1, Release Date: 2011-01-11                       |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage: M = Matrix(QQ, [[1 for dummy in range(125)]])
sage: V = M.right_kernel()
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)

/home/siv/sage/sage-4.6.1-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/<ipython console> in <module>()

/home/siv/sage/sage-4.6.1-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/local/lib/python2.6/site-packages/sage/matrix/matrix_rational_dense.so in sage.matrix.matrix_rational_dense.Matrix_rational_dense.right_kernel (sage/matrix/matrix_rational_dense.c:13025)()

/home/siv/sage/sage-4.6.1-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/local/lib/python2.6/site-packages/sage/matrix/matrix2.so in sage.matrix.matrix2.Matrix.column_space (sage/matrix/matrix2.c:15609)()

/home/siv/sage/sage-4.6.1-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/local/lib/python2.6/site-packages/sage/matrix/matrix2.so in sage.matrix.matrix2.Matrix.column_module (sage/matrix/matrix2.c:15563)()

/home/siv/sage/sage-4.6.1-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/local/lib/python2.6/site-packages/sage/matrix/matrix2.so in sage.matrix.matrix2.Matrix.row_module (sage/matrix/matrix2.c:15249)()

/home/siv/sage/sage-4.6.1-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/local/lib/python2.6/site-packages/sage/modules/free_module.pyc in span(self, gens, base_ring, check, already_echelonized)
   3154         if base_ring is None or base_ring == self.base_ring():
   3155             return FreeModule_submodule_field(
-> 3156                 self.ambient_module(), gens=gens, check=check, already_echelonized=already_echelonized)
   3157         else:
   3158             try:

/home/siv/sage/sage-4.6.1-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/local/lib/python2.6/site-packages/sage/modules/free_module.pyc in __init__(self, ambient, gens, check, already_echelonized)
   5943             raise TypeError, "Argument gens (= %s) must be a list, tuple, or sequence."%gens
   5944         FreeModule_submodule_with_basis_field.__init__(self, ambient, basis=gens, check=check, 
-> 5945             echelonize=not already_echelonized, already_echelonized=already_echelonized)
   5946 
   5947     def _repr_(self):

/home/siv/sage/sage-4.6.1-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/local/lib/python2.6/site-packages/sage/modules/free_module.pyc in __init__(self, ambient, basis, check, echelonize, echelonized_basis, already_echelonized)
   5743         FreeModule_submodule_with_basis_pid.__init__(
   5744             self, ambient, basis=basis, check=check, echelonize=echelonize, 
-> 5745             echelonized_basis=echelonized_basis, already_echelonized=already_echelonized)
   5746 
   5747     def _repr_(self):

/home/siv/sage/sage-4.6.1-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/local/lib/python2.6/site-packages/sage/modules/free_module.pyc in __init__(self, ambient, basis, check, echelonize, echelonized_basis, already_echelonized)
   4684                                 "the ambient vector space")
   4685         if echelonize and not already_echelonized:
-> 4686             basis = self._echelonized_basis(ambient, basis)
   4687         R = ambient.base_ring()
   4688         # The following is WRONG - we should call __init__ of

/home/siv/sage/sage-4.6.1-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/local/lib/python2.6/site-packages/sage/modules/free_module.pyc in _echelonized_basis(self, ambient, basis)
   5874             sparse=ambient.is_sparse())
   5875         A = MAT(basis)
-> 5876         E = A.echelon_form()
   5877         # Return the first rank rows (i.e., the nonzero rows).
   5878         return E.rows()[:E.rank()]

/home/siv/sage/sage-4.6.1-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/local/lib/python2.6/site-packages/sage/matrix/matrix_rational_dense.so in sage.matrix.matrix_rational_dense.Matrix_rational_dense.echelon_form (sage/matrix/matrix_rational_dense.c:14410)()

/home/siv/sage/sage-4.6.1-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/local/lib/python2.6/site-packages/sage/matrix/matrix_rational_dense.so in sage.matrix.matrix_rational_dense.Matrix_rational_dense._echelon_form_padic (sage/matrix/matrix_rational_dense.c:14748)()

/home/siv/sage/sage-4.6.1-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/local/lib/python2.6/site-packages/sage/matrix/matrix_integer_dense.so in sage.matrix.matrix_integer_dense.Matrix_integer_dense._rational_echelon_via_solve (sage/matrix/matrix_integer_dense.c:28385)()

/home/siv/sage/sage-4.6.1-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/local/lib/python2.6/site-packages/sage/matrix/matrix_integer_dense.so in sage.matrix.matrix_integer_dense.Matrix_integer_dense.rank (sage/matrix/matrix_integer_dense.c:24590)()

/home/siv/sage/sage-4.6.1-linux-64bit-ubuntu_10.04.1_lts-x86_64-Linux/local/lib/python2.6/site-packages/sage/matrix/matrix_integer_dense.so in sage.matrix.matrix_integer_dense.Matrix_integer_dense._rank_modp (sage/matrix/matrix_integer_dense.c:24877)()

RuntimeError: 

comment:6 Changed 8 years ago by mmezzarobba

  • Milestone set to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

No activity on this issue for three years, and no one seems to have a clue what was going on--can we close the ticket?

comment:7 Changed 8 years ago by tscrim

  • Authors set to Travis Scrimshaw
  • Branch set to u/tscrim/ticket/10095
  • Commit set to 3a881677e4a83e4d4de51b95778fabadb5f4e7eb
  • Milestone changed from sage-duplicate/invalid/wontfix to sage-6.2

Actually, it seems to have been fixed sometime before 6.1:

sage: M = Matrix(QQ, [[1 for dummy in range(125)]])
sage: V = M.right_kernel()
sage: V
Vector space of degree 125 and dimension 124 over Rational Field
Basis matrix:
124 x 125 dense matrix over Rational Field
sage: MatrixSpace(ZZ,20,20)(1) \ MatrixSpace(ZZ,20,1).random_element()
20 x 1 dense matrix over Rational Field
sage: MatrixSpace(ZZ,200,200)(1) \ MatrixSpace(ZZ,200,1).random_element()
200 x 1 dense matrix over Rational Field

sage: get_memory_usage()
172.796875
sage: A = MatrixSpace(RDF,1000,1000).random_element()
sage: B = MatrixSpace(RDF,1000,1000).random_element()
sage: C = A * B
sage: get_memory_usage()
240.1328125

My guess is there was a memory leak that was plugged.

I've added a branch which contains the above examples as doctests which needs review.


New commits:

3a88167Added doctests to matrix_space.py.

comment:8 Changed 8 years ago by mmezzarobba

  • Status changed from needs_review to positive_review

comment:9 Changed 8 years ago by tscrim

  • Reviewers set to Marc Mezzarobba

Thanks Marc.

comment:10 Changed 8 years ago by vbraun

  • Branch changed from u/tscrim/ticket/10095 to 3a881677e4a83e4d4de51b95778fabadb5f4e7eb
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.