DETAILS OF ITERATIVE TEMPLATES TEST: Univ. of Tennessee and Oak Ridge National Laboratory October 1, 1993 Details of these algorithms are described in "Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods", Barrett, Berry, Chan, Demmel, Donato, Dongarra, Eijkhout, Pozo, Romine, and van der Vorst, SIAM Publications, 1993. (ftp netlib2.cs.utk.edu; cd linalg; get templates.ps). MACHINE PRECISION = 1.11E-16 CONVERGENCE TEST TOLERANCE = 1.00E-15 For a detailed description of the following information, see the end of this file. ====================================================== CONVERGENCE NORMALIZED NUM METHOD CRITERION RESIDUAL ITER INFO FLAG ====================================================== see the end of this file. Order 36 SPD 2-d Poisson matrix (no preconditioning) CG 1.28E-16 3.08E-03 6 Chebyshev 6.17E-11 3.29E+02 144 1 SOR 2.18E-14 2.39E-01 144 1 BiCG 1.28E-16 3.08E-03 6 CGS NaN NaN 144 1 BiCGSTAB 1.29E-17 3.85E-03 6 GMRESm 2.55E-20 8.01E+15 1 X QMR 2.58E-16 5.40E-03 6 Jacobi 3.02E-08 6.16E+05 144 1 ------------------------------------------------------- Order 36 SPD 2-d Poisson matrix (Jacobi preconditioning) CG 1.28E-16 3.08E-03 6 Chebyshev 1.20E-06 6.41E+06 144 1 SOR 2.18E-14 2.39E-01 144 1 BiCG 1.28E-16 3.08E-03 6 CGS NaN NaN 144 1 BiCGSTAB 1.29E-17 3.85E-03 6 GMRESm 1.27E-17 3.79E+13 1 X QMR 2.58E-16 5.40E-03 6 ------------------------------------------------------- Order 21 SPD Wathen matrix (no preconditioning) CG 2.74E-18 1.24E-03 26 Chebyshev 1.52E-02 2.32E+10 84 1 SOR 8.41E-11 3.28E+02 84 1 BiCG 2.74E-18 1.24E-03 26 CGS 4.07E-16 6.80E-02 27 BiCGSTAB 1.24E-16 1.55E-03 27 GMRESm 7.83E-16 2.95E+15 1 X QMR 3.36E-16 1.08E-03 26 ------------------------------------------------------- Order 21 SPD Wathen matrix (Jacobi preconditioning) CG 9.10E-22 6.18E-04 20 Chebyshev 5.58E-01 5.28E+11 84 1 SOR 8.41E-11 3.28E+02 84 1 BiCG 9.10E-22 6.18E-04 20 CGS NaN NaN 84 1 BiCGSTAB 6.78E-16 2.86E+12 74 X GMRESm 8.93E-18 9.33E+11 1 X QMR 4.12E-16 1.24E-03 20 ------------------------------------------------------- Order 27 SPD 3-d Poisson matrix (no preconditioning) CG 2.83E-17 3.33E-03 4 Chebyshev 9.50E-16 1.41E-02 68 SOR 9.92E-16 2.50E-03 24 BiCG 2.83E-17 3.33E-03 4 CGS 1.34E-17 2.70E-03 4 BiCGSTAB 1.42E-18 3.33E-03 4 GMRESm 2.53E-17 4.50E+15 1 X QMR 4.15E-16 6.45E-03 4 Jacobi 7.35E-16 1.33E-02 98 ------------------------------------------------------- Order 27 SPD 3-d Poisson matrix (Jacobi preconditioning) CG 2.41E-17 4.58E-03 4 Chebyshev 6.75E-14 4.74E-01 108 1 SOR 9.92E-16 2.50E-03 24 BiCG 2.41E-17 4.58E-03 4 CGS 4.09E-17 3.33E-03 4 BiCGSTAB 4.29E-18 4.99E-03 4 GMRESm 1.61E-17 5.25E+12 1 X QMR 2.50E-16 3.74E-03 4 ------------------------------------------------------- Order 125 PDE1 nonsymmetric matrix (no preconditioning) BiCG 2.13E-16 1.35E-03 65 CGS 8.11E-16 6.68E-03 91 BiCGSTAB 6.90E-16 5.12E-03 100 GMRESm 5.02E-16 1.30E+21 1 X QMR 1.44E-14 1.41E-02 500 1 ------------------------------------------------------- Order 125 PDE1 nonsymmetric matrix (Jacobi preconditioning) BiCG 7.38E-16 7.58E-02 60 CGS 3.76E-16 2.29E-02 71 BiCGSTAB 2.96E-16 4.05E-03 84 GMRESm 9.03E-26 4.17E+21 1 X QMR 9.12E-14 6.65E-02 500 1 ------------------------------------------------------- Order 125 PDE2 nonsymmetric matrix (no preconditioning) BiCG 7.58E-16 3.55E-02 31 CGS 9.46E-16 1.88E+00 40 BiCGSTAB 9.61E-03 1.36E+11 248 -10 GMRESm 3.44E-16 1.53E+22 1 X QMR 1.03E-14 9.08E-02 500 1 ------------------------------------------------------- Order 125 PDE2 nonsymmetric matrix (Jacobi preconditioning) BiCG 8.97E-16 4.95E-02 31 CGS 1.68E-16 1.87E+00 37 BiCGSTAB 2.62E-09 2.93E+04 500 1 GMRESm 1.62E-19 1.18E+19 1 X QMR 1.44E-14 9.14E-02 500 1 ------------------------------------------------------- Order 125 PDE3 nonsymmetric matrix (no preconditioning) BiCG 1.18E-14 3.86E-03 500 1 CGS 8.28E+12 4.14E+12 500 1 BiCGSTAB 1.11E+02 5.48E+11 116 -10 GMRESm 2.88E-17 4.79E+15 1 X QMR 6.97E-13 8.26E-03 500 1 ------------------------------------------------------- Order 125 PDE3 nonsymmetric matrix (Jacobi preconditioning) BiCG 8.28E-16 2.34E-03 443 CGS 2.64E+08 3.61E+12 500 1 BiCGSTAB 4.69E+00 9.06E+11 106 -10 GMRESm 7.19E-19 4.64E+12 1 X QMR 6.01E-14 2.22E-03 500 1 ------------------------------------------------------- Order 36 PDE4 nonsymmetric matrix (no preconditioning) BiCG 1.10E-16 1.11E-02 42 CGS 9.41E-01 4.60E+11 144 1 BiCGSTAB 1.25E-01 6.84E+10 144 1 GMRESm 8.28E-22 1.43E+13 1 X QMR 1.47E-14 8.35E-03 144 1 ------------------------------------------------------- Order 36 PDE4 nonsymmetric matrix (Jacobi preconditioning) BiCG 1.10E-16 1.11E-02 42 CGS 9.41E-01 4.60E+11 144 1 BiCGSTAB 1.25E-01 6.84E+10 144 1 GMRESm 5.95E-18 1.64E+13 1 X QMR 1.47E-14 8.35E-03 144 1 ------------------------------------------------------- ====== LEGEND: ====== ================== SYSTEM DESCRIPTION ================== SPD matrices: WATH: "Wathen Matrix": consistent mass matrix F2SH: 2-d Poisson problem F3SH: 3-d Poisson problem PDE1: u_xx+u_yy+au_x+(a_x/2)u for a = 20exp[3.5(x**2+y**2 )] Nonsymmetric matrices: PDE2: u_xx+u_yy+u_zz+1000u_x PDE3 u_xx+u_yy+u_zz-10**5x**2(u_x+u_y+u_z ) PDE4: u_xx+u_yy+u_zz+1000exp(xyz)(u_x+u_y-u_z) ===================== CONVERGENCE CRITERION ===================== Convergence criteria: residual as reported by the algorithm: ||AX - B|| / ||B||. Note that NaN may signify divergence of the residual to the point of numerical overflow. =================== NORMALIZED RESIDUAL =================== Normalized Residual: ||AX - B|| / (||A||||X||*N*TOL). This is an apostiori check of the iterated solution. ==== INFO ==== If this column is blank, then the algorithm claims to have found the solution to tolerance (i.e. INFO = 0). This should be verified by checking the normalizedresidual. Otherwise: = 1: Convergence not achieved given the maximum number of iterations. Input parameter errors: = -1: matrix dimension N < 0 = -2: LDW < N = -3: Maximum number of iterations <= 0. = -4: For SOR: OMEGA not in interval (0,2) For GMRES: LDW2 < 2*RESTRT = -5: incorrect index request by uper level. = -6: incorrect job code from upper level. <= -10: Algorithm was terminated due to breakdown. See algorithm documentation for details. ==== FLAG ==== X: Algorithm has reported convergence, but approximate solution fails scaled residual check. ===== NOTES ===== GMRES: For the symmetric test matrices, the restart parameter is set to N. This should, theoretically, result in no restarting. For nonsymmetric testing the restart parameter is set to N / 2. Stationary methods: - Since the residual norm ||b-Ax|| is not available as part of the algorithm, the convergence criteria is different from the nonstationary methods. Here we use || X - X1 || / || X ||. That is, we compare the current approximated solution with the approximation from the previous step. - Since Jacobi and SOR do not use preconditioning, Jacobi is only iterated once per system, and SOR loops over different values for OMEGA (the first time through OMEGA = 1, i.e. the algorithm defaults to Gauss-Siedel). This explains the different residual norms for SOR with the same matrix.