Here is an approach which I have found, but please don't be discouraged from answering if you also have ideas. I often upvote anything helpful even if it is not the answer I seek.
Viewed in the language of matrices, the FFT provides us a factorization of the DFT matrix $\bf D$:
$$\bf D = F_N\cdots F_1$$
Where each $\bf F_k$ is a sparse matrix with elements of each row only non-zero in a small prime number of positions. If number of samples (vector space dimension) considered is a power of two, this prime is often $2$. We will show how to utilize this factorization as a part of building a Fourier frame. First we will just stress the incredible smoothness of the harmonic functions $\sin, \cos$ which are basis functions of the Fourier transform.
What is nice about smooth functions is that even with relatively primitive interpolation techniques, we will get high precision. We will not make any proof of this here, but we will consider a linear interpolation on two samples. It basically is a linear weighting with sum 1. Each function value we can calculate this way. This requires 2 non-zero values for each row in a matrix - same as for the $\bf F_k$ matrices above!
So assume we have a set of matrices performing this linear interpolation $\bf P_k$ with some scaling, say for example $t\to \alpha_k t$, where for example $\alpha_k =1.10$ would mean our new frame vectors would be sines and cosines 10% stretched in time dimension.
We could basically calculate sets of $N-1$ different $\alpha_k$ and still only need to double the computational load, since all of them would benefit from the initial $\bf D$ factorization into the $\bf F_k$. So if we do this cleverly, for example with a filter network, we can save huge amounts of computations.
The computations above would be $$\bf P_1 F_N \cdots F_1\\\vdots\\P_N F_N \cdots F_1$$
Where the common part $\bf D$ would be calculated jointly and then fed to $N$ different branches in a filter network each multiplying with a sparse linear interpolation matrix like the one below. When applied it shrinks all frequencies of the original FFT by a factor $\alpha = 1.05 \approx 63/60$.
Best Answer
Fourier Transform is a function.
Fast Fourier Transform is an algorithm.
It is similar to the relationship between division and long division. Division is a function, long division is a way to compute the function.