Computer Algebra, MAS-5731.

Course Contents.

Contents Computer Algebra MAS-5731 Fall 1999.

1. Introduction to Maple
2. Karatsuba method for multiplication of polynomials and integers
3. Euclidean algorithm
4. Computing in algebraic extensions

5. Resultants.
6. Factorization of polynomials
7. Nullstellensatz and the ideal membership problem
8. Groebner basis
9. Several applications of Groebner basis

The material treated in this course is found in the worksheets on the web. A text book is optional.

Relation between the fall1999 course and the fall2000 course

The contents of computer algebra in fall 2000 will be different from the content in spring 1998 or fall 1999, so that students who already took computer algebra can take computer algebra again in spring 2000 and it will still count as 3 credit hours.

The relation with the spring1998/fall1999 course is the following: Most of the algorithms studied in the spring2000 course (for an overview see the next section) use one or more of the following tools: algebraic extensions, resultants, gcd's, factoring polynomials, modular arithmetic etc.

Studying how these tools work internally was the contents of the spring1998/fall1999 course. In the fall2000 course we study algorithms that use these tools.

So for the fall2000 course it will be useful to have done the spring1998 or fall1999 course, but not essential. Students who have not taken the spring1998/fall1999 course can also take the fall2000 course. For these students the first two weeks of the fall2000 course will be different than for the others, because these first two weeks will need to be spent on learning Maple.

Contents Computer Algebra MAS-5731 in Fall 2000.

Elementary Integration.

See the help page ?int for some examples.

How can Maple compute such integrals? We will focus on the problem of elementary integration. A function will be called an elementary function if it can be built up with the following operations:

1) Rational functions in x with coefficients in the complex numbers C.

2) The functions exp and log.

3) Additions, multiplications, divisions, and compositions of functions.

4) algebraic extensions

So for example the functions (note that sin(x) and cos(x) can be expressed in terms of the exponential function):

f := x/(x^2+1)

g := sin(x)

h := exp(cos(x)+x^2)/(ln(x)^2+1)^2

are elementary functions. Now the problem of elementary integration is: Given an elementary function f, does there exist an elementary function F such that F'=f? If yes, how to find F?

Although this problem looks analytical, the solution to this problem is purely algebraic in nature.

Linear Differential Equations.

> (x^3+x)*diff(diff(y(x),x),x)-diff(y(x),x)+y(x)*x^3 = 0;

> dsolve(%);

How does Maple compute something like this?

It turns out that many ideas used in elementary integration can also be used in linear differential equations. We will study some of the methods. Again, the algorithms we will study will be algebraic in nature instead of analytical.