Opened 12 years ago

# New classes for matrices and vectors over Z/NZ with N >= 46341

Reported by: Owned by: David Roe jason, was major sage-6.4 linear algebra padics, modular arithmetic Jason Grout, Clément Pernet David Roe N/A

### Description

Sage currently has specialized classes for matrices and vectors over Z/nZ with n < 46341, used for multi-modular algorithms over Z. Once this boundary is passed, performance drops off.

This ticket aims to implement an analogous class for larger N, using an array of mpz_t's as the underlying representation.

One of the benefits is speed: determinants in particular should show a big speedup.

### comment:2 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11 → sage-5.12

### comment:3 Changed 9 years ago by For batch modifications

Milestone: sage-6.1 → sage-6.2

### comment:4 Changed 9 years ago by For batch modifications

Milestone: sage-6.2 → sage-6.3

### comment:5 Changed 8 years ago by For batch modifications

Milestone: sage-6.3 → sage-6.4

### comment:7 Changed 5 years ago by Clément Pernet

Diging out this outdated ticket. Things have changed many times since then, so it might be relevant to close it. However, there still remain an issue at the border when fflas-ffpack being used for matrix_modn_dense.

In the following experiments:

```sage: for i in range(30):
....:     p=next_prime(2**(i+1))
....:     t=time.clock()
....:     d=random_matrix(GF(p),2000,2000).det()
....:     print(i+1,p,(time.clock()-t)*1000)
....:
(1, 3, 508.6589999999944)
(2, 5, 532.3750000000018)
(3, 11, 550.8360000000039)
(4, 17, 574.7530000000154)
(5, 37, 587.5880000000109)
(6, 67, 606.4110000000085)
(7, 131, 614.6369999999877)
(8, 257, 935.7809999999915)
(9, 521, 943.7840000000222)
(10, 1031, 834.3969999999956)
(11, 2053, 835.2339999999856)
(12, 4099, 845.3449999999805)
(13, 8209, 878.2430000000261)
(14, 16411, 917.9200000000094)
(15, 32771, 922.7109999999925)
(16, 65537, 944.1960000000051)
(17, 131101, 946.4779999999848)
(18, 262147, 938.7389999999982)
(19, 524309, 954.8000000000059)
(20, 1048583, 967.0779999999866)
(21, 2097169, 980.2110000000255)
(22, 4194319, 1025.5329999999958)
(23, 8388617, 38899.896000000015)
(24, 16777259, 38043.026999999995)
```

one sees the threshold near 8 bits for the switch from float to double, and the threshold of 23bits when the generic implementation gets used. There is a 40x slowdown there, which is a shame.

To smooth things out, one could consider,

• using fflas-ffpack over int64_t, which would move the slow down threshold to about 29-30bits,
• convert larger word-size field elements to the RNS representation in fflas-ffpack which would perform better than the current implementation.
Note: See TracTickets for help on using tickets.