cleaning of linbox for dense integer matrices

[videlec]

Various cleaning to the linbox interface (sage.libs.linbox) and Sage dense integer matrices (sage.matrix.matrix_integer_dense).

• implement a more direct linbox/flint interface in sage/libs/linbox/linbox_flint_interface.pyx (supersedes part of linbox-sage.C inside linbox)

• remove all mpz pointers from Matrix_integer_dense (that is the attributes
  bint _initialized_mpz, mpz_t * _entrie and mpz_t ** _rows) as
  well as the associated constructors/destructors (int _init_mpz(self), int _init_mpz_impl(self), int _init_linbox(self), void _dealloc_mpz(self))

• fix the following error

sage: matrix(ZZ, 2).det(algorithm='padic')
Traceback (most recent call last):
...
ImportError: No module named matrix_integer_dense_hnf

• add more examples and tests to the documentation

(see #22872 for the linbox task ticket)

CC: @ClementPernet @sagetrac-dlucas

Component: packages: standard

Keywords: linbox

Author: Vincent Delecroix

Branch/Commit: 0b082c2

Reviewer: Clément Pernet

Issue created by migration from https://trac.sagemath.org/ticket/22924

[videlec]

Branch: u/vdelecroix/22924

[videlec]

Commit: 38d9da3

[videlec]

New commits:

cca8edf	fix headers
38d9da3	Cleaning linbox interface of Matrix_integer_dense

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

86d8af3

Cleaning linbox interface of Matrix_integer_dense

[sagetrac-git]

Changed commit from 38d9da3 to 86d8af3

[sagetrac-git]

Changed commit from 86d8af3 to 4cae968

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

cccbe30	Cleaning linbox interface of Matrix_integer_dense
4cae968	22924: remove (instead of deprecate) code from linbox.pyx

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

09f6280

22924: get rid of spies

[sagetrac-git]

Changed commit from 4cae968 to 09f6280

[sagetrac-git]

Changed commit from 09f6280 to 69a140e

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

48cd83b	fix headers
3f5ec83	Cleaning linbox interface of Matrix_integer_dense
ef07ed5	22924: remove (instead of deprecate) code from linbox.pyx
69a140e	22924: get rid of spies

[videlec]

comment:9

(rebased on 8.0.b4)

[ClementPernet]

comment:10

Great.
Let's start with a few remarks:

1. Why do need the dependency on fix pxd header files #22886 ? That ticket is stalled and is therefore also blocking this one.
2. While we are changing a lot of stuff, I wouldn't mind getting rid of these ugly poly_linbox method, with a string parameter typ that determines whether to compute minpoly or charpoly. We should rather only have the 2 methods _minpoly_linbox_ and _charpoly_linbox_. There is not much duplicated code between these two, especially now after this clean-up.

[ClementPernet]

Reviewer: Clément Pernet

[videlec]

comment:12

Replying to @ClementPernet:

Great.

Thanks for having a look!

Let's start with a few remarks:

1. Why do need the dependency on fix pxd header files #22886 ? That ticket is stalled and is therefore also blocking this one.

I think that Cython compilation fails otherwise (I am trying again right now on top of 8.0.beta4... will take some time since I need to recompile the whole Sage after playing with #22493).

2. While we are changing a lot of stuff, I wouldn't mind getting rid of these ugly poly_linbox method, with a string parameter typ that determines whether to compute minpoly or charpoly. We should rather only have the 2 methods _minpoly_linbox_ and _charpoly_linbox_. There is not much duplicated code between these two, especially now after this clean-up.

The ticket only intends to clean matrix_integer_dense.pyx. The two functions you mention are actually removed from matrix/matrix_integer_dense.pyx but kept in libs/linbox/linbox_flint_interface.pyx (but note that the argument there is an integer). I can get rid of the following function in the interface

# set p to the minpoly or the charpoly of A
cdef inline void linbox_fmpz_mat_poly(fmpz_poly_t p, fmpz_mat_t A, int minpoly)

Is that what you want?

[ClementPernet]

comment:13

Replying to @videlec:

I can get rid of the following function in the interface

# set p to the minpoly or the charpoly of A
cdef inline void linbox_fmpz_mat_poly(fmpz_poly_t p, fmpz_mat_t A, int minpoly)

Is that what you want?

Ok sorry for the confusion. My remark indeed applies to the new libs/linbox_flint_interface.pyx.
Sure, it should definitely not be exposed through the new interface as it is an internal trick to factor out code. Then I also suggest to avoid this trick and simply write the two methods for the sake of clarity.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

55bdc0a	Cleaning linbox interface of Matrix_integer_dense
c8b95de	22924: remove (instead of deprecate) code from linbox.pyx
fcafa60	22924: get rid of spies
637fd87	22924: cleaning in linbox_flint_interface.pyx

[sagetrac-git]

Changed commit from 69a140e to 637fd87

[videlec]

comment:15

No dependency on #22886 anymore (it is needed for cylinbox but it is fine for this ticket).

I cleaned the flint interface a bit more than what you asked for.

[videlec]

Changed dependencies from #22886 to none

[videlec]

comment:16

I was wrong (and you were right). There is still def _poly_linbox(self, typ, var='x'): as a method of Matrix_integer_dense.

[videlec]

comment:17

By the way, I am adding tests and LinBox has trouble with the characteristic polynomial of the 0 x 0 matrix

sage: matrix([]).charpoly('y', 'linbox')
Traceback (most recent call last):
...
MemoryError: failed to allocate 2305843008945258512 bytes

Does it qualify as a bug? For now, I will add a special case in the interface LinBox/flint.

EDIT: and it hangs forever for minpoly.

[videlec]

comment:18

For minpoly it is written

        .. NOTE::

           Linbox charpoly disabled on 64-bit machines, since it hangs
           in many cases.

However, I do not see where this actually happens in the code. Do you know what this is?

[sagetrac-git]

Changed commit from 6b45893 to a75ec91

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

[ClementPernet]

comment:35

Also, I see some new code not directly related to the subject of the ticket (e.g. in _rational_kernel_flint, rational_kernel_iml), but this is rather ok for me as it is documentation improvement on routines related to the ticket).

[videlec]

comment:36

Replying to @ClementPernet:

Replying to @videlec:

I implemented your remarks. Though, I do not think that 6b45893 is reasonable.

Ok this seems indeed quite tedious. After browsing through the current use of size() for degree in LinBox, I would say it's rather safe to assume that the vector has been resized and therefore that the size method would return the degree. I was probably being too pedantic, sorry. I suggest to drop 6b45893.

I dropped it.

It would be fine for me to use degree however it is horribly complicated. Why is there a class Degree that is a trivial wrapper around a int64_t? Why could we not use degree directly as a method of a polynomial?

[videlec]

comment:37

Replying to @ClementPernet:

Also, I see some new code not directly related to the subject of the ticket (e.g. in _rational_kernel_flint, rational_kernel_iml), but this is rather ok for me as it is documentation improvement on routines related to the ticket).

