============= README file for testing the Iterative Templates ==================
Version 1.0 November 1, 1993.
This file 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 routine that a user can execute
to verify that the routines are working.
================================================================================
A test routine has been included with the templates algorithms.
The user should run the test to make sure that the code has been
successfully downloaded and unpacked.
In the directory where the shar file has been ``unshared'' startup
MATLAB. In MATLAB type "tester". ( The tests takes less than one
minute on a Sparc workstation. ) As each test system is generated
and solved by the appropriate algorithms, the following output
should print to the screen:
test =
1
test =
2
:
:
test =
6
3. RESULTS: If all goes well, the following message should appear:
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. This can be done by generating
a system using the following:
A = makefish( 3 );
b = ones(9,1);
x = 0*b;
M = eye(9);
max_it = 10;
tol = .000001;
[x, error, iter, flag] = cg(A, x, b, M, max_it, tol)
This should generate a 9x9 Poisson matrix, which is block tridiagonal, with
4's on the diagonal, -1's on the offdiagonal, and -1's on the diagonals of the
offdiagonal blocks. CG should have no trouble computing the solution in
3 or 4 iterations.
================================================================================
The basic template routines are:
* cg.m Conjugate Gradient method
* bicg.m Bi-conjugate Gradient method
* cgs.m Conjugate Gradient squared method
* bicgstab.m Bi-conjugate Gradient stabilized method
* gmres.m Generalized Minimal Residual method
- calls rotmat.m for computing the elements of the Givens matrix.
* qmr.m Quasi-Minimal residual method
* cheby.m Chebyshev method
* jacobi.m Jacobi method
* sor.m Successive Over-Relaxation method
- jacobi and sor require a utility routine split.m, which performs
the matrix splitting.
================================================================================
Routines for executing the test routine:
tester.m main routine
matgen.m driver routine for generating the test matrices:
The test matrices are generated by: lehmer.m
makefish.m
wathen.m