Speeding up matrix multiplication?
I'm currently trying write code to compute with overconvergent modular symbols. In iterating a Hecke operator, the key (i.e. most time consuming) operation that is performed tons of times is simply taking the product of a large dense matrix say M with a vector v, both with integral entries.
More precisely, let p be a (relatively small) prime (think p=11) and N some integer (think 100). I have an N by N matrix and am interested in quickly computing the product M⋅v modulo pN.
I am simply using the intrinsic SAGE command of multiplying a matrix by a vector, and I was surprised to see that working with matrices over Z/pnZ was much (i.e. 10 times) slower than working with matrices over Z.
My question: is there a faster way to do this computation than using SAGE's intrinsic matrix times a vector command over Z?