Opened 12 years ago

Last modified 5 years ago

#11161 new enhancement

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

Reported by: David Roe Owned by: jason, was
Priority: major Milestone: sage-6.4
Component: linear algebra Keywords: padics, modular arithmetic
Cc: Jason Grout, Clément Pernet Merged in:
Authors: David Roe Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

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.

Change History (7)

comment:1 Changed 12 years ago by Jason Grout

Cc: Jason Grout added

comment:2 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11sage-5.12

comment:3 Changed 9 years ago by For batch modifications

Milestone: sage-6.1sage-6.2

comment:4 Changed 9 years ago by For batch modifications

Milestone: sage-6.2sage-6.3

comment:5 Changed 8 years ago by For batch modifications

Milestone: sage-6.3sage-6.4

comment:6 Changed 7 years ago by Clément Pernet

Cc: Clément Pernet added

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.