============= 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