readme

Matrix Iteration Methods. Matlab Implementation.

============= README file for testing the Iterative Templates ==================
Version 1.1 August, 2006.

The directory in which this README file is found contains the MATLAB versions 
of the algorithms discussed in the book ``Templates for the Solution of Linear 
Systems: Building Blocks for Iterative Methods'', by Richard Barrett, Michael 
Berry, Tony F. Chan, James Demmel, June Donato, Jack Dongarra, Victor Eijkhout,
Roldan Pozo, Charles Romine, and Henk Van der Vorst, SIAM Publication, 1993.  
In addition, there are test routines that a user can execute to verify that 
the routines are working. 

================================================================================

Test routines have been included with the templates algorithms. 
The user should run tester.m to make sure that the code has been 
successfully downloaded and unpacked. Further, tests for individual algorithms
are included in this release for convenience. These test functions are
named test_<algorithm>.m. 

In the directory where the tar file has been ``untarred'', start up
MATLAB. In MATLAB type "tester".  ( The tests require only a few seconds
on an old Sparc Ultra4 workstation.) 

The test functions generate a few small, easy to solve linear systems, which
then are solved by appropriate algorithms. During execution the following output 
should print to the screen:

test =

     1


test =

     2

     :
     :

test =

     6

TESTING =
      
             COMPLETE


RESULTS =

             ALL TESTS PASSED

Two problems can occur, illustrated below using CG:

(i)     cg failed to converge for

        test = 

                3

        error =

                13.234

This means that the Conjugate Gradient algorithm failed to find the
approximate solution to the set tolerance of eps*1000. After the
maximum number of iterations, the normalized residule,
called ``error'' is 13.234.

(ii) cg failed for initial guess = solution

One of the tests inputs the exact solution as the initial guess
(as computed using MATLABs direct method x = A \ b.) Each algorithm
should recognize this and immediately return. If there is a problem,
the following message will print to the screen:

     cg failed for initial guess = solution

These errors will be reported as they occur. Finally, an overall
report for each suspect algorithm will print to screen:

     cg failed test (failed to converge)

     cg failed test (initial guess = solution error)

If an error occurs, the user may be able to track down the source of the
problem by testing the algorithm individually. 

================================================================================
Files:
================================================================================

The basic template routines are:

1)  cg.m        Conjugate Gradient method

2)  bicg.m      Bi-conjugate Gradient method

3)  cgs.m       Conjugate Gradient squared method

4)  bicgstab.m  Bi-conjugate Gradient stabilized method

5)  gmres.m     Generalized Minimal Residual method

6)  qmr.m       Quasi-Minimal residual method

7)  cheby.m     Chebyshev method

8)  jacobi.m    Jacobi method

9)  sor.m       Successive Over-Relaxation method

Utility routines:

1) rotmat.m: Computes the elements for the Given rotation matrix used by gmres.m.

2) split.m: Matrix splitting functionality for jacobi.m and sor.m.

Test routines:

1) tester.m   main routine

2) matgen.m   Driver routine for generating the test matrices. 

   The test matrices are generated by:  

     i) lehmer.m
    ii) makefish.m
   iii) wathen.m

   Descriptions of the test matrices are found in these files.

3) test_<algorithm>.m: Test functions for individual algorithms.

      i) test_bicg.m
     ii) test_bicgstab.m
    iii) test_cg.m
     iv) test_cgs.m
      v) test_cheby.m
     vi) test_gmres.m
    vii) test_jacobi.m
   viii) test_qmr.m
     ix) test_sor.m

Tests:

1. Poisson problem, on a 4x4 grid, so matrix is dimension 16.

2. Wathen matrix: consistent mass matrix, dimension 40.

3. Wathen matrix: consistent mass matrix, diagonally scaled, dimension 40.

4. Lehmer matrix, dimension 5.

5. Lehmer matrix, dimension 10.

6. Poisson problem, on a 4x4 grid, so matrix is dimension 16. However,
     exact solution is input as initial guess, which should be immediately
     detected by algorithm.

=== End README.