Assignments
Assignment 1
Assignment 2
Assignment 3
Assignment 4
Assignment 5
Assignment 6
Assignment 7
Project
1 Power Series
2 Groebner Bases
FGLM notes
Solutions
MATH 800 Computer Algebra, Fall 2023
Lectures
Tuesdays and Thursdays 9:30-10:30am in AQ 5029 and on Zoom
Zoom link
Meeting ID 889 3902 9408 Passcode 889399
Office Hours
Mondays 10-11am, on Zoom: Zoom link Meeting ID 892 5915 7448 Passcode 818446
Fridays 9-10am on Zoom: Zoom link Meeting ID 831 9280 0298 Passcode 966704
Course Information
Course Topics
- (4) Introduction to Maple and algebraic algorithms
- (4) Algorithms for exact Linear Algebra
- (3) The Fast Fourier Transform and fast algorithms
- (3) Algorithms for multivariate polynomials
- (4) Polynomial ideals and Groebner bases
- (3) Computing with algebraic numbers
- (3) Algorithms for sparse polynomial interpolation
Lecture Notes, Handouts and Lecture Recordings
I will post my lecture notes as a .pdf in the table below.
After each lecture I will upload a video recording of the lecture.
| Date | Topic | Handouts | Lecture Notes | Lecture Recording |
| September 7th | Maple tutorial | MapleNotes.mws MapleNotes.pdf |
Notes | Video (.mp4) |
| September 12th | Analysis of algorithms | Notes | Video (.mp4) | |
| September 14th | The Euclidean algorithm | Euclidean Algorithm | Notes | Video (.mp4) |
| September 19th | Polynomial interpolation | ClasscalAlgComplexites.pdf | Notes | Video (.mp4) |
| September 21st | Linear Algebra I | Notes | Video (.mp4) | |
| September 26st | Linear Algebra II | Fraction Free (.pdf) BareissEdmonds.pdf |
Notes | Lec6.mp4 |
| September 28th | Linear Algebra III | Bareiss/Edmonds/Lipson (.txt) Padic + Ratrecon (.pdf) RationalReconstruction (.txt) |
Notes | Lec7.mp4 |
| October 3rd | Linear Algebra IV | Berkowitz Maple code Linear Algebra basics in Maple |
Notes | Lec8.mp4 |
| October 5th | The Fast Fourier Transform I | FFT timings (.pdf) | Notes | Lec9.mp4 |
| October 12th | The Fast Fourier Transform II | FFT1 FFT2 FFT12noperm FFTmul |
Notes | Lec10.mp4 |
| October 17th | Fast Polynomial Division Fast Multipoint Evaluation |
Notes | Lec11.mp4 | |
| October 19th | Multivariate Polynomials | PolynomialDataStructures | Notes | Lec12.mp4 |
| October 24th | Multiplying Sparse Polynomials using Merging | UnivariatePolynomials (.pdf) UnivariatePolynomials (.txt) |
Notes | Lec13.mp4 |
| October 26th | Multiplying Sparse Polynomials using Heaps | Heaps in Maple | Notes | Lec14.mp4 |
| October 31st | Ideals in Polynomial Rings | Notes | Lec15.mp4 | |
| November 2nd | Division and Monomial Ideals | Division in Maple The Division Algorithm |
Notes | Lec16.mp4 |
| November 4th | The Hilbert Basis Theorem and Groebner Bases | Notes | Lec17.mp4 | |
| November 9th | Computing Groebner bases and applications | GroebnerBasis.pdf | Notes | Lec18.mp4 |
| November 14th | Algebraic Numbers and Minimal Polynomials | AlgebraicNumbers.pdf | Notes | Lec19.mp4 |
| November 16th | Algebraic Number Fields and Primitive Elements | PrimitiveElements.pdf | Notes | Lec20.mp4 |
| November 21st | Factoring Polynomials over Algebraic Number Fields | NormFactors.pdf Trager.pdf |
Notes | Lec21.mp4 |
| November 23rd | The Black-Box Representation for Polynomials | Notes | Lec22.mp4 | |
| November 28th | Zippel's Sparse Polynomial Interpolation | Notes | Lec23.mp4 | |
| November 30th | Ben-Or/Tiwari Sparse Polynomial Interpolation | BenOrTiwari.pdf | Notes | Lec24.mp4 |
Maple
We will use Maple extensively for calculations and programming in this course. If you do not have access to Maple you may buy the student version of Maple from Maplesoft. I have obtained a discounted price of for $99 + taxes (discounted from $149 + taxes). Got to Maplesoft, select Student and enter the product code M800-SFU-M2023 to get the discount.
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.
MapleNotes.mws MapleNotes.pdf