### Create a StudySoup account

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

Already have a StudySoup account? Login here

# AppliedSymbolicComputation CS300

Drexel

GPA 3.88

### View Full Document

## 48

## 0

## Popular in Course

## Popular in ComputerScienence

This 50 page Class Notes was uploaded by Vito Kilback on Wednesday September 23, 2015. The Class Notes belongs to CS300 at Drexel University taught by Staff in Fall. Since its upload, it has received 48 views. For similar materials see /class/212471/cs300-drexel-university in ComputerScienence at Drexel University.

## Reviews for AppliedSymbolicComputation

### 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: 09/23/15

ngax1 y ami Raysmi X Cab H Jik5 JFQQJ i Pkibk P 2 Pp PFZX1Squot39 REAKS Va FDA Vac Jr V H V 1539 V 9 PDQ P u 3c u 4 6 H431 u Et bku1quotkQ 39 MQUT 5L uz t D R I If 83 ILq p 1 AC Wquot 52L C1 1 kL 3 Wu P Wat 41 439 l 31l31L M h ELM 1 MW quot Pkm Wad i WJW J 3 am 1 3 rfg er 9m g t quot w wi xm x f c a V L L1 F3 MM 1 a I 71 L 1quot 1 P FRquot 762 P 9 7 3 l FMW C 7 J rVV MAM i Cuecx fk i kl Zk em ECKL Pk i RIP LECX 1W3 90012 lt 35 g g L quot 1L g ik PK Es 3 339 P ikW IWE WK EM a L P 39k Plk quot P UV 3 Wm W39Cd f CW Wm Q m 4 PQVMZ fig PQ39WM P L 3r QVH quot MM Lx mam Mum vww me F PM WV u 1 r V L Q sf PQ Ar P Q PQ a 9394 PQ L km NM 0quot x PKG Q l k7 P Q CA P l L 1 Q39UVrIPLYL Ext UA TEwa mL PWLRN m AC 730 7 PALM Kl1vm hv IA 1k h JVMux 3W l A t z 7 L1 L13 Lu Kvx1MH 3 g Wl u A PM thl 41 L magi 00 t a 0 5 a f a o 2 U a 02 A H Tm vaev I R r r C A NF 1AM c Vthcp d M A m wtk Cr FM C gt v37 Cu WT u 55 may War 2 rpiw fu yIWt CL H UZ ru quot0 Mltxgtlpsrr 0 n f ucn1AVHLTr n T92 TCL r mC i urCr h l TuZ H WCAFlTJ H k L 3 DEM394 Q PC P LI HEP Ccme U363 Ln QA 501 am own7k 9 9 33 N L U39 39 QULL C 7 8 Q1 UL QMK IL I U Q t l ii wv LEVI QM M prkm K v f g u Q WAG QMKM WAquot Qku Qkq IO 39 I 16 i G K Quk I4 Applied Symbolic Computation cs 300 Modular Arithmetic Jeremy R Johnson Introduction Objective To become familiar with modular arithmetic and some key algorithmic constructions that are important for computer algebra algorithms Modular Arithmetic Modular inverses and the extended Euclidean algorithm Fermat s theorem Euler s Identity Chinese Remainder Theorem References Rivest Shamir Adelman Modular Arithmetic Zn Definition a E b mod n ltgt n b a Alternatively a qn b Properties equivalence relation a a a mod n Reflexive a a b mod n gt b a a mod n Symmetric a a b mod n and b a c mod n gt a E c mod n Transitive Definition An equivalence class mod n axanmodnaqnqeZ Modular Arithmetic Zn It is possible to perform arithmetic with equivalence classes mod n a b ab a b ab In order for this to make sense you must get the same answer equivalence class independent of the choice of a and b In other words if you replace a and b by numbers equivalent to a or b mod n you end of with the sumproduct being in the same equivalence class a1 a2 mod n and b1 5 b2 mod n gt a1 b1 5 a2 b2mod n a1 b1 5 a2 b2 mod n aQ1nbQZnabQ1Q2n a 11quot b qzn a b bq1 aq2 11 q2n Representation of Zn The equivalence classes a mod n are typically represented by the representatives a Positive Representation Choose the smallest positive integer in the class a then the representation is 01n 1 Symmetric Representation Choose the integer with the smallest absolute value in the class a The representation is Ln1l2J Ln2J When n is even choose the positive representative with absolute value nl2 EG 26 21o123 25 21o12 Modular Inverses Definition x is the inverse of a mod n if ax a 1 mod n The equation ax 51 mod n has a solution iff gcdan 1 By the Extended Euclidean Algorithm there exist x and y such that ax ny gcdan When gcdan 1 we get ax ny 1 Taking this equation mod n we see that ax a 1 mod n By taking the equation mod n we mean applying the mod n homomorphism m Z Zm which maps the integer a to the equivalence class a This mapping preserves sums and products E mab ma mb mab ma ltlgtmb Fermat s Theorem Theorem If a at 0 e Zp then a 391 E 1 mod p More generally if a e Zp then aP E a mod p Proof Assume that a 7 0 e Zp Then a 2a p1a p1 ap1 Also since ai a aj mod p gt i sj mod p the numbers a 2a p1a are distinct elements of Zp Therefore they are equal to 12p1 and their product is equal to p1 mod p This implies that p1 aP391E p1 mod p gt a 391 E 1 mod p Euler phi function Definition phin a 0 lt a lt n and gcdan 1 Properties pp p1 for prime p ltgtpquote p1pquote1 q mn p m ltpn for gcdmn 1 ltPP0l P3910391 Examples p15 p3 p5 24 8 12478111314 qgt9 313quot21 23 6 124578 Euler s Identity The number of elements in Zn that have multiplicative inverses is equal to phin Theorem Let Zn be the elements of Zn with inverses called units If a e Zn then am a 1 mod n Proof The same proof presented for Fermat s theorem can be used to prove this theorem Chinese Remainder Theorem Theorem If gcdmn 1 then given a and b there exist an integer solution to the system x a a mod m and x b mod n Proof Consider the map x gt x mod m x mod n This map is a 11 map from Zmn to Zm x Zn since if x and y map to the same pair then x a y mod m and x a y mod n Since gcdmn 1 this implies that x a y mod mn Since there are mn elements in both Zmn and Zm x Zn the map is also onto This means that for every pair ab we can find the desired x Alternative Interpretation of CRT Let Zm x Zn denote the set of pairs ab where a e Zm and b 6 Zn We can perform arithmetic on Zm x Zn by performing componentwise modular arithmetic asb csd absCd abcgd acbd Theorem Zmn z Zm x Zn E There is a 11 mapping from Zmn onto Zm x Zn that preserves arithmetic ac mod m bd mod n a mod m b mod nc mod m d mod n ac mod m bd mod n a mod m b mod nc mod m d mod n The CRT implies that the map is onto E for every pair ab there is an integer x such that x mod m x mod n ab 11 Constructive Chinese Remainder Theorem Theorem If gcdmn 1 then there exist em and en orthogonal idempotents em 1 mod m em 0 mod n ens 0 mod m en a 1 mod n It follows that aem b en a a mod m and a b mod n Proof Since gcdmn 1 by the Extended Euclidean Algorithm there exist x and y with mx ny 1 Set em ny and en mx Applied Symbolic Computation cs 300 The Fast Fourier Transform FFT and Convolution Jeremy R Johnson Applied Symbolic Computation Introduction Objective To derive the fast Fourier transform FFT as a factorization of the Vandermonde matrix To introduce the convolution operator and relate it to polynomial and matrix algebra To use the Chinese Remainder Theorem to prove the convolution theorem and rederive the FFT Vandermonde Matrices Polynomial multiplication using interpolation Factoring the Vandermonde matrix using evenodd symmetry Convolution Theorem Deriving the FFT using the Chinese Remainder Theorem References Lipson Tolimieri Cormen et al Applied Symbolic Computation 2 Horner s Method Let Ax a3x3 azx2 a1x a0 A asa a20 o a1 0 a0 In general let Ax Z a xi i0 A0 am Ai Ai1 0 ami Am Aoc The number of operations is 2m m additions m multiplications Applied Symbolic Computation Evaluation Utilizing Symmetry The cost of evaluation at two points can be reduced if one is the negative of the other Let Ax A1x2x Aox2 where the coefficients of A1x are the odd coefficients of Ax and the coefficients of Aox are the even coefficients of Ax Since a2 a2 A0a 2 A0a 2 and A1oc 2 A1oc 2 Aa Ao0t 2 0 Add 2 A Ao 2 a A101 2 Example Ax asx5 a4x4 a3x3 azx2 a1x a0 A1x2x A0x2 A1x asx2 a3x a1 A0x a4x2 azx a0 Applied Symbolic Computation 4 Evaluation Utilizing Symmetry To evaluate Ax with degA m at ia requires 4m operations using Horner s method fora and a 4m2 3 2m 3 approx half operations using i symmetry To evaluate a polynomial of degree N1 at N2m points 2N2 oN2 N2 oN2 Applied Symbolic Computation Factoring the Vandermonde Matrix Recall 1 n 1 050 a0 1 n 1 051 051 Va0an Applied Symbolic Computation Factoring the Vandermonde Matrix If n 2m and a1 an a1 am X1 ocm then the Vandermonde matrix can be factored using the evenodd symmetry discussed previously 12 3 1ala2a3 l 12 3 1 a1a2 a3 l 2 1010100010500100 2 0 0 01001 00001 10 1000a0001a2010 010 10003001 2000 Applied Symbolic Computation i OOO Factoring the Vandermonde Matrix The previous factorization can be concisely described by the following formula Va1ama1 am 2m 1 1 Fr 1 1 szdiaga1am Vm Wayworm Lim a permutation that groups even and odd coeffs Applied Symbolic Computation Discrete Fourier Transform If a1 an are equal to the nth roots of unity the Vandermonde matrix becomes the DFT matrix Let xi oi where 0 is a primitive nth root of unity 1 1 1 1 01 011 1 Va19nanFn H H H H 1 a quotW D Applied Symbolic Computation Discrete Fourier Transform 1 1 F21 1 1 1 1 1 1 1 1 2 1 i 1 i F321 0 0 F4 1 2 1 1 1 1 a a 1 z 1 z Applied Symbolic Computation 10 Properties of Roots of Unity Lemma 03391 11 Lemma Let n 2m and a be a primitive nth root of unity Then 032 is a primitive mth root of unity Lemma Let n 2m and o be a primitive nth root of unity Then 0339 1 and comk coquot Therefore F239 is a Vandermonde matrix where half the points are negatives of the other half Thus we can utilize the previous factorization to compute the DFT Moreover if n2k this property can be used recursively Applied Symbolic Computation 11 Fast Fourier Transform Assume that n 2m then Fm F2 ImXIm WmXIZ ML Wm diag1a1a 1 Let Tn be the computing time of the FFT and assume that n2quot then Tn 2Tnl2 n Tn nlogn Applied Symbolic Computation 12 Example FFT Factorization 391111 11 1 1 F421 11 1 1 l 11 3910 0100011 010101001 1 10 1000100 010 100010 F2 12T12 F2L 4 T2 2 0 W2 d1ag111 1 1 t1 KOO OO OOOH OHOO OOHO 1 000 Applied Symbolic Computation FFT Input N 2quot a aoa1an1 aoa1x an1xquot1 Output A A0A1An1 with Ak a03k Procedure FFTNaoaA if N 1 then A0 a0 else n N2 b aoa2a2n1 c a1a3a2n1 FFTnb 023 FFTnc 020 for k from 0 to n1 do Ak Bk a X Ck Ank Bk 39 wk x Ck end do end if End Applied Symbolic Computation 14 Polynomial Multiplication using Interpolation Compute Cx AxBx where degreeAx m and degreeBx n DegreeCx mn and Cx is uniquely determined by its value at mn1 distinct points Evaluation Compute Aoni and Boci for distinct ai i0mn Pointwise Product Compute Coui AaiBoci for i0mn Interpolation Compute the coefficients of Cx cnxmn c1x c0 from the points Cai AociBai for i0mn Applied Symbolic Computation 15 Inverse DFT 1 1 1 1 1 11 1 Fflt1nFl1n 1 ZD39n l n 1n 1 Proof The ij element of n 1 n 1 n 1 ik kj ik kj ki j FnFnZaJ w 20 0 20 k0 k0 k0 If i j then the sum is equal to n and if i j then the sum is 0 since xquot1 x1x 391 x 1 Applied Symbolic Computation 16 Linear Convolution Definition Let u and v be two vectors of size m and n respectively The linear convolution of u and v is equal to MVk ZujijC 0mn ijk Example 0 V0 110 V0 0 V1 1 V0 1 V1 0V2u1V1u2V0 U2 V2 1 V2 2 V1 U2 V2 Applied Symbolic Computation 17 Linear Convolution ancl Polynomial Multiplication Linear convolution is the same as polynomial multiplication Let ux umxm u1x u0 and vx vnxn v1x v0 Then uxvx uvmnxmn uv1 x uv0 Example uXVX uzxz u1X uoV2X2 V1X V0 U2V2X4 U1V2 u2V1X3 0V2 u1V1 u2V0X2 0V1 u1V0X roo Applied Symbolic Computation Cyclic Convolution Definition Let u and v be two vectors of size n respectively The npoint cyclic convolution of u and v is equal to MVk Eu VJJC 0n ijEkmodn Example uo v0 u0v0u1v2u2v1 u1 v1 0V1U1V0U2V2 u2 v2 uov2u1vlu2vo Applied Symbolic Computation 19 Cyclic Convolution ancl Polynomial Multiplication Npoint cyclic convolution is the same as polynomial multiplication modulo xquot1 Let ux umxm u1x u0 and vx vnxn v1x v0 Then uxvx mod xquot1 uvn1x 391 uv1 x uv0 Example uXVX uzxz u1X uoV2X2 V1X V0 U2V2X4 U1V2 u2V1X3 0V2 u1V1 u2V0X2 0V1 u1V0X roo U2V2X U1V2 u2V1 0V2 u1V1 0V2X2 0V1 u1V0X roo 0V2 u1V1 u2V0X2 0V1 u1V0 u2V2X rooquot39 u1V2 u2V1 Applied Symbolic Computation 20 Circulant Matrices Definition A circulant matrix Cuoun is obtained by cyclically rotating the vector uoun Multiplication by a circulant matrix corresponds to cyclic convolution The ij element of Cuoun is equal to uij mod n Example L10 L12 L11 v0 uovoulv2u2vl uo v0 L11 L10 2 v1 0V1U1V0U2V2 ul v1 L12 L11 L10 v2 uov2ulvlu2vo ug v2 Applied Symbolic Computation 21 Shift Matrices Definition The npoint shift matrix Sn is the permutation matrix that cyclically shifts the elements of a vector The ij element of Sn is equal to 1 when ij 51 mod n Example 0 O 1 V0 V2 1 O 0 V1 v0 0 1 0 v2 V1 Applied Symbolic Computation 22 Generating Circulant Matrices A circulant matrix is equal to a linear combination of powers of the shift matrix 0000011101420 MOI12111 0000u2 111011220 110 OU1 2 1111le 0 0 110 0 U10 U2 0 O 100 001 010 u0010u1100u2001 001 010 100 1 2 ZUOI3U1S3U2S3 Applied Symbolic Computation 23 Convolution Theorem Theorem Fnu v Fnu o Fnv u v Fn1Fu Fv This theorem provides an Onogn algorithm for performing cyclic convolution provided Fn is computed with the FFT We will prove this theorem two different ways Show that Fn diagonalizes a circulant matrix Use the Chinese remainder theorem Applied Symbolic Computation 24 Diagonalizing the Shift Matrix Theorem Fn Sn Wn Fn where Wn diag1oa 0 111001111 1w1w2100w1w21 1w2w1010w2w11 100111 1 12 0w01wa OOwZIwal Applied Symbolic Computation 25 Diagonalizing a Circulant Matrix Theorem Fn Cnu diagFnU Fn 1 1 1 uo U2 ul 1 1 1 1 2 2 1 1602 01111 uo 11213101 a2 1 a a U2 L11 L10 1 a a 71 2 71 F3C3F3 F3ltUOI3U1S3U2S3F3 qu3I3Fu1F3S3Fglu2F3SF 2 u013u1W3u2W3 uou1u2 0 0 1 2 0 00 10 U2 0 2 1 0 0 uoa u1a U2 Applied Symbolic Computation 26 First Proof of the Convolution Theorem Theorem Fnu v Fnu o Fnv u V Fn391Fnu Fnv Proof Fnu V FnCu V diaQFnU an Fnu nV Applied Symbolic Computation 27 Polynomial Version of the Chinese Remainder Theorem Theorem Let fx and gx be polynomials in Fx coefficients in a field Assume that gcdfxgx 1 For any A1x and A2x there exist a polynomial Ax with Ax a A1x mod fx and Ax E A2x mod gx Theorem Fxlfxgx z Fxlfxx Fxlgx lE There is a 11 mapping from Fxlfxgx onto Fxlfx x Fxlgx that preserves arithmetic Ax gt Ax mod fx Ax mod gx Applied Symbolic Computation 28 Multifactor CRT o The CRT can be generalized to the case when we have n pairwise relatively prime polynomials If f1xfnx are pairwise relatively prime ie gcdfixfjx 1 for i at then given A1xAnx there exists a polynomial Ax such that A a Aix mod fix Moreover there exist a system of orthogonal idempotents E1xEnx such that Eix a 1 mod fix and Eix E 0 mod fjx for i j Ax A1xE1x AnxEnx FxlA1xAnx z FxlA1x x x FxlAnx Applied Symbolic Computation 29 CRT and the Convolution Theorem Since x 1 x1xmxoaquot391 and gcdxoai xoai 1 for i j Cxlxquot1 z Cxlx1 x x Cxlxoan391 Let ux and vx be elements of Cxlxn1 The map Cxlxn1 onto Cxlx1 x x Cxlxoan391 is Fn ux gets mapped to u1uco 391 Multiplication in Cxlxn1 is cyclic convolution Multiplication in Cxlx1 x x Cxlxoan391 is a pointwise product First multiplying ux and vx in Cxlxn1 and then applying Fn is the same as applying Fn to ux and Fn to vx and then multiplying in Cxlx1 x x Cxlxmn391 Therefore Fnu v Fnu o Fnv Applied Symbolic Computation 30 CRT and the FFT Factor Fn by projecting onto Cxlx1 x x Cxlxoan391 in stages Let n 2m then xquot1 xm1xm1 and gcdxm1xquot1 1 Cxlxn1 z Cxlxm1 x Cxlxm1 This mapping is F2 8 Im Cxlxm1 z Cxlx1 x Cxlxoaz x x Cxlxoa2m391 This mapping is Fm Cxlxm1 z Cxlxoa x x Cxlxmzm391 This mapping is WmFm Fm EB WmFmF2 lm Ax A1A02A032m391AoaAoaquot391 Applied Symbolic Computation 31 CRT and the FFT Fm GB WmFmF2 69 lm Ax A1A02A02m391AoaA0quot391 FZm Ax gt A1 AwAw2 Awquot39quot Therefore F2mLimvz Fszm Wmhv2 Im FimF2mF2 1mXImWmX12 FmLm Applied Symbolic Computation 32

### 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."

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "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.