Breakdown Rules

Base Rules

Definition

# In spiral-core\namespaces\spiral\transforms\dft\dft_rules.gi
 DFT_Base := rec(
        forTransposition := false,
        applicable       := nt -> nt.params[1] = 2 and not nt.hasTags(),
        apply            := (nt, C, cnt) -> F(2)
)

Twiddle Function for DFT

Tw1 := (n,d,k) -> Checked(
        IsPosIntSym(n), IsPosIntSym(d), IsIntSym(k),
        fCompose(dOmega(n,k),
                diagTensor(dLin(div(n,d), 1, 0, TInt),
                        dLin(d, 1, 0, TInt))));

Rule Methods

PrintActiveRules(DFT);          # rules for DFT currently active
DFT_Base.switch;                # filed in rule to determine active
t := DFT(2);
DFT_Base.applicable(t); # is the rule applicable
DFT_Base.children(t);           # all possible Algorithmic choices
DFT_Base.apply(t, [], []);      # t->spl for a particular choice

Cooley-Tukey Rule

Definition

# In spiral-core\namespaces\spiral\transforms\dft\dft_rules.gi
DFT_CT := rec(
        maxSize       := false,
        forcePrimeFactor := false,
        applicable := (self, nt) >> nt.params[1] > 2
                and not nt.hasTags()
                and (self.maxSize=false or nt.params[1] <= self.maxSize)
                and not IsPrime(nt.params[1])
                and When(self.forcePrimeFactor, not
                                 DFT_GoodThomas.applicable(nt), true),
        children  := nt -> Map2(DivisorPairs(nt.params[1]),
                        (m,n) -> [ DFT(m, nt.params[2] mod m),
                                           DFT(n, nt.params[2] mod n) ]),
        apply := (nt, C, cnt) -> let(mn := nt.params[1],
                                m := Rows(C[1]), n := Rows(C[2]),
                        Tensor(C[1], I(n)) *
                        Diag(fPrecompute(Tw1(mn, n, nt.params[2]))) *
                        Tensor(I(m), C[2]) *
                        L(mn, m)
                )
        )

Applicability

Cooley Tukey requires a non-prime size.

t := DFT(2);
t1 := DFT(4);
t2 := DFT(8);
t3 := DFT(20);

DFT_CT.applicable(t);           # see for which sized DFT_CT
DFT_CT.applicable(DFT(5));      # is applicable
DFT_CT.applicable(t1);
DFT_CT.applicable(t2);
DFT_CT.applicable(t3);

Children: Algorithmic Choices

c1 := DFT_CT.children(t2);      # enumerate all algorithmic choices
c2 := DFT_CT.children(t2);
c3 := DFT_CT.children(t3);

Expand DFT(8) by Hand

s := DFT_Base.apply(t, [], []); # expand DFT(2) -> F(2)
s1 := DFT_CT.apply(t1, [s, s], [t, t]);         # DFT(4) -> SPL
s2 := DFT_CT.apply(t2, [s1, s], [t1, t]);       # DFT(8) -> SPL
MatSPL(t2) = MatSPL(s2);

Ruletrees and SPL Revisited

From Transform to SPL Formula

n := 8; k := -1;                        # transform parameters
opts := CopyFields(SpiralDefaults,      # local configuration
        rec(breakdownRules := rec(
                DFT := [DFT_Base,
                CopyFields(DFT_CT, rec(maxSize := 20))])));
t := DFT(n, k);                 # transform
rt := RandomRuleTree(t, opts);  # get rule tree
spl := SPLRuleTree(rt);         # SPL formula

Impact of Configuration

PrintActiveRules(DFT);
opts.breakdownRules.DFT;
DFT_CT.maxSize;         # global configuration unchanged
ct := Filtered(opts.breakdownRules.DFT, i->i.name =  DFT_CT.name)[1];
ct.maxSize;                     # access local configuration
t2 := DFT(21);                  # works with global but not local opts
rt := RandomRuleTree(t2, SpiralDefaults);
rt2 := RandomRuleTree(t2, opts);
FindUnexpandableNonterminal(t2, opts);  # Where do we fail?
ct.maxSize := false;                            # remove guard in DFT_CT
rt2 := RandomRuleTree(t2, opts);                # try again
FindUnexpandableNonterminal(t2, opts);  # Where do we fail now?