Star plus serial song. Computer Algebra is the discipline that studies the algorithms for Symbolic Computation. In Symbolic Computation, one computes with symbols, rather than with numbers. Computer Algebra, Spring 2018, course documents Weeks 1 and 2. Note: If your web-browser does not start Maple when clicking on these Maple files, then it may be easier to download all files for weeks 1 and 2 in this zip file, then unpack it on your computer. This creates a folder weeks_1_2 with the files in it (the file 'files.txt' indicates in which order we're using them). • We will look at this in class. • We will look at this in class. If there's enough time we'll also look at the following worksheets:,. ![]() Study the remaining worksheets for next time. • Another and some (in the form of a pdf-file) with. • Programming assignment: (this contains homework for week 2. Note: you may choose to do the assignment in this worksheet, or program the Karatsuba method instead). • A (called ) based on the 'divide and conquer' approach. • Multiplying polynomials with the 'divide and conquer' approach: the. Weeks 3 - 6 • Modular algorithms and the. • Study this program (don't worry about the complicated LinearAlgebra:-Modular commands, more important is to try to understand the overall setup; a bound B, a product m that should be at least 2B+1, and the chrem and mods(d,m) at the end). Read the worksheet. • Study the algorithms in and do the assignment about sqrfree. The worksheet explains how the following algorithms work: • The Extended Euclidean Algorithm (only implemented for the case of positive integers, but it works in the same way for polynomials). • How to do divisions modulo an integer p. Note: one can use a similar algorithm to do divisions modulo a polynomial. • How to compute quotients and remainders. • Euclidean Algorithm for polynomials. • Chinese Remainder Theorem (only implemented for two integer moduli m1,m2. Of course a very similar algorithm would work when m1,m2 are polynomials). For additional information see the worksheet on Factoring polynomials in Q[x] below. • Project: Implement factorization in Q[x,y] in the same way as factorization in Q[x] is done in the worksheet. You may use Maple's 'sqrfree' for squarefree factorization, and may only use Maple's 'factor' for factoring univariate polynomials. Replace 'icontent' by 'content', replace p-adic Hensel lifting by x-adic Hensel liften, replace the bound on the length of the coefficients by a bound on the degree of the coefficients, etc. Turn the Hensel lift algorithm from the worksheet on p-adic numbers into a Hensel lift algorithm for the x-adic case. Weeks 7 - 10. • • (this does not generalize to higher dimension, for that, we need the paper of Lenstra, Lenstra, and Lovasz). • Assignment m:= 13^30; f1:= x^2+634*x+37; Find a polynomial g in Z[x] such that: • degree(g). Content • (2) Algorithms for long integer multiplication and GCD computation. • (3) Unique factorization, Euclidean rings and polynomial rings. • (1) Pseudo division and polynomial GCD computation. • (2) The Chinese remainder theorem and polynomial interpolation. • (2) The Fast Fourier Transform and fast multiplication. • (2) A modular algorithm for polynomial GCD computation. • (3) The P-adic Newton iteration, Hensel's lemma and Hensel lifting. • (2) Polynomial factorization over finite fields and the integers. • (2) Resultants and algorithms for rational function integration. • (1) Representation and differentiation of formulae on a computer. • (4) The Risch decision procedure for elementary function integrals. Maple We will use Maple extensively for calculations and programming in this course. Much of the course is about how Maple works. SFU has a site license for Maple. Maple is installed on the PCs and MACs in the assignment lab, the CECM lab, university open labs and the library. Maple is available from Maplesoft for a very good price at The following Maple worksheet [ in Maple worksheet format (.mws) and Adobe PDF format (.pdf) ] contains notes for how to use Maple. Please read through this even if you have used Maple before.
0 Comments
Leave a Reply. |