Symbolic Computing

LT20, 4:00-6:00pm
Wed, 8 April 2003

Revision class

Part I, Mathematica

1. Basic Syntax

We expect a mastery of the basic syntax of Mathematica. In particular, we want to be familiar with many of the special symbols and notations in Mathematica, such as:

=	Set (assignment)
:=	delayed Set (delayed assignment)
->	replacement rule
/.	apply (of a rule)
//.	apply repeated
@@	the Apply[  ] function
/@	Map[ ] function
//	postfix (of function)
@	prefix (of function)
~f~	infix (of function)
f[#]&	pure function
x_	pattern (anything named x)
x__	one or more 
x___	zero or more
{  }	List
(  )	grouping
[  ]	function argument
[[  ]]	indexing
(*  *)	comments
%	previous output
==	compare for equal
===	compare for identical (stronger)
,	comma separate arguments 
;	group expressions as logically one

etc.

2. Principles of Mathematica

Mathematica follows few well-defined principles, that we try to summarize here:

(a)  Do exact calculation unless input is approximate.  E.g.,

{Sqrt[3],  Sqrt[3.0]}

(b)  Apply built-in and user-defined rules until results no longer change (thus recursive).  Recognize the rules (or definitions) according to pattern matching.

(c) Uniform internal data and program format (expressions) :
                h[(Subscript[a, 1]), (Subscript[a, 2]), ..., (Subscript[a, n])]
where h is the head, (Subscript[a, i]) is its ith argument.     
A collection of list manipulation functions (such as Take[ ], Drop[ ], Union[ ], Join[ ])
work on any expression, as well as special important type List {  }.

For example,  {a,b,c} (same as List[a,b,c]) can be used as array storing data, or matrix {{a,b},{c,d}}.  But the program 
f[x_] := Module[{}, ...] is also in the same format h[a,b,c].

3. Programming Style

We expect students can program in several different programing styles:

(A) Procedural programing style using explicit loop control such as Do[  ], While[  ], For[  ], If[  ], Return[  ],  Goto[ ], etc.

A procedural based program normally is enclosed in a Module[ ].  E.g.:

myprog[arg1_,  arg2_]  :=  
      Module[{i, local1,  
          local2,   ... }, 
...;
For[i  =  0,  
            i  <  10,  ++i, 
Print[  ... ]; 
do that;
];
returnvalue
]

Note that you cannot reassign values to argument variables.

(B) Rule-base programming defines a set of transformation rules using patterns.  The same name can be given several distinct definitions, the use of which is decided by pattern matching.   In a rule-base programming, the left-hand side of the delayed assignment (the pattern) can be complicated.

Here is an example of rule base programming for counting the number of arguments:

argn[]  :=  0;
argn[x_]  :=  1;
argn[x_,  y__]  :=  1  +  argn[y]

(C)  Functional programing style avoids side effect (such as looping).  Functional programing uses Map[ ], Apply[ ], Nest[ ], Fold[ ], and pure functions to get the effect of looping.

The question of when to use a pure function is dictated by syntax.  Suppose we need to square each element in a list. With Map, we must use pure function:

Map[#^2 &,  {a, b, c}]

or we can define a square function first.  Note that we use square without argument.

square[x_] :=  x^2;
Map[square,  {a, b, c}]

Equivalently:

Map[square[#] &,  {a, b, c}]

What to review?

(1) One can do the lab problems again (independently, in an examination setting)
(2) Review the tutorial problems
(3) Reading
(4) Do the following problems

Mathematica Exercise Problems:

(1) Tell us exactly what is Mathematica's response with the following inputs (assuming each one is independent of others):  [For correct answer, you should do a Clear[variable] for these expressions that produce side affect, such as assigning values to variables]

(a + b*c)[[2, 2]]

x = 1;  y = 2 + x;  x = 2; y

f  @@  {a, b}

Map[f, g[a, b]]

f[f[f[x]]]  //.  f[x]  -> x

Fold[f, x, {a, b, c}]

{1, 2, 3}^3

f[x] := x^2; f[y_] = y^3;  f[x] + f[y]

Sqrt[#] & [4]

MatchQ[f[a^x],  f[x^x_]]

Head[I]

a + b*c  /.  Plus  ->  List

a*b*c  //.  x_* y_  ->  x + y

Part[Sin[x*y + z], 1, 2]

List  @@  f[a, b, c]

{x -> #1} &  /@  {a, b, c}

MatchQ[f[a, b, c], f[x_]]

Drop[{a, b, c}^3, 1]

Head[Real]

{a, {b, c}} = {1, {2, 3}};  b

{a (a),  a {a},  a[a]}

#^2 &[2]

a = Sin;  a[Pi]

{1, 2, 3}  // f

f  @@  {1, 2, 3}

FullForm[x^3 + u*y]

x  //.  x ->  x

Log  /@  {E,  E^2,  1}

Sum[1, {5}]

ReplacePart[{{1, 0}, {0, 1}}, a, {2, 2}]

Map[#^3 &, x + y + 2]

Function[var, var^2 + 1][2]

Apply[Times, {1, 2, 3, 4}]

Select[{1, a, x^2, 3, 5, 1 + x, 7},  # < 4 &]

Precision[E]

{x -> #[[1]], y -> #[[2]]}  &  /@  {{1, 
          2}, {3, 4}}

x  //  f[#] &

(2) What do the following programs do?

lglg[f_, {x_, xmin_, xmax_}, opts___] :=  
      ParametricPlot[{Log[10, x], Log[10, f]}, {x, xmin, xmax}, 
        opts]

super[lis_List] := 
      lis  //.  {x___, a_, b_, y___}  /;  
            b  ≤ a  ->  {x, a, y}

prog[xlist_List] :=  
      Module[{elements = Union[xlist]}, 
        Map[{#, Count[xlist, #]} &, elements]]

myproc[n_] :=  
      Module[{x = 0, z = 1}, 
        If[n == 0, 1,  While[x ≠ n, ++x; z = z*x]]; 
        z]

Revision class

Part II, computer algebra theory

Definition of algebraic domains

We expect the students to know the definitions of group, abelian group, ring, integral domain, Euclidean domain, and field.
All of them should be closed (axiom A0) with respect to one or two operations. Roughly speaking, the algebraic domains are the following:

GROUP:  
If a, b ∈ G, so is group multiplication a b ∈ G.
(1)  a (b c)  =  (a b) c;
(2) identity e exist, e a = a e  =  a;
(3) each element a has inverse (a^(-1)), such that a (a^(-1 )) = (a^(-1)) a  =  
          e;

Examples of group: multiplication of unitary matrices; permutations of n objects.

ABELIAN Group:
is a group with a b  =  b a.

Examples of Abelian group: the set of integers Z = {...,-3,-2,-1,0,1,2,...} with addition;  addition in Z\(TraditionalForm\`\_n\) for n  = 2, 3, 4,  ... ; multiplication of Q-{0}.

RING:
Closed under two operations: + and *.
(1) + is an Abelian group;
(2) * has identity e and a (b c)  =  (a b) c;
(3) distribution law
	\(TraditionalForm\`a\ \((b + 
              c)\)\  = \ \((a\ b)\)\  + \ \((a\ c)\), 
\((a + b)\)\ c\  = \ \((a\ c)\)\  + \ \(\((b\ c)\)\(.\)\)\)

Examples of ring: addition and multiplication in Z; addition and multiplication of n by n matrices.

INTEGRAL DOMAIN is a ring with
(1) commutative for multiplication, a b  =  b a;
(2) a b  =  a c, and a ≠ 0 implies b = c.

Examples of integral domain: the set of integers Z; polynomials over integral domain; gaussian numbers.

EUCLIDEAN DOMAIN is an integral domain such that

We can find  a  =  q b  +  r,  b ≠  0,
such that v(r)  <  v(b),  
      and v(a b)  ≥  v(b).
Of course a, b, q, r all belong to D.

Examples of Euclidean domain:  the set of all integers Z; polynomials over a field; gaussian numbers.

FIELD
(1) + is an Abelian group;
(2) * on F-{0} is an Abelian group;
(3) has distribution law.

Examples of field: addition and multiplication of rational number Q, real R, and complex number C;  Z\(TraditionalForm\`\_p\) for p a prime;  Galois fields.

Do you require me to remember all these definitions?  Yes.  At least roughly, if not precisely.

GCD, Unit, Prime, Square-Free, etc

We should know the additional concepts above.  

GCD(a, b):  in some sense largest element c such as  c | a, c | b.  (largest in what sense?)   [ c | a means c can divide a evenly, that is a = c q].

Unit:  a member that has (multiplicative) inverse.

Prime:  a prime in an integral domain is a member that can not be factored into product of two other numbers, none of them is a unit.  Of course 0, 1 and other units are not prime.

Square-free:  a is square-free if a does not have factor of the form (b^2) for some b not a unit.   That  (b^2) | c is false unless b is a unit.

Algorithms

We are expected to be able to use the following algorithms in a pencil-paper calculation:

(0) Polynomial long division;
(1) Euclidean algorithm for GCD;
(2) Extended Euclidean algorithm;
(3) Garner algorithm for Chinese remainder problem;
(4) Square-free factorization algorithm.

We'll discuss the basis for the algorithms:

Euclidean algorithm is based on 
GCD(a, b) = GCD(b, r), where
	a=q b + r.
Apply this recursively, we find remainder sequence (Subscript[r, 0])  =  a,  (Subscript[r, 1]) = b,  (Subscript[r, 2]) = r, ..., (Subscript[r, n]) = 0.
GCD(a, b) is the last nonzero remainder.

Extended Euclidean algorithm relies on the fact we have
	(Subscript[r, i]) = a (Subscript[s, i]) + b (Subscript[t, i]).

Garner's Algorithm

It is based on the mix-radix expansion

u = 
        (Subscript[v, 0])  +  (Subscript[v, 1]) (Subscript[m, 0]) +  (Subscript[v, 2]) (Subscript[m, 0]) 
            (Subscript[m, 1]) +  (Subscript[v, 3]) (Subscript[m, 0]) (Subscript[m, 1]) (Subscript[m, 2])
+  ...   +  (Subscript[v, n ]) (Subscript[m, 0]) 
              (Subscript[m, 1]) ...  (Subscript[m, n - 1])

Familiarity with modular arithmetic (i.e. compute in Z\(TraditionalForm\`\_p\)) is a must.

Square-Free Factorization  expands as
a(
          x)  =  (Subscript[a, 1])(
              x) (((Subscript[a, 2])(x))^2) (((Subscript[a, 3])(x))^3) ... 

a(x) is square free if and only if 
GCD(a(x), a' (x))  =  1 (i.e. a unit).
Division and CGD calculation is used in square-free factorization procedure.

Exercises:
(1) compute GCD(a (x), b(x)) in Q and in Z\(TraditionalForm\`\_5\) using Euclidean and Exended Euclidean algorithm for the following polynomial:
a(x)  =  
        (x^3) + (x^2) - x - 1, 
b(x)  =  x + 4
For extended Euclidean algorithm, compute s(x) and t(x).

(2) Factor a(x) above with square free factorization algorithm in Q[x]. 

(3) Solve the Chinese remainder problem for 
u  ≡  
        1 mod 2, 
u  ≡  
        3 mod  5, 
u  ≡  2 mod 7. 
To what extent the answer u is unique?

A general principle of symbolic computation

Solve the problem in a simpler domain (such as Z\(TraditionalForm\`\_p\)) several times, and then reconstruct the original problem (by .e.g., Chinese remainder theorem).

Format of Final Exam

4 questions:
% 50 on Mathematica (simple questions & programming)
% 50 on symbolic algebra (including concepts and application of algorithms)