Skip to content

PFA implementation #105

@dannys4

Description

@dannys4

I think the major missing algorithm in this package is the prime-factorization algorithm for mixed-radix FFTs where the factors are co-prime. I'm not entirely sure, but I think this is why the composite benchmark is substantially worse than the rest relative to FFTW for small-size ffts.

This one has some serious considerations for a few reasons:

  • which radices to choose in a many-composite algorithm?
  • How to effectively incorporate this into the callgraph?
  • Is this actually any better? I have no idea

For completeness, I should note that I've previously implemented Rader's algorithm at some point (I'm not sure if in C++ or julia...) and it did not work well at all unless your prime is length $2^k - 1$, which I'll leave until someone actually struggles with the use-case.

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions