Re: some very slow mf* functions

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* J E Cremona [2018-11-21 10:39]:
> If I create the cuspidal newspace of level 11025, weight 2 trivial
> character using Snew=mfinit([11025,2],0) , which has dimension 317, and
> then compute some Hecke matrices, they take an enormous amount of time:
> several days for mfheckemat(Snew,29).  Why?
> 
> My own C++ modular symbols code can compute all Tp for p<100 in a few
> seconds, admittedly on the whole space (dimension 1684) not the newspace.

First, the design goals were different: we want arbitrary weight and
character and the code is generic: we optimized nothing for trivial
character or weight 2.

Second, our approach is "modular-symbols-free", which means it must be
inefficient for things modular symbols are good at; and will have
different strong points: for instance the new space is much easier for
us than the full space, since this is what the trace forms give us for free
(whereas we have to build the full space from all new subpieces)

Assuming the weight and character are fixed [ otherwise you have
additional dependency on k and order(chi) of course ], 

1) the complexity of mfinit is dominated by the cost computing the base change
matrix between Miller's basis and the horrible "random" basis afforded by
trace forms, which is O~(d^\omega + 1), with \omega = log_2 7 in PARI's
implementation.

2) the cost of computing T_p is O(d^3 p^{3/2})  [ this is really a 3 here,
not an \omega ]

This is somewhat mitigated by a very optimized implementation
[ esp. with Configure --mt=pthreads on a nice 96-core machine ]
but it is no surprise that a good modular symbols implementation turns
out to be orders of magnitude faster.

> Overall the new mf* functionality is fantastically useful -- but some
> spaces take orders of magnitude longer than other apparently similar ones,
> and it would be nice to understand why.

I am very interested in two (hopefully smaller) "apparently similar examples"
which differ by an order of magnitude.

In the end it boils down to trivial (but heavy) linear algebra which should
have comparable costs if the dimensions of the new spaces are comparable
[ assuming identical weight/Nebentypus as above ].

Thanks for using the mf* package ! :-)

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`