Download Multiplicative Complexity, Convolution, and the DFT by Michael T. Heideman, C.S. Burrus PDF

By Michael T. Heideman, C.S. Burrus

This publication is meant to be a finished connection with multiplicative com­ plexity concept as utilized to electronic sign processing computations. even if a number of algorithms are integrated to demonstrate the idea, I focused extra at the boost­ ment of the speculation itself. Howie Johnson's infectious enthusiasm for designing effective DfT algorithms bought me drawn to this topic. i'm thankful to Prof. Sid Burrus for encouraging and assisting me during this attempt. i might additionally wish to thank Henrik Sorensen and Doug Jones for plenty of stimulating discussions. lowe an outstanding debt to Shmuel Winograd, who, virtually singlehandedly, supplied lots of the key theoretical effects that resulted in this current paintings. His monograph, mathematics Complexity o/Computations, brought me to the mechanism at the back of the proofs of theorems in multiplicative complexity. allowing me to come to his past papers and savor the splendor of his equipment for deriving the speculation. the second one key paintings that inspired me was once the paper through Louis Auslander and Winograd on multiplicative complexity of semilinear platforms outlined by way of polynomials. After analyzing this paper, it used to be transparent to me that this idea will be utilized to many impor­ tant computational difficulties. those impacts could be simply discerned within the current work.

Show description

Read Online or Download Multiplicative Complexity, Convolution, and the DFT PDF

Best extraction & processing books

Phase Diagrams and Ceramic Processes

Ceramic items are product of chosen and consolidated uncooked fabrics throughout the program of thermal and mechanical power. The complicated connec­ tions among thermodynamics, chemical equilibria, fabrication strategies, section improvement, and ceramic homes outline the undergraduate curriculum in Ceramic technology and Ceramic Engineering.

Biodegradable Poly(Lactic Acid): Synthesis, Modification, Processing and Applications

"Biodegradable Poly (Lactic Acid): Synthesis, amendment, Processing and functions" describes the guidance, amendment, processing, and the study and purposes of biodegradable poly (lactic acid), which belong to the biomedical and environment-friendly fabrics. hugely illustrated, the ebook introduces systematically the synthesis, actual and chemical ameliorations, and the newest advancements of study and purposes of poly (lactic acid) in biomedical fabrics.

Handbook of Materials Structures, Properties, Processing and Performance

This vast wisdom base offers a coherent description of complex subject matters in fabrics technological know-how and engineering with an interdisciplinary/multidisciplinary procedure. The ebook contains a historic account of serious advancements and the evolution of fabrics basics, supplying an immense standpoint for fabrics options, together with advances in processing, choice, characterization, and repair existence prediction.

Extra resources for Multiplicative Complexity, Convolution, and the DFT

Sample text

S. • k. A row vector ~ with J. entries in G that are nonzero only in positions l,is+i'is+2 •... • A exists such that if Y= flW = [Y1 112 1 . 11,1;1, then Yj to VpJ j = 1,2, ... ,k . t ",-1 . LY,{ LaiF~):ri' ,= 1 j =O ' , 0- 1 . 2. this combination can be zero only if Yj :E i =1,2, ... = 0 for a ji =0, Vi,i, since Yj Ii! VPi for 36 i = 1,2, ... ,". 5 the computation of PWA(x)y requires at least n mid steps. r)y) ~ k-s+i+t-n. Therefore k-s+l+l-n ~ II, yielding t~ 211-k-l+s. : I, we obtain t = Ils(MPM(P); G) = iis(MPM(P);G) = 211-" .

U' ,:0 (modP(u» are Cpa where a = lao 0 1 all_If Let t be the minimum number of multiplications needed to compute MPM(P), then A(x)y = Um where U is an nX t matrix with entries in G and m = [ml"'2 ... m/]T. For all nonzero row vectors WE Gil, wA(x) >Ie- 0, therefore rank U = n and U has n linearly independent columns. The columns of U may be pennuted if necessary such that the first n columns are linearly independent. A non-singular nXn matrix W exists such that WU=(f IU') and at least one of its rows is not in Vp since the rows of W span G".

R)y) ~ k-s+i+t-n. Therefore k-s+l+l-n ~ II, yielding t~ 211-k-l+s. : I, we obtain t = Ils(MPM(P); G) = iis(MPM(P);G) = 211-" . 3 applies is the evaluation of cyclic (or circular) convolutions. • N-I. 4) where all indexes are reduced to principaJ residues modulo N. 4) is equivalent to the polynomial product z(u) Ex(U)Y(U) (mod uN_I) N-I. N-I. N-I. i=O i=O ;=0 wherex(u)= LX,-u',y(u) = LY,-u',andz(u)::: LZiu'. The polynomial uN_I factors over Q into irreducible cyclotomic polynomials. This factorization is uN_l = II C/u), diN where C/u) is the d 'h cyclotomic polynomial.

Download PDF sample

Rated 4.54 of 5 – based on 16 votes