Opened 13 years ago

Closed 7 years ago

#1169 closed enhancement (duplicate)

NTL cache-friendly FFT routines

Reported by: dmharvey Owned by: somebody
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: basic arithmetic Keywords:
Cc: vbraun Merged in:
Authors: Reviewers: Jean-Pierre Flori
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

I've written a more cache-friendly version of NTL's FFT routines. This may speed up NTL's polynomial arithmetic for polynomials of very high degree (e.g. > 100000) with small coefficients. For example I get a speedup of about 2x on sage.math.

BEFORE INCLUDING IN SAGE, someone needs to write some automatic tuning code, otherwise it might GREATLY SLOW DOWN arithmetic for small polynomials, which would be very stupid. See my website for code and more details:

http://math.harvard.edu/~dmharvey/code/ntl-fft/

Change History (7)

comment:1 Changed 13 years ago by mabshoff

  • Milestone set to sage-2.9

comment:2 Changed 12 years ago by mabshoff

David,

what is the status here? It seems that your website does contain the code.

Cheers,

Michael

comment:3 Changed 12 years ago by dmharvey

Yes it does, but it doesn't have tuning code and I don't have time to work on it now. Without proper tuning it is just as likely to make things slower.

comment:4 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:5 Changed 8 years ago by jpflori

  • Cc vbraun added
  • Milestone changed from sage-5.13 to sage-duplicate/invalid/wontfix
  • Report Upstream set to N/A
  • Status changed from new to needs_review

I think this code has been integrated (somehow) into NTL 6.0. So #14876 should supercede this.

comment:6 Changed 7 years ago by jpflori

  • Reviewers set to Jean-Pierre Flori
  • Status changed from needs_review to positive_review

NTL 6.0.0 is on its way.

comment:7 Changed 7 years ago by vbraun

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.