It is. _rational_kernel_iml now uses fmpz_mat_to_mpz_array that was introduced in the ticket.

[ClementPernet]

comment:38

Replying to @videlec:

Feel free to open another one to deal with rings/finite_rings (and put me in cc if you do).

Done in #22966.

[ClementPernet]

comment:39

Let me try an explanation for this mess (which I agree should be simplified):

Replying to @videlec:

Why is there a class Degree that is a trivial wrapper around a int64_t?

I would have said: so as to deal with the degree of the 0 polynomial which is -1 and not size()-1=0

Why could we not use degree directly as a method of a polynomial?

I assume because in Givaro (and the whole LinBox ecosystem), the container (here givvector does not know about the semantic). It is the domain of computation (here GivPoly1Dom who does).

[videlec]

comment:40

Replying to @ClementPernet:

Let me try an explanation for this mess (which I agree should be simplified):

Replying to @videlec:

Why is there a class Degree that is a trivial wrapper around a int64_t?

I would have said: so as to deal with the degree of the 0 polynomial which is -1 and not size()-1=0

In LinBox you have size(0) = 1!? Why would you store the zero at all?

Why could we not use degree directly as a method of a polynomial?

I assume because in Givaro (and the whole LinBox ecosystem), the container (here givvector does not know about the semantic). It is the domain of computation (here GivPoly1Dom who does).

I see. This way is indeed more flexible.

[videlec]

comment:41

Tell me if there are other improvements to be done on this ticket.

[ClementPernet]

comment:42

Replying to @videlec:

I would have said: so as to deal with the degree of the 0 polynomial which is -1 and not size()-1=0

In LinBox you have size(0) = 1!? Why would you store the zero at all?

My mistake. Givaro actually resizes the 0 polynomial to an empty vector, so size-1 is always equal to the degree.

After a discussion with J-G. Dumas on the topic here are a few clarifications:

• the degree can be accessed in two ways:
  1. either through `Poly1Dom<..>::degree which silently resize the vector when there are leading zeros.
  2. direcrly by P.size()-1 when the programmer knows what she does and does not want to pay the price of a resize.

So it's fine to do it with size()-1 as in this ticket, since we know the polynomials handed by LinBox have correct size in this case.

• The class Degree was meant to provide a distinct type than the int64_t returned by size, in order to avoid mixing both approaches. Still the class is not quite satisfactory for the moment (degree (0 + 0)=-2 != -1). This has been fixed upstream in linbox-team/givaro@756005d

[ClementPernet]

comment:43

Ok, the ticket is now fine for me. -> positive review.

[ClementPernet]

comment:44

Sorry, two minor documentation typos to be fixed in src/sage/libs/linbox/linbox_flint_interface.pyx:

• line 10 "linbox-Sage.C" -> "linbox-sage.C"
• line 128 "preformed" -> "performed"
  Back in needs work.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

0b082c2

22924: typos

[sagetrac-git]

Changed commit from a75ec91 to 0b082c2

[ClementPernet]

comment:47

Fine then, back to positive review.

[videlec]

comment:48

Thanks for the review!

[vbraun]

Changed branch from u/vdelecroix/22924 to 0b082c2