### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# 545 Class Note for CSE 565 at PSU

### View Full Document

## 21

## 0

## Popular in Course

## Popular in Department

This 24 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Pennsylvania State University taught by a professor in Fall. Since its upload, it has received 21 views.

## Similar to Course at Penn State

## Popular in Subject

## Reviews for 545 Class Note for CSE 565 at PSU

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

Algorithm Design and Analysis LECTURE 14 Divide and Conquer Fast Fourier Transform Adam Smith A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 9242008 Midterm Exam 1 Willard Building Room 76 Tuesday night September 30 815pm You may bring one 1 doublesided handwritten 85 X 11 sheet of notes on colored paper Hint use its preparation as a study aid 9242008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne FasT Fourier Transform ApplicaTions ApplicaTions OpTics acousTics quanTum physics TelecommunicaTions conTr39ol sysTems signal processing speech r39ecogniTion daTa compr39ession image processing DVD JPEG MP3 MRI CAT scan Numer39ical soluTions To Poisson39s equaTion The FFT is one of The Tr39uly gr39eaT compuTaTional developmenTs of This 20Th cenTur39y IT has changed The face of Science and engineering so much ThaT iT is noT an exagger39aTion To say ThaT life as we know iT would be very differenT wiThouT The FFT Charles van Loan Fas r Fourier Transform Brief His rory Gauss 1805 1866 Analyzed periodic moTion of asTeroid Ceres RungeKb nig 1924 Laid Theore rical groundwork DanielsonLanczos 1942 Efficient algori rhm CooleyTukey 1965 Moni roring nuclear Tests in Soviet Union and Tracking submarines Rediscovered and popularized FFT ImporTance noT fully realized un ril advent of digi ral compu rers Polynomials Coefficien r Represen ro rion Polynomial coefficien r r39epr39esen ro rion Ax a0 alx azx2 a1xquot391 Bx b0 blx b2x2 bn1xquot391 Add On arithmetic operations Ax Bx a0 b0a1b1x an1bn1xquot391 Evoluo re On using Hor39ner39s me rhod Ax a0 xa1xa2 xan2 xan1 Mul riply convolve Onz using brute force 2n 2 i Axx Bx 2 Ci xi where c1 E aij i0 i0 Polynomials Poin rValue Represen ra rion Fundamen ral Theorem of algebra Gauss PhD Thesis A degree n polynomial with complex coefficien rs has n complex r39ooTs Corollary A degree n1 polynomial Ax is uniquely specified by its evaluation at n disTincT values of x V Polynomials Poin rValue Represen ra rion Polynomial poin rvalue r39epr39esen ra rion Ax XosJ o Xn1ayn1 Bx X0 20 Xn1 zn 1 Add On arithmetic operations Ax Bx x0y0 20xn1yn1zn1 Mul l39iply On bu l39 need 2n1 poim s Ax x Bx x0y0 x 20x2n1y2n1x 22H Evalua re Onz using Lagrange39s for39mula H x x j A H x goyk 110 xj jaek Conver ring Be rween Two Polynomial Represen ro rions Tr39odeoff FosT evaluation or39 fast mul riplico rion We won t boTh RepreSenToTion MulTiply CoefficiemL Onz On PoinTvolue On Onz Goal Make all ops fast by efficien rly conver39Ting be rween Two r39epr39esen ro rions V a0a1an1 A meo xn1ayn1 lt coefficien r poin rvalue represen ra rion represen ra rion Conver ring Be rween Two Polynomial Represenfa rions Br39u re For39ce Coefficien r To poin rvalue Given a polynomial a0 a1 x an1 xn39l evaluate if at n distinct points x0 xn1 0n2 for ma rr39ixvec ror39 mul riply 2 11 1 3 0 1 x0 x0 x0 a0 2 71 1 yl 1 x1 x1 39 39 39 x1 a1 2 n l y2 1 x2 x2 39 x2 02 1 2 quot 1 a 3 yn l xn1 xn1 xn1 n l On for Gaussmn elimina rion 39 Vander39monde ma rr ix is inver rible iff xi dis rinc r Poin rvalue To coefficient Given n distinct points x0 xn1 and values yo yn1 find unique polynomial a0 a1 x an1xquot391 rha r has given values at given poin rs Coefficien r To Poin rValue Represen ra rion In rui rion Coefficien r To poin rvalue Given a polynomial a0 a1 x an1 xn39l evaluate if at n distinct points x0 xn1 Divide Br39eak polynomial up into even and odd power39s Ax a0 alx azx2 a3x3 a4x4 a5x5 a6x6 a7x7 Aevenx a0 azx a4x2 a6x3 Aodd x a1 a3x a5x2 a7x3 39 X Aevenxz X Aoddxz 39 A39x Aevenxz 39 X Aoddxz In rui rion Choose Two poin rs To be 1 A 1 Aeven1 1 Aodd1 A1 Aeven 1 Aodd1 Can evalua re polynomial of degree 5 n a r 2 points by evaluating Two polynomials of degree 5 n at 1 point Coefficien r To PointValue Represen ra rion In rui rion Coefficien r To poin rvalue Given a polynomial a0 a1 x an1 xn39l evaluate if at n distinct points x0 xn1 Divide Br39eak polynomial up into even and odd power39s Ax a0 alx azx2 a3x3 a4x4 a5x5 a6x6 a7x7 Aevenx a0 azx a4x2 a6x3 Aodd x a1 a3x a5x2 a7x3 39 X Aevenxz X Aoddxz 1 39 A39x Aevenxz 39 X Aoddxz In rui rion Choose four39 points To be 1 il 39i A 1 Aeven 1 1 Aodd1 A1 Aeven 1 1 Aodd 1 Can evalua re polynomial of degree 5 n A i A 1 i A 1 a r 4 poinTs by evaluaTing Two polynomials 39 even odd 39 f d lt l T 2 Ts 39 Aeven391 39 Aodd391 0 agree an a pom 39 Discre re Fourier Transform Coefficien r To poin rvalue Given a polynomial a0 a1 x an1 xn39l evaluate if at n distinct points x0 xn1 Key idea choose xk 00k where a is principal n rh roof of uni ry yo 1 1 1 1 1 a0 yl 1 m1 002 ms Du 1 a1 yz 1 D2 04 we c0201 1 a2 y3 1 13 16 19 om 1 a3 y H 1 mn l 0201 1 0301 1 um 1x114 art 1 l l Discre re Fourier Transform Fourier ma rrix Fn Roo rs of Uni ry Def An n rh roof of unify is a complex number x such Tha r x391 1 Fact The n rh roofs of unify are 000 001 on where 00 e 27 i quot pf mkn e 2niknn eni2k 12k 1 Fact The nh roofs of unify are v0 v1 vnZ39l where v e 4 i quot FGC I39 002 v and 002k vk Fos r Fourier Transform Goal Evoluo re a degree n1 polynomial Ax o0 on1 xquot391 of HS n rh roofs of unity 000 D1 Jon i Divide Br39eok polynomial up into even and odd powers 39 Aevenx 00 02X Cl4X2 an22 xn3912 39 Aodd X 01 03x G5X2 an21xn12 39 AevenX2 X Aoddxz Conquer Evoluo re degr39ee Aevenx and Aoddx of The nh roofs of uni l y v0 v1 vnZ39l Combine Aook Aevenvk 00k Aoddvk O s k lt n2 k k 2 kn2 2 MW AVvltkaoddvlt 0skltn2 V m 0 mk39H IZ Dllt FFT Algor39i rhm fft n aoa1 an1 if n 1 return a0 eoe1en21 lt FFTn2 aoa2a4an2 dod1dn21 lt FFTn2 a1a3a5an1 fork0ton2 1 wk lt e2nikn k yk lt ekmdk k Ykn2 ek w dk return yo Y1 I IYn l FFT Summary Theorem FFT algori rhm evalua res a degree n1 polynomial at each of The nfh roofs of why in On log n steps assumes n is a power of 2 Running Time T2n 2Tn On 2 Tn On log n On log n V 0 1 ao a1aan1 A 60 yo aquot yn1 lt coefficien r poin rvalue r39epr39esen ra rion r39epr39esen ra rion Recursion Tree perfec r shufer an r a2 r a4 r as a1 r a3 r a5 r a7 an 1 a4 a2 1 as a1 1 35 a3 1 a7 an 34 32 35 31 35 33 3 7 000 100 010 110 001 101 011 111 quotbi rreversedquot order Poin rValue To Coefficien r Represen ra rion Inverse DFT Goal Given The values yo yn1 of a degree n1 polynomial at The n poinTs 10 11 0039 find unique polynomial a0 a1 x an1xquot391fhaf has given values at given points 1 a0 1 1 1 1 1 yo a1 1 ml Dz 03 Du 1 yl a2 1 Dz 034 ms 00201 1 yz a3 1 13 16 039 130 y3 61H 1 Du 1 00201 1 mam 1 wn 1n 1 yH l i Inverse DFT Fourier ma rrix inverse Fn391 Inverse FFT Claim Inverse of Fourier matrix is given by following formula 1 1 1 1 1 1 00 1 0 2 0 3 w n l G l 1 03 2 w 4 00 6 w 2n 1 n n 1 0 3 0 6 0 9 w 3n 1 1 w n I w 2n 1 w 3n 1 w n 1n 1 Consequence To compute inverse FFT apply same algori rhm but use 00 1 e 392 i quot as principal n39rh roof of unify and divide by n Inverse FFT Proof of Correc rness Claim Fn and 6n are inverses Pf F G kk l Elwkjw jk39 l Ele k 1 ifkk39 summa rion lemma Summa rion lemma Le r 00 be a principal n rh roof of unify Then nil kj n if k E 0 mod n w i0 0 otherwise Pf If k is a mul riple of n Then 00quot 1 gt sums To n Each n roof of unify 00quot is a roof of x 1x 1 1 x x2 Xn1 if mk 1we have 100k00k200k 10 gt sumsToO Inverse FFT Algorithm ifftn aoa1an1 if n 1 return a0 eoe1en21 lt FFTn2 aoa2a4an2 dod1dn21 lt FFTn2 a1a3a5an1 fork0ton2 1 wk lt e Zacikn yk lt ek 0quot dk n Ykn2 ek 39 wk dk n return yo Y1 I r Yn l Inverse FFT Summary Theorem Inverse FFT algor39i rhm in rer39pola res a degree n1 polynomial given values at each of The n rh roofs of unify in On log n sTeps assumes n is a power of 2 On log n L r 0 1 a09ala 9an 1 A 60 7y0 quotquotwn yn l lt coefficien r 00quot log n poin rvalue r39epr39esen ra rion r39epr39esen ra rion Polynomial Mul riplica rion Theorem Con mul riply Two degr39ee n1 polynomials in On log n sfeps coefficien r r epr esen ro rion coefficien r r epr esen ro rion a0a1an1 C c c 0 19quot 2n 2 b0b1bn1 FFT On log n inver39Se FFT On log n AX0 Ax2n1 poin rvalue mulfiplica rion BX0Bx2n1 om CXoCx1Cx2n1 InTeger MulTiplicaTion InTeger mulTiplicaTion Given Two n biT inTegers a an1 a1ao and b bn1 b1b0compuTe Their producT c a x b ConvoluTion algoriThm n l Form Two polynomials I Nofe a AZ b Bxbob1xb2x2bn1xn 1 CompuTe Cx Ax x Bx EvaluaTe CZ a x b Running Time On log n complex ariThmeTic sTeps 2 Ax a0 a1x a2x an1x Theory Schb nhageSTrassen 1971 On log n log log n biT operaTions MarTin FUrer Penn STaTe 2007 On log n 239 9 biT operaTions PracTice GNU MulTiple Precision AriThmeTic Library 6MP proclaims To be llThe fasTesT bignum library on The planeTquot IT uses bruTe force KaraTsuba and FFT depending on The size of n

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.