#16116: Multiplication of dense cyclotomic matrices should be faster
-------------------------------------------------+-------------------------
Reporter: jipilab | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.4
Component: number fields | Resolution:
Keywords: cyclotomic field, matrix, | Merged in:
multiplication, benchmark, days57 | Reviewers:
Authors: | Work issues:
Report Upstream: N/A | Commit:
Branch: | Stopgaps:
Dependencies: |
-------------------------------------------------+-------------------------
Comment (by vdelecroix):
Replying to [comment:8 was]:
> Replying to [comment:7 vdelecroix]:
> > Hello,
> >
> > I reformatted your example such that they fit in less lines (it can
easily switched back to your original version if you do not like it).
> >
> > I had a quick look at the code for dense cyclotomic matrices. The
implementation is quite old and uses a lot of reduction mod p (even for
multiplication). The code calls a lot of Python code like creating a
finite field, creating a matrix space, etc which are relatively slow
compared to a small matrix multiplication. Did you try multiplying larger
matrices (i.e. 10x10 or 15x15)?
>
> I designed and implemented the algorithm for dense cyclotomic matrices.
We were optimizing for larger matrices... which in the context of modular
forms means at least 100 rows (and often much, much more). GAP/pari on
the other hand optimize for relatively tiny matrices. The asymptotically
fast algorithms for large matrices are totally different than for small...
All right. I now understand better what I read! I see two possibilities.
1) [easy one] We add a test in the matrix space constructor:
- if the size is small -> use the generic implementation of dense
matrices
- if the size is large -> use your optimized version
This requires a bit of benchmark.
2) [better one] Wrap pari matrices for small sizes or add a another
multiplication on the current datatype that is fast on small matrices.
Vincent
--
Ticket URL: <http://trac.sagemath.org/ticket/16116#comment:9>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
