Topics in Computer Algebra

About me Research Publications Students Teaching Talks Links

Assignments

  Assignment 1 (.pdf)
  Assignment 2 (.pdf)
  Assignment 3 (.pdf)
  Assignment 4 (.pdf)
  Assignment 5 (.pdf)

Topics in Computer Algebra, Fall 2021

Lectures: Thurdays 9:30am to 11:30am and Fridays 10:30am to 12:30pm

Room: AQ 5026

Office Hours: Tuesdays 3:00pm to 5:00pm

Zoom link Meeting ID: 643 2518 1923 Password: 774226

Content

For a list of topics and a lecture schedule and course assessement see course information sheet

Handouts and Notes

Date	Handouts	Lecture Notes	Lecture Recordings
September 9	FFT1.pdf FFTmul.pdf FFT2.pdf FFTnoperm.pdf FFT12.pdf	FFTreview.pdf FFT1code.pdf FFT1code.pdf FFT2algorithm.pdf FFT12perms.pdf FFTlintrans.pdf	Lec1A.mp4 Lec1B.mp4
September 10		FastDivision.pdf FastEval.pdf	Lec2A.mp4 Lec2B.mp4
September 16	UnipolyMerge.pdf UnipolyMerge.mw Polynomial Data Structures	AddMerge.pdf MonomialOrderings.pdf	Lec3A.mp4 Lec3B.mp4
September 17	Heaps in Maple.pdf	HeapsNotes.pdf PolyMultNotes.pdf	Lec4A.mp4 Lec4B.mp4
September 23	GEalgos.pdf FracFreeGaussElimExample.pdf	Determinants.pdf FractionFree.pdf BareissEdmondsCost.pdf	Lec5AB.mp4
September 24	PadicSolve.pdf PadicSolve.mw EEA.pdf EEA.txt	Padic Solve.pdf Rational Reconstruction.pdf	Lec6A.mp4 Lec6B.mp4
September 30	No Lecture – National Reconciliation Day
October 1	Berkowitz.pdf	AdjugateMatrix.pdf BerkowitzAlgorithm.pdf	Lec7AB.mp4
October 7	Hu and Monagan's GCD Algorithm
October 8	ModGcdZx.pdf BrownsCost.pdf	Lec8A.pdf Lec8B.pdf	Lec8A.mp4 Lec8B.mp4
October 14	Zippel's Sparse Interpolation Algorithm.	Lec9A.pdf Lec9B.pdf	Lec9AB.mp4
October 15	BenOrTiwari.pdf BenOrTiwari.mw	Lec10A.pdf Lec10B.pdf Lec10C.pdf	Lec10A.mp4 Lec10B.mp4
October 21	Varieties in k^n and Ideals in k[x1,...,xn].		Lec11AB.mp4
October 22	DivisionAlgorithm.pdf NormalForm.pdf	Lec11A.pdf Lec11B.pdf	Lec12A.mp4 Lec12B.mp4
October 28	The Hilbert basis theorem and Groebner bases.		Lec13A.mp4 Lec13B.mp4 Lec13B.mp4
October 29	GroebnerBasis.pdf GroebnerBasis.mw		Lec14A.mp4 Lec14B.mp4

Maple

We will use Maple for programming and calculations. The following Maple worksheet has some notes for programming in Maple: MapleNotes.mw and MapleNotes.pdf

References

Algorithms for Computer Algebra by Geddes, Czapor and Labahn
Modern Computer Algebra by von zur Gathen and Gerhard
Ideals, Varieties and Algorithmsby Cox, Little and O'Shea

Papers

Lazy and Forgetful Polynomial Arithmetic and Applications by Vrbik and Monagan, Springer LNCS 5743: 226–239, 2009.
Sparse Polynomial Arithmetic by Stephen Johnson, ACM SIGSAM 8(3):63–71, 1974.
Analysis of Algorithms, A Case Study: Determinants of Matrices with Polynomial Entries by Gentleman and Johnson, TOMS 2(3): 232–241, 1976.
Maximal Quotient Rational Reconstruction by M. Monagan, Proc. ISSAC '04, pp. 243–249, 2004.
On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors, W.S. Brown, J. ACM 18(4):478–504, 1971.
Probabilistic algorithms for sparse polynomials. by R. Zippel, Springer LNCS 72:216–226, 1979.
A Deterministic Algorithm for Interpolating Sparse Multivariate Polynomials by M. Ben-Or and P. Tiwari, Proc. STOC '88, pp. 301–309, 1988.