Opened 2 years ago
Closed 8 months ago
#23214 closed enhancement (fixed)
enhance sparse integer matrix with linbox (+ cleaning)
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage8.5 
Component:  linear algebra  Keywords:  linbox 
Cc:  cpernet, tscrim, tmonteil  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  Travis Scrimshaw, Vincent Klein 
Report Upstream:  N/A  Work issues:  
Branch:  98ac984 (Commits)  Commit:  98ac98478bedfaf6a2ac8d84da67253978e7e9ca 
Dependencies:  Stopgaps: 
Description (last modified by )
LinBox has algorithms to work with sparse matrices. This ticket provides the necessary interface for:
 solving sparse systems over integers
 computing determinant and rank
 computing minimal and characteristic polynomials
Some cleaning had to be done as a first step (used to be #26178).
LinBox issues
 Issue 118 (determinant hangs)
 Issue 138 (Compilation failure on OSX)
 Issue 144 (row index: unsigned long versus size_t)
(see also #22872 for the linbox task ticket)
Change History (65)
comment:1 Changed 22 months ago by
comment:2 Changed 22 months ago by
And combinatorics and geomtry and ... just waiting for upstream github issue 56.
comment:3 Changed 20 months ago by
That issue has been closed. Are we waiting on a release?
comment:4 Changed 20 months ago by
Indeed, Clément wrote on the github issue
Note that we're also planning on releasing all 3 libraries soon (within a few weeks), and I'll create a sage ticket for updating the spkg.
comment:5 Changed 20 months ago by
comment:6 Changed 14 months ago by
 Dependencies changed from #23158 to #24544
 Milestone changed from sage8.0 to sage8.3
comment:7 Changed 14 months ago by
 Cc tscrim added
 Description modified (diff)
 Summary changed from solving integer sparse linear system using LinBox to solve/det/rank for sparse integer matrix using LinBox
comment:8 Changed 14 months ago by
 Description modified (diff)
 Summary changed from solve/det/rank for sparse integer matrix using LinBox to enhance sparse integer matrix with linbox
comment:9 Changed 14 months ago by
 Branch set to u/vdelecroix/23214
 Commit set to 2712020f863309676e9da504ede9c34976c1d619
 Status changed from new to needs_review
New commits:
eb54e4b  24544: cleaning linbox headers

9d787d3  24544: fix matrix_modn_dense

99ed944  24544: fix matrix_modn_sparse

13f4de4  24544: fix documentation

a1e4933  24544: do not compile the sage extension support anymore

956610a  24544: remove linbox GFq from benchmarks

7e92d8e  23214: sparse integer matrices and LinBox

2712020  23214: empty conversion.pyx to make cython happy

comment:10 Changed 14 months ago by
 Description modified (diff)
comment:11 Changed 14 months ago by
This hangs forever
sage: m = diagonal_matrix(ZZ, 68, [2]*66 + [1,1]) sage: type(m) <type 'sage.matrix.matrix_integer_sparse.Matrix_integer_sparse'> sage: m.det()
(from matrix/matrix_integer_dense_hnf.py
)
comment:12 Changed 14 months ago by
 Description modified (diff)
comment:13 Changed 14 months ago by
 Commit changed from 2712020f863309676e9da504ede9c34976c1d619 to 1cd803714d3cdc6435a58649a4a7efebd9460c9c
comment:14 Changed 14 months ago by
 Commit changed from 1cd803714d3cdc6435a58649a4a7efebd9460c9c to 84236154543bf0b2dcf547dcd372d5605d949668
comment:15 Changed 14 months ago by
 Status changed from needs_review to needs_work
sage: Matrix(IntegerModRing(16), 3, 3, lambda i,j: i+j, sparse=True).determinant()  TypeError Traceback (most recent call last) <ipythoninput22d0c9b09dcc5> in <module>() > 1 Matrix(IntegerModRing(Integer(16)), Integer(3), Integer(3), lambda i,j: i+j, sparse=True).determinant() /usr/local/src/sageconfig/local/lib/python2.7/sitepackages/sage/matrix/matrix_modn_sparse.pyx in sage.matrix.matrix_modn_sparse.Matrix_modn_sparse.determinant (build/cythonized/sage/matrix/matrix_modn_sparse.cpp:10523)() 924 925 if algorithm is None or algorithm == "linbox": > 926 r, d = self._rank_det_linbox() 927 self.cache('rank', r) 928 self.cache('det', d) /usr/local/src/sageconfig/local/lib/python2.7/sitepackages/sage/matrix/matrix_modn_sparse.pyx in sage.matrix.matrix_modn_sparse.Matrix_modn_sparse._rank_det_linbox (build/cythonized/sage/matrix/matrix_modn_sparse.cpp:9553)() 766 767 if not is_prime(self.p): > 768 raise TypeError("only GF(p) supported via LinBox") 769 770 cdef Modular_int64 * F = new Modular_int64(self.p) TypeError: only GF(p) supported via LinBox
comment:16 Changed 12 months ago by
 Keywords linbox added
comment:17 Changed 11 months ago by
 Milestone changed from sage8.3 to sage8.4
update milestone 8.3 > 8.4
comment:18 Changed 10 months ago by
 Commit changed from 84236154543bf0b2dcf547dcd372d5605d949668 to 43babdeae57a36e1b40dcf22e4ba254b3d229e2c
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
2c157ff  24544: cleaning linbox headers

b037c87  24544: fix matrix_modn_dense

a12f0a1  24554: fix matrix modn sparse

52d8a34  24544: fix documentation

8acfbc9  24544: remove linbox GFq from benchmarks

43babde  23214: use linbox in sparse integer matrices

comment:19 Changed 10 months ago by
 Status changed from needs_work to needs_review
comment:20 Changed 10 months ago by
patchbot is happy :)
comment:21 Changed 10 months ago by
Oops, I got this confused with the other needs review linbox ticket where compiling on OSX was an issue, I'll try them both out together now I guess.
comment:22 Changed 10 months ago by
@alexjbest: this ticket strictly contains the commit of the other one #24544.
comment:23 Changed 10 months ago by
Small typo (missing leading colon): meth:`sage.matrix.matrix_sparse.Matrix_sparse.charpoly`
Otherwise I am happy with the current state (and will assume there are no failures on OSX).
comment:24 Changed 10 months ago by
 Commit changed from 43babdeae57a36e1b40dcf22e4ba254b3d229e2c to 1d8d266779da4d0e9078e2050d9bb861a2ac213b
Branch pushed to git repo; I updated commit sha1. New commits:
1d8d266  23214: small typo

comment:25 Changed 10 months ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
LGTM. Thanks. Alex, if you end up hitting an error during your testing, please revert.
comment:26 Changed 10 months ago by
 Status changed from positive_review to needs_work
Doesn't build on OSX:
[sagelib8.4.beta3] In file included from build/cythonized/sage/matrix/matrix_integer_sparse.cpp:708: [sagelib8.4.beta3] In file included from /Users/buildslavesage/slave/sage_git/build/local/include/linbox/matrix/densematrix.h:79: [sagelib8.4.beta3] In file included from /Users/buildslavesage/slave/sage_git/build/local/include/linbox/matrix/densematrix/blasmatrix.h:44: [sagelib8.4.beta3] /Users/buildslavesage/slave/sage_git/build/local/include/linbox/vector/blasvector.h:306:11: error: member reference base type 'const long' is not a structure or union [sagelib8.4.beta3] _size(V.size()),_1stride(1),_rep(V.size(), F.zero),_ptr(&_rep[0]),_field(&F) [sagelib8.4.beta3] ~^~~~~ [sagelib8.4.beta3] build/cythonized/sage/matrix/matrix_integer_sparse.cpp:10932:21: note: in instantiation of function template specialization 'LinBox::BlasVector<Givaro::ZRing<Givaro::Integer>, std::__1::vector<Givaro::Integer, std::__1::allocator<Givaro::Integer> > >::BlasVector<long>' requested here [sagelib8.4.beta3] __pyx_v_res = new LinBox::DenseVector<Givaro::ZRing<Givaro::Integer>>(__pyx_v_givZZ, __pyx_v_self>__pyx_base.__pyx_base.__pyx_base.__pyx_base.__pyx_base._ncols); [sagelib8.4.beta3] ^ [sagelib8.4.beta3] In file included from build/cythonized/sage/matrix/matrix_integer_sparse.cpp:708: [sagelib8.4.beta3] In file included from /Users/buildslavesage/slave/sage_git/build/local/include/linbox/matrix/densematrix.h:79: [sagelib8.4.beta3] In file included from /Users/buildslavesage/slave/sage_git/build/local/include/linbox/matrix/densematrix/blasmatrix.h:44: [sagelib8.4.beta3] /Users/buildslavesage/slave/sage_git/build/local/include/linbox/vector/blasvector.h:306:38: error: member reference base type 'const long' is not a structure or union [sagelib8.4.beta3] _size(V.size()),_1stride(1),_rep(V.size(), F.zero),_ptr(&_rep[0]),_field(&F) [sagelib8.4.beta3] ~^~~~~ [sagelib8.4.beta3] /Users/buildslavesage/slave/sage_git/build/local/include/linbox/vector/blasvector.h:306:61: warning: field '_rep' is uninitialized when used here [Wuninitialized] [sagelib8.4.beta3] _size(V.size()),_1stride(1),_rep(V.size(), F.zero),_ptr(&_rep[0]),_field(&F) [sagelib8.4.beta3] ^ [sagelib8.4.beta3] /Users/buildslavesage/slave/sage_git/build/local/include/linbox/vector/blasvector.h:129:13: error: type 'long' cannot be used prior to '::' because it has no members [sagelib8.4.beta3] typename OtherVector::const_iterator jt = V.begin(); [sagelib8.4.beta3] ^ [sagelib8.4.beta3] /Users/buildslavesage/slave/sage_git/build/local/include/linbox/vector/blasvector.h:311:4: note: in instantiation of function template specialization 'LinBox::BlasVector<Givaro::ZRing<Givaro::Integer>, std::__1::vector<Givaro::Integer, std::__1::allocator<Givaro::Integer> > >::createBlasVector<long>' requested here [sagelib8.4.beta3] createBlasVector(V); [sagelib8.4.beta3] ^ [sagelib8.4.beta3] build/cythonized/sage/matrix/matrix_integer_sparse.cpp:10932:21: note: in instantiation of function template specialization 'LinBox::BlasVector<Givaro::ZRing<Givaro::Integer>, std::__1::vector<Givaro::Integer, std::__1::allocator<Givaro::Integer> > >::BlasVector<long>' requested here [sagelib8.4.beta3] __pyx_v_res = new LinBox::DenseVector<Givaro::ZRing<Givaro::Integer>>(__pyx_v_givZZ, __pyx_v_self>__pyx_base.__pyx_base.__pyx_base.__pyx_base.__pyx_base._ncols); [sagelib8.4.beta3] ^ [sagelib8.4.beta3] 8 warnings and 3 errors generated. [sagelib8.4.beta3] error: command 'gcc' failed with exit status 1
comment:27 Changed 10 months ago by
With the relevant lines from matrix_integer_sparse.cpp
:
/* "sage/matrix/matrix_integer_sparse.pyx":1074 * cdef linbox.SparseMatrix_integer * A = new_linbox_matrix_integer_sparse(givZZ, self) * cdef linbox.DenseVector_integer * b = new_linbox_vector_integer_dense(givZZ, v) * cdef linbox.DenseVector_integer * res = new linbox.DenseVector_integer(givZZ, self._ncols) # <<<<<<<<<<<<<< * cdef givaro.Integer D * */ __pyx_v_res = new LinBox::DenseVector<Givaro::ZRing<Givaro::Integer>>(__pyx_v_givZZ, __pyx_v_self>__pyx_base.__pyx_base.__pyx_base.__pyx_base.__pyx_base._ncols);
comment:28 Changed 9 months ago by
This compile failure can be reproduced outside of sage. Issue opened on upstream linbox/issues/138.
comment:29 Changed 9 months ago by
 Description modified (diff)
comment:30 Changed 9 months ago by
 Description modified (diff)
comment:31 followup: ↓ 33 Changed 8 months ago by
what is the status of this ticket ?
comment:32 Changed 8 months ago by
 Dependencies #24544 deleted
comment:33 in reply to: ↑ 31 Changed 8 months ago by
comment:34 followup: ↓ 35 Changed 8 months ago by
As mentionned in linbox/issues/138, passing a long instead of a size_t to BlasVector? constructor is causing an weird type resolution problem, which I can still not fully understand. Meanwhile 2 options can fix the problem:
 have sage cython code send size_t parameters to LinBox, as required by the interface. This means doing explicit casts (inelegant) or changing the type of ncols and nrows in matrix classes (heavy change)
 removing the templated constructor in LinBox::BlasVector that is in the way. This change is not harmfull for the library, but it feels not right to remove features for some weird type resolution issue on OSX due to sage not respecting the interface. This second option would also delay the fixing of this issue to the integration of the next release of LinBox or patching sage's LinBox.
comment:35 in reply to: ↑ 34 Changed 8 months ago by
Replying to cpernet:
As mentionned in linbox/issues/138, passing a long instead of a size_t to BlasVector? constructor is causing an weird type resolution problem, which I can still not fully understand. Meanwhile 2 options can fix the problem:
 have sage cython code send size_t parameters to LinBox, as required by the interface. This means doing explicit casts (inelegant) or changing the type of ncols and nrows in matrix classes (heavy change)
One possible obstruction for the change Py_ssize_t
> size_t
is that matrices can be accessed with negative indices. Perhaps it is not so dramatic. However, if this change happend we want to do it coherently with vectors, etc.
For the other proposition, calling properly LinBox with casting where necessary do not look too ugly for me. We can arrange so that it only appears in the code at sage/libs/linbox/
.
 removing the templated constructor in LinBox::BlasVector that is in the way. This change is not harmfull for the library, but it feels not right to remove features for some weird type resolution issue on OSX due to sage not respecting the interface. This second option would also delay the fixing of this issue to the integration of the next release of LinBox or patching sage's LinBox.
comment:36 Changed 8 months ago by
 Commit changed from 1d8d266779da4d0e9078e2050d9bb861a2ac213b to 4ec1fa51976f71392a47e1c54116115a6f47a385
comment:37 followup: ↓ 39 Changed 8 months ago by
 Status changed from needs_work to needs_review
Please Mac OSX testing needed!
comment:38 Changed 8 months ago by
 Description modified (diff)
 Milestone changed from sage8.4 to sage8.5
 Summary changed from enhance sparse integer matrix with linbox to enhance sparse integer matrix with linbox (+ cleaning)
comment:39 in reply to: ↑ 37 Changed 8 months ago by
comment:40 Changed 8 months ago by
We have almost the same error but for matrix_modn_sparse
.
[sagelib8.5.beta1] In file included from build/cythonized/sage/matrix/matrix_modn_sparse.cpp:725: [sagelib8.5.beta1] In file included from /Users/doctorant/sage/local/include/linbox/matrix/densematrix.h:79: [sagelib8.5.beta1] In file included from /Users/doctorant/sage/local/include/linbox/matrix/densematrix/blasmatrix.h:44: [sagelib8.5.beta1] /Users/doctorant/sage/local/include/linbox/vector/blasvector.h:306:11: error: member reference base type 'const long' is not a structure or union [sagelib8.5.beta1] _size(V.size()),_1stride(1),_rep(V.size(), F.zero),_ptr(&_rep[0]),_field(&F) [sagelib8.5.beta1] ~^~~~~ [sagelib8.5.beta1] build/cythonized/sage/matrix/matrix_modn_sparse.cpp:12191:19: note: in instantiation of function template specialization 'LinBox::BlasVector<Givaro::ZRing<Givaro::Integer>, std::__1::vector<Givaro::Integer, std::__1::allocator<Givaro::Integer> > >::BlasVector<long>' requested here [sagelib8.5.beta1] __pyx_v_b = new LinBox::DenseVector<Givaro::ZRing<Givaro::Integer>>(__pyx_v_givZZ, __pyx_v_self>__pyx_base.__pyx_base.__pyx_base.__pyx_base.__pyx_base._nrows); [sagelib8.5.beta1] ^ [sagelib8.5.beta1] In file included from build/cythonized/sage/matrix/matrix_modn_sparse.cpp:725: [sagelib8.5.beta1] In file included from /Users/doctorant/sage/local/include/linbox/matrix/densematrix.h:79: [sagelib8.5.beta1] In file included from /Users/doctorant/sage/local/include/linbox/matrix/densematrix/blasmatrix.h:44: [sagelib8.5.beta1] /Users/doctorant/sage/local/include/linbox/vector/blasvector.h:306:38: error: member reference base type 'const long' is not a structure or union [sagelib8.5.beta1] _size(V.size()),_1stride(1),_rep(V.size(), F.zero),_ptr(&_rep[0]),_field(&F) [sagelib8.5.beta1] ~^~~~~ [sagelib8.5.beta1] /Users/doctorant/sage/local/include/linbox/vector/blasvector.h:306:61: warning: field '_rep' is uninitialized when used here [Wuninitialized] [sagelib8.5.beta1] _size(V.size()),_1stride(1),_rep(V.size(), F.zero),_ptr(&_rep[0]),_field(&F) [sagelib8.5.beta1] ^ [sagelib8.5.beta1] /Users/doctorant/sage/local/include/linbox/vector/blasvector.h:129:13: error: type 'long' cannot be used prior to '::' because it has no members [sagelib8.5.beta1] typename OtherVector::const_iterator jt = V.begin(); [sagelib8.5.beta1] ^ [sagelib8.5.beta1] /Users/doctorant/sage/local/include/linbox/vector/blasvector.h:311:4: note: in instantiation of function template specialization 'LinBox::BlasVector<Givaro::ZRing<Givaro::Integer>, std::__1::vector<Givaro::Integer, std::__1::allocator<Givaro::Integer> > >::createBlasVector<long>' requested here [sagelib8.5.beta1] createBlasVector(V); [sagelib8.5.beta1] ^ [sagelib8.5.beta1] build/cythonized/sage/matrix/matrix_modn_sparse.cpp:12191:19: note: in instantiation of function template specialization 'LinBox::BlasVector<Givaro::ZRing<Givaro::Integer>, std::__1::vector<Givaro::Integer, std::__1::allocator<Givaro::Integer> > >::BlasVector<long>' requested here [sagelib8.5.beta1] __pyx_v_b = new LinBox::DenseVector<Givaro::ZRing<Givaro::Integer>>(__pyx_v_givZZ, __pyx_v_self>__pyx_base.__pyx_base.__pyx_base.__pyx_base.__pyx_base._nrows); [sagelib8.5.beta1] ^ [sagelib8.5.beta1] 8 warnings and 3 errors generated. [sagelib8.5.beta1] error: command 'gcc' failed with exit status 1 [sagelib8.5.beta1] [ 3/86] make[4]: *** [sage] Error 1
comment:41 Changed 8 months ago by
 Branch changed from u/vdelecroix/23214 to u/cpernet/23214
comment:42 Changed 8 months ago by
 Commit changed from 4ec1fa51976f71392a47e1c54116115a6f47a385 to d0f5a9964550afec7d36827641de9ce929c06d1f
There was indeed some casts missing. I pushed a fixed and checked that all casts have been done. @vklein, could you check again please?
New commits:
d0f5a99  fix missing cast to size_t

comment:43 Changed 8 months ago by
Sure.
comment:44 Changed 8 months ago by
I got 3 failing doctests, see patchbot.
comment:45 Changed 8 months ago by
Tests are still running on OSX. That mean off course that all compilation problems are solved.
comment:46 Changed 8 months ago by
I get 5 errors on OSX:
sage t long src/sage/combinat/designs/ext_rep.py # Killed due to abort sage t long src/sage/doctest/external.py # Killed due to abort sage t long src/sage/matrix/matrix_modn_sparse.pyx # 3 doctests failed
matrix_modn_sparse.pyx
errors are the sames as the patchbot ones and the two others are not ticket dependent (see Justin C. Walker message in Sage 8.5.beta1 released ).
comment:47 Changed 8 months ago by
My bad. Error should be fixed now.
comment:48 Changed 8 months ago by
forgot to push ?
comment:49 Changed 8 months ago by
 Branch changed from u/cpernet/23214 to u/vdelecroix/23214
 Commit changed from d0f5a9964550afec7d36827641de9ce929c06d1f to ea33422553f347d9cb647ca212d3c5f91ecff354
comment:50 Changed 8 months ago by
There seems to be a test failure on one of the patchbots:
File "src/sage/matrix/matrix_space.py", line 1982, in sage.matrix.matrix_space.MatrixSpace._an_element_ Failed example: M.density() Expected: 99/1000000 Got: 49/500000 ********************************************************************** 1 item had failures: 1 of 7 in sage.matrix.matrix_space.MatrixSpace._an_element_ [383 tests, 1 failure, 6.40 s]  sage t long warnlong 54.6 src/sage/matrix/matrix_space.py # 1 doctest failed
Can you reproduce this locally (sorry, I cannot test this right now on my laptop)?
comment:51 Changed 8 months ago by
This concerns petitbonum
and, on the other hand, everything is fine on pc78math
.
I can not reproduce either.
comment:52 Changed 8 months ago by
 Cc tmonteil added
 Status changed from needs_review to needs_work
This one on tmonteildebianstretch32 (32 bits) is more annoying
[sagelib8.5.beta2] build/cythonized/sage/matrix/matrix_modn_sparse.cpp:8931:132: error: no matching function for call to 'LinBox::GaussDomain<Givaro::Modular<long long unsigned int, long long unsigned int> >::InPlaceLinearPivoting(size_t&, uint64_t&, LinBox::SparseMatrix<Givaro::Modular<long long unsigned int, long long unsigned int>, LinBox::SparseMatrixFormat::SparseSeq>&, size_t, size_t)' [sagelib8.5.beta2] (void)(__pyx_v_dom>InPlaceLinearPivoting(__pyx_v_A_rank, __pyx_v_A_det, (__pyx_v_A[0]), __pyx_v_A>rowdim(), __pyx_v_A>coldim())); [sagelib8.5.beta2] ^
@Clément: any clue of what might be wrong on 32 bit architecture?
comment:53 Changed 8 months ago by
@Clement: note that in LinBox the function is declared as (linbox/algorithms/gauss.h
line 227)
// Sparsest method // erases elements while computing rank/det. template <class _Matrix> unsigned long& InPlaceLinearPivoting(unsigned long &rank, Element& determinant, _Matrix &A, unsigned long Ni, unsigned long Nj) const;
Here I don't understand why rank
, Ni
and Nj
are not size_t
as they should rather be.
comment:54 Changed 8 months ago by
 Description modified (diff)
I filled the Issue 144 on linbox website.
comment:55 Changed 8 months ago by
 Commit changed from ea33422553f347d9cb647ca212d3c5f91ecff354 to 98ac98478bedfaf6a2ac8d84da67253978e7e9ca
Branch pushed to git repo; I updated commit sha1. New commits:
98ac984  23214: follow LinBox declarations

comment:56 Changed 8 months ago by
 Status changed from needs_work to needs_review
comment:57 followup: ↓ 59 Changed 8 months ago by
Good news: tests pass on 32 bits.
@vinklein: can you test one more time on OSX?
If everything went fine on OSX, I think we should get this ticket merged as is. I will change unsigned long
to size_t
as soon as LinBox gets updated.
comment:58 Changed 8 months ago by
This is also good on my machine and on a 32 and 64 bit patchbot.
comment:59 in reply to: ↑ 57 Changed 8 months ago by
comment:60 Changed 8 months ago by
Build & tests pass on OSX (98ac984
)
comment:61 Changed 8 months ago by
 Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Vincent Klein.
 Status changed from needs_review to positive_review
comment:62 Changed 8 months ago by
Merci Vincent!
comment:63 Changed 8 months ago by
 Reviewers changed from Travis Scrimshaw, Vincent Klein. to Travis Scrimshaw, Vincent Klein
comment:64 Changed 8 months ago by
De rien !
comment:65 Changed 8 months ago by
 Branch changed from u/vdelecroix/23214 to 98ac98478bedfaf6a2ac8d84da67253978e7e9ca
 Resolution set to fixed
 Status changed from positive_review to closed
Just to put in a plug for this, it would be very useful for various aspects of number theory, particularly dealing with Hecke operators which tend to be represented by sparse integer matrices.