the essence of the algorithm lies in the following observation suppose then one can express any index appearing in ( via pair ( )with where { and { similarlyone can express any index appearing in ( via pair ( )with where { and { identifying xt xt , and , we may re-express ( as xt , - - = , = ( observe that (because or )so that the inner sum over depends only on and define yt , : - , = computing each yt , requires ( operations in terms of the {yt , }( can be written as xt , - yt , = requiring ( operations to compute thuscalculating the dft using this two-step procedure requires ( ( )operationsrather than ( now supposing rm repeated application the above divide-and-conquer idea yields an -step procedure requiring ( ( rm )operations in particularif rk for all mwe have that rm and logr nso that the total number of operations is ( mo( logr ( )typicallythe radix is small (not necessarily primenumberfor instance further reading good reference book on matrix computations is golub and van loan [ useful list of many common vector and matrix calculus identities can be found in [ strang' introduction to linear algebra [ is classic textbookand his recent book [ combines linear algebra with the foundations of deep learning fast reliable algorithms for matrices with structure can be found in [ kolmogorov and fomin' masterpiece on the theory of functions and functional analysis [ still provides one of the best introductions to the topic popular choice for an advanced course in functional analysis is rudin [