compute [ zn ln- ] compute steps and are (up to constantsin the form of an idftand step is in the form of dft these are computable via the fft (section in ( ln ntime step is dot product computable in (ntime thusthe circular convolution can be computed with the aid of the fft in ( ln ntime one can also efficiently compute the product of an toeplitz matrix and an vector in ( ln ntime by embedding into circulant matrix of size nx namelydefine cb where tn- tn- -( - -( - - - - - -( - then product of the form ta can be computed in ( ln ntimesince we may write # ta ba the left-hand side is product of circulant matrix with vector of length nand so can be computed in ( ln ntime via the fftas previously discussed conceptuallyone can also solve equations of the form cx for given vector cn and circulant matrix (corresponding to cn assuming all its eigenvalues are non-zerovia the following four steps compute fb/ compute fc compute / [ / zn /ln- ] compute fp once againsteps and are (up to constantsin the form of an idftand step is in the form of dftall of which are computable via the fft in ( ln ntimeand step is computable in (ntimemeaning the solution can be computed using the fft in ( ln ntime fast fourier transform fast fourier transform the fast fourier transform (fftis numerical algorithm for the fast evaluation of ( and ( by using divide-and-conquer strategythe algorithm reduces the computational complexity from ( (for the naive evaluation of the linear transformationto ( ln [