a(11)x(11) + ... + a(1n)x(n) = b(1)
            :               
            :
        a(n1)x(n1) + ... + a(nn)x(n) = b(n)

        A X = b

        det(A) != 0   

        X = A-1 b.   

• Back Substitution
  If the matrix of the coefficients is a triangular matrix such as

              r(11) r(12) ... r(1n)
                    r(22) ... r(2n) 
       R =            .   ...   .
              0            .    .
                              r(nn)
  

  when these equations are

       r(11)x(1)+r(12)x(2)+ ... +r(1n)x(n) = b(1)
                 r(22)x(2)+ ... +r(2n)x(n) = b(2)
                           ...    ...    ...
                                 r(nn)x(n) = b(n)
  

  We can get the solution x(n) from the last equation

       x(n) = b(n)/r(nn) ,
  

  substitute to the second last equation x(n-1) is solved

       x(n-1) = (b(n-1)-r(n-1,n)x(n))/r(n-1,n-1) .
  

  In common

       x(i)=(b(i)-(r(i,i+1)k(i+1)+r(i,i+2)k(i+2)+ ... +r(i,n)k(n)))/r(i,i), 
                    i = n,n-1, ... , 1.
  

  This procedure is called " back substitution ".
  To get the triangular matrix from the original A we resort to the method of elimination.
  
  
• Gauss Elimination
  Gauss Elimination is a very famous method to convert the common matrix into upper triangular matrix.It employs the fundamental convertion of matrix : swap two lines, constant multiples of one line is substracted from the other line and etc.After n-1 steps the original matrix(n*n) is converted into the required upper triangular , then we can turn to the back substitution.
  Here we use the Gaussian Elimination with partial pivoting in column .The computing steps are:
  (1) Select pivot.Select k, to make

       |a(k,j)|= max |a(i,j)| ;

  if a(k,j)=0, then det(A)=0, stop here; else, go on.
  (2) Swap line j and k in matrix [A,b]
  (3) For i=j,j+1,j+2,...,n,compute l(i,j) and store it in the position of a(i,j)

       a(i,j) = l(i,j) = a(i,j)/a(j,j).
  

  Then compute the elements in the submatrix after line j column j in [A,b]. Namely, for i = j,j+1,...,n , k = j+1, ... , n

       a(i,k) = a(i,k) - l(i,j)a(j,k) ,  
  

  while other elements are not changed.
  After finishing the above steps the original matrix

      [A,b]
  

  is transfered into

      [R,b],
  

  where R is the upper triangular matrix. At the same time the old equations is converted into

       RX=b .
  

  Now we can use the back substitution to get solutions.
  

2. Developing Data Parallelism

3. Running and Analysis

Table1: 

#proc      128*128     256*256    512*512    1024*1024     2048*2048     
-------------------------------------------------------------------------------------  
   1             0.19          3.54           40.05           230.66           2636.24            
-------------------------------------------------------------------------------------
   4             1.80          3.85           14.75           64.04            706.00
-------------------------------------------------------------------------------------

Bibliography