Symbolic Computing

LT20, 4:00-6:00pm
Wed, 26 March 2003

Intermediate expression swell

One problem with symbolic or exact computation with integers is that the intermediate results get bigger and bigger.  This already shows up in QCD computation. 

Here is another example of similar nature.

Suppose that we want to solve the linear system with only integer arithmetic (i.e. compute in Z):

22  x  +  44  y + 74  z  =  
        1,         (1)
15  x + 14  y   - 
          10  z  =  -2,      (2)
-25 x - 28  y + 20  z  =  
        34.       (3)

We can use a variant of Gaussian elimination, e.g.,  22* Eq(2) - 15* Eq(1)  to void division,  we get
\(TraditionalForm\`22  x\  + \ 44  y\ \  + \ \ \ \ 74\ z\  = \ 
        1, 
\ \ \ \ \ \ \ \ \ \ \(-352\) y - 
          1330  z\  = \ \(-59\), 
\ \ \ \ \ \ \ \ \ \ \ \ \ 484\ y\  + 2290\ z\  = \ 773. \)
 Similarly, using the second equation to eliminate 44  y and 484  y in the first and last equation, and use the new last equation to eliminate z, we get
 1257315840  x  =  
        7543895040, 
-57150720 y  =  
        314328960, 
162360 z  =  243540. 

Using a GCD computation on integers, we can reduce it to lowest terms, and find that

x = 6,  y = -11/2, and z = 3/2.

So, what is the moral of the story?

The idea of using a simpler algebraic structure to do calculations several times, and reconstruction the solutions of original problem.

This idea is used in factorization of polynomials, in symbolic solutions of linear equations, and so on.

Solving the linear equation mod 7

Since (Subscript[Z, 7]) is a field, we can do +, -, *, and / as usual.   The multiplication table looks like this:

* mod 7      0     1     2     3     4     5     6
_________________________________
0                0      0     0     0     0     0     0
1                0      1     2     3     4     5     6
2                0      2    4      6     1     3    5
3                0      3    6      2     5     1    4
4                0      4     1    5      2    6     3
5                0      5      3    1     6    4     2
6                0      6     5     4     3     2     1

From this table, we see that (2^(-1)) = 4,  (3^(-1)) = 5,  
      (6^(-1)) = 6.    

The original equation:
2  x  +  44  y  + 74  z  =  
        1, 
15  x + 14  y - 
          10  z  =  -2,    
-25 x - 28  y + 
          20  z  =  34. 
when mod 7, becomes much simpler:
x  +  2  y + 4  z  =  
        1, 
x  +  0  y  + 4  z  =  
        5, 
3  x   +  0  y  +  6  z  =  6. 

Similar Gaussian elimination (mod 7) gives:
x  =  6 (mod 7),  y =  5 (mod 7),  
      z  =  5 (mod). 
(spend few minutes to work out the answers)
The workings:    
Please fill in the steps.  

Suppose we obtained x mod 7 = 6, x mod 11  = 6, x mod 13 = 11, x mod 17 = 5, and  x mod 19 = 9, can we recover the original x in Z?

Ring morphisms

Let R and R' be two rings.  Then a mapping Φ : R → R' is called a ring morphism if
     (i) Φ(a + b)= Φ(a)  +  Φ(b) for all a, b ∈ R;
    (ii) Φ(a ∘b) = Φ(a) Φ(b) for all a, b ∈ R;
   (iii) Φ(1) = 1.

What this means is that a mapping between two rings exists that preserves all the operations.   Informally, it means that formulas in ring R is also valid in R'.

Example:

Consider mapping from ring Z (the set of all integers) to (Subscript[Z, p]), given by Φ(a)  =  a mod p.   The mod operation takes an element in Z ( ..., -2, -1, 0, 1, 2, 3, ...) to an element in (Subscript[Z, p])(0, 1, 2,  ... , p - 1).   The mod operation is a ring morphism since \(TraditionalForm\`\((a + 
              b)\)\ mod\ p\  = \ {\((a\ mod\ p)\)\  + \ \((a\ mod\ p)\)}\ mod\ p, 
\((a*
              b)\)\ mod\ p\  = \ {\ \((a\ mod\ p)\)\ *\ \((b\ mod\ p)\)\ }\ mod\ p, 
1\ mod\ p\  = \ 1. \)

Proof that Φ(0) = 0; and Φ(-a) = Φ(a) for all ∈ R, where Φ is a ring morphism.

If Φ is injective  (one-to-one), it is called monomorphism;

If Φ is surjective (onto), it is called epimorphism;

If Φ is bijective (one-to-one and onto), it is called isomorphism.

Check your math books to find out what are injective, surjective, and bijective.  Is the mapping Z → (Subscript[Z, p]) by Φ(a) = (a mod p), a monomorphism? an epimorphism, or isomorphism?

Chinese remainder Theorem

An example of the Chinese remainder problem is as following:  an integer x, when divided by 3 remainder is 2, when divided by 5 remainder is 3, when divided by 7 remainder is 2, what is x?  We write:
x ≡ 2 mod 3,
x ≡ 3 mod 5,
x ≡ 2 mod 7.
The three-bar equal sign (≡) denotes congruential relation, i.e.,
a ≡  b mod p means  a - b is a multiple of p.

Chinese Remainder Theorem:  
Let (Subscript[m, 0]), (Subscript[m, 1]), ..., (Subscript[m, n]) ∈ Z be integers which are pairwise relatively prime - i.e.,
	GCD((Subscript[m, i]), (Subscript[m, j])) = 1   for i  ≠  j,
and let (Subscript[u, i]) ∈ (Subscript[Z, (Subscript[m, i])]), i  =  0, 1,   ... ,  n be n+1 specified residues.  For any fixed integer a ∈ Z there exists a unique integer u ∈ Z which satisfies the following conditions:
a  ≤  u  <  a  +  m, where m  =  (∏_(i = 0)^n) (Subscript[m, i]);
u  ≡  (Subscript[u, i]) (mod (Subscript[m, i])),  0 ≤ i ≤ n.

The theorem says if we choose a set of numbers which have unit GCD for any pair, such as, 3,  7, 10, 13 (not necessarily all primes), or equivalently, GCD((Subscript[m, 0]), (Subscript[m, 1]),  ... , (Subscript[m, n]))  =  1, then the set of equations
u ≡  
        2 mod 3, 
u ≡  
        2 mod 7, 
u ≡  
        5 mod 10, 
u ≡  8 mod 13
has a unique solution modulo  m  =  3*7*10*13=2730.

Note that in the theorem if we choose a  =  0, then the solution 0  ≤  u  <  m.  If we take a  =  -Floor [m/2], then u can be negative.

Garner's algorithm for Chinese remainder problem

Representation of (Subscript[Z, p])
In (Subscript[Z, p]), if a is a number between 0 to p - 1, any integer a  + k*p is considered the same number.  Thus if p=5, 3, 8, 13, as well as -2, or -7 are considered all equivalent to 3. 
In applying Garner's algorithm, we need to take a consistent representation either
(i)  positive representation:  0 ≤ a < p for a  in (Subscript[Z, p]);
or 
(ii) symmetric representation:  -(p - 1)/2 ≤  
        a  ≤  (p - 1)/2, (assume p is odd)

For example, in positive presentation, the value in (Subscript[Z, 5]) ranges from 0 to 4.  In the symmetric representation the value in (Subscript[Z, 5]) is -2,  -1,  0,  1,  2.

The starting point in Garner's algorithm is to represent the solution u in the mixed radix representation:

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

      
where (Subscript[v, i])  ∈  (Subscript[Z, (Subscript[m, i])]) for i  =  0,  1,   ... ,  n.

Since (Subscript[v, i]) is interpreted as in Z\(TraditionalForm\`\_\(m\_i\)\), the mixed radix representation formula must be valuated in Z\(TraditionalForm\`\_\(m\_i\)\) when computing (Subscript[v, i]).

An example:
x ≡ 2 mod 3,
x ≡ 3 mod 5,
x ≡ 2 mod 7,
(Subscript[m, 0]) =  3,  (Subscript[m, 1]) = 5,  (Subscript[m, 2]) = 7,  n = 2. 
we can determine x modulo 3*5*7=105.   Write 
x  =  (Subscript[v, 0])  +  (Subscript[v, 1])*3  +  (Subscript[v, 2])*3*5.
If we mod 3 to the above equation, we get
x mod 3  =  2  =  (Subscript[v, 0]).  Note that (Subscript[v, 0]) is in (Subscript[Z, 3]), using positive presentation, we have uniquely, (Subscript[v, 0]) =  2.   So
x  -  2  =  (Subscript[v, 1])*3  +  (Subscript[v, 2])*15. 
Mod 5 to the above equation, we get
x mod 5  -  
          2 mod 5  =  ((Subscript[v, 1]) * 3) mod 5.
We have isolated (Subscript[v, 1]). Since (Subscript[v, 1])lives in (Subscript[Z, 5]), we have to solve the above equation in (Subscript[Z, 5]).   That is
(3 - 2) = (Subscript[v, 1])*3   (in (Subscript[Z, 5]))
or (Subscript[v, 1]) =  1 * (3^(-1)) =  2  (since the multiplicative inverse of 3 in (Subscript[Z, 5]) is 2).  
We determine the last unknown through
x  -  2  -  2*3 =  (Subscript[v, 2])*15
Mod 7 to the above equation, using x mod 7  =  2, we get
2 - 2 - 2*3 = -6  =  
          (Subscript[v, 2]) * 15  mod 7 = (Subscript[v, 2]) mod 7.
Note that 15 = 3*5, and (15^(-1)) = (3^(-1))*(5^(-1)) = 5*3 = 
            15  ≡ 1  (mod 7). 
Solving the equation in (Subscript[Z, 7]), we have
(Subscript[v, 2])  =  -6  =  1  (mod 7).  So the final result for x is
x  =  (Subscript[v, 0]) +  (Subscript[v, 1])*3  +  (Subscript[v, 2])*15
    =  2  +  2*3  +  
          1*15  
     = 23.
We can verify that:

{Mod[23, 3],  Mod[23, 5],  Mod[23, 7]}

Exercise:  Work out the solution for:
u ≡  
        2 mod 3, 
u ≡  
        2 mod 7, 
u ≡  
        5 mod 10, 
u ≡  8 mod 13

Here is a formal description of the Garner's algorithm (not a runnable Mathematica program):

ChineseRemainder[{(Subscript[m, 0]),  (Subscript[m, 1]),   ... ,  
          (Subscript[m, n])}, 
{(Subscript[u, 0]),  (Subscript[u, 1]),   ... ,  (Subscript[u, n])}]  =  
      Module[{ ... }, 

 (* 
          Given positive moduli (Subscript[m, i]) ∈  
            Z,  (0  ≤  i  ≤  
                  n) which are pairwise relatively prime and given corresponding residue (Subscript[u, i]) ∈  (Subscript[Z, (Subscript[m, i])]), 
          compute the unique integer u  ∈  (Subscript[Z, m]) (where m  =  (Subscript[m, 0])*(Subscript[m, 1])* ...  
                      (Subscript[m, n])) such that u  ≡  (Subscript[u, i]) (mod (Subscript[m, i])),  i  =  0,  
          1,   ... ,  n. *) 

 (* 
          Step 1 :  
              Compute the required inverses (Subscript[γ, k])  =  ((((Subscript[m, 0])*(Subscript[m, 1])* ...  (Subscript[m, k - 1])))^(-1)) (mod (Subscript[m, k])),  
          using a procedure reciprocal[a, 
              q] which computes (a^(-1)) (mod q). *) 
For[k = 1,  
          k ≤ 
            n,  ++k, 
p  =  (Subscript[Φ, (Subscript[m, k])])[
              (Subscript[m, 0])]; 
For[i  =  1, 
            i  <  k,  ++i, 
p  =  (Subscript[Φ, (Subscript[m, k])])[
                p*(Subscript[m, i])]
]; 
(Subscript[γ, k])  =  reciprocal[p, 
              (Subscript[m, k])]
]; 

 (* Step 2,  
          Compute the mix radix coefficients (Subscript[v, k]) *) 
(Subscript[v, 0])  =  (Subscript[u, 0]); 
For[k = 1, 
          k ≤ n, ++k, 
t  =  
            (Subscript[v, k - 1]); 
For[j  =  k - 2,  
            k  ≥  
              0,  --k, 
t  =  Φ[
                t*(Subscript[m, j]) + 
                  (Subscript[v, j])]
]; 
(Subscript[v, k]) =  Φ[((Subscript[u, k]) - 
                    t)*(Subscript[γ, k])];
]; 

 (* Step 3,  
          Convert from mixed radix representation to standard representation *) 
u  =  (Subscript[v, n]); 
For[
          k  =  n - 1,  
          k  ≥  0,  --k, 
u  =  
            u *(Subscript[m, k])  +  
              (Subscript[v, k])
]; 
u
]

How do we then solve linear equations with integer coefficients with the help of Garner's algorithm?

Recommended Readings:

From `Algorithms for Computer Algebra', by K. O. Geddes, S. R. Czapor, and G. Labahn.

Chapter 2, page 23 to 37, 42 to 43
Chapter 5, page 151 to 155, 171 to 183.