Symbolic computation

2019/2020
Programme:
Computer Science and Mathematics, Second Cycle
Year:
1 ali 2 year
Semester:
first or second
Kind:
optional
Group:
B
ECTS:
6
Language:
slovenian, english
Course director:

Prof. Dr. Marko Petkovšek

Hours per week – 1. or 2. semester:
Lectures
2
Seminar
1
Tutorial
2
Lab
0
Content (Syllabus outline)
  1. Rewrite systems (reduction relations, Newman's lemma, completion) 2. Operations with polynomials (resultants and subresultants, modular arithmetic, Hensel lifting, polynomial factorization and decomposition) 3. Operations with ideals (monomial orders, Gröbner bases, solving systems of algebraic equations, applications in geometry and robotics) 4. Solving linear difference and differential equations (polynomial solutions, hypergeometric and hyperexponential solutions, summation and integration in closed form, automated proofs of identities)
Readings

David Cox, John Little, Donal O’Shea: Ideals, Varieties, and Algorithms. Third edition. Springer, New York , 2007. ISBN: 978-0-387-35650-1.
Joachim von zur Gathen, Jürgen Gerhard: Modern Computer Algebra. Third edition. Cambridge University Press, Cambridge, 2013. ISBN: 978-1-107-03903-2.
The Concrete Tetrahedron. Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Texts and Monographs in Symbolic Computation. Springer, Dunaj, 2011. ISBN: 978-3-7091-0444-6

Objectives and competences

Students acquire competency to use tools for automated solving of mathematical problems, important in applications, such as the problem of representation of algebraic structures, the problem of simplification of expressions, solving systems of algebraic equations, solving linear difference and differential equations, and summation and integration in closed form.

Intended learning outcomes

Knowledge and understanding: Complete rewrite systems. Operation of algorithms for polynomial factorization and decomposition. Algorithms for solving systems of algebraic equations. Algorithms for solving linear difference and differential equations. Algorithms for closed-form summation and integration and for proving identities.
Application: Solving problems in robotics, geometry, combinatorics, and analysis of complexity of algorithms.
Reflection: Relations among problems of representation, simplification, and computation.
Transferable skills: The ability to solve certain mathematical problems exactly by means of a computer.

Learning and teaching methods

Lectures, exercises, homeworks, consultations, projects.

Assessment

Homeworks or project
Written exam
Oral exam
grading: 5 (fail), 6-10 (pass) (according to the Statute of UL)

Lecturer's references

Marko Petkovšek:
PETKOVŠEK, Marko, WILF, Herbert S., ZEILBERGER, Doron. A=B. Wellesley (Massachusetts): A. K. Peters, cop. 1996. VII, 212 str. ISBN 1-56881-063-6. [COBISS-SI-ID 4085337]
BOUSQUET-MÉLOU, Mireille, PETKOVŠEK, Marko. Linear recurrences with constant coefficients: the multivariate case. Discrete Mathematics, ISSN 0012-365X. [Print ed.], 2000, vol. 225, no. 1-3, str. 51-75. [COBISS-SI-ID 10147929]
PETKOVŠEK, Marko, ZAKRAJŠEK, Helena. Solving linear recurrence equations with polynomial coefficients. V: SCHNEIDER, Carsten (ur.), BLÜMLEIN, Johannes (ur.). Computer algebra in quantum field theory : integration, summation and special functions, (Texts and monographs in symbolic computation, ISSN 0943-853X). Wien: Springer, cop. 2013, str. 259-284. [COBISS-SI-ID 16779353]