1 2 DETAILS OF ITERATIVE TEMPLATES TEST: 3 4 Univ. of Tennessee and Oak Ridge National Laboratory 5 October 1, 1993 6 Details of these algorithms are described in "Templates 7 for the Solution of Linear Systems: Building Blocks for 8 Iterative Methods", Barrett, Berry, Chan, Demmel, Donato, 9 Dongarra, Eijkhout, Pozo, Romine, and van der Vorst, 10 SIAM Publications, 1993. 11 (ftp netlib2.cs.utk.edu; cd linalg; get templates.ps). 12 13 14MACHINE PRECISION = 1.11E-16 15CONVERGENCE TEST TOLERANCE = 1.00E-15 16 17 18 For a detailed description of the following information, 19 see the end of this file. 20 21 ====================================================== 22 CONVERGENCE NORMALIZED NUM 23 METHOD CRITERION RESIDUAL ITER INFO FLAG 24 ====================================================== 25 26 see the end of this file. 27Order 36 SPD 2-d Poisson matrix (no preconditioning) 28 29 CG 1.28E-16 3.08E-03 6 30 Chebyshev 6.17E-11 3.29E+02 144 1 31 SOR 2.18E-14 2.39E-01 144 1 32 BiCG 9.09E-17 3.08E-03 6 33 CGS NaN NaN 144 1 34 BiCGSTAB 1.29E-17 3.85E-03 6 35 GMRESm 4.00E-20 8.01E+15 1 X 36 QMR 1.99E-16 5.40E-03 6 37 Jacobi 3.02E-08 6.16E+05 144 1 38 ------------------------------------------------------- 39Order 36 SPD 2-d Poisson matrix (Jacobi preconditioning) 40 41 CG 1.28E-16 3.08E-03 6 42 Chebyshev 1.20E-06 6.41E+06 144 1 43 SOR 2.18E-14 2.39E-01 144 1 44 BiCG 9.09E-17 3.08E-03 6 45 CGS NaN NaN 144 1 46 BiCGSTAB 1.29E-17 3.85E-03 6 47 GMRESm 9.82E-18 3.79E+13 1 X 48 QMR 1.99E-16 5.40E-03 6 49 ------------------------------------------------------- 50Order 21 SPD Wathen matrix (no preconditioning) 51 52 CG 2.74E-18 1.24E-03 26 53 Chebyshev 1.52E-02 2.32E+10 84 1 54 SOR 8.41E-11 3.28E+02 84 1 55 BiCG 8.91E-18 1.39E-03 26 56 CGS 4.07E-16 6.80E-02 27 57 BiCGSTAB 1.24E-16 1.55E-03 27 58 GMRESm 7.83E-16 2.95E+15 1 X 59 QMR 2.98E-16 6.18E-04 26 60 ------------------------------------------------------- 61Order 21 SPD Wathen matrix (Jacobi preconditioning) 62 63 CG 9.10E-22 6.18E-04 20 64 Chebyshev 5.58E-01 5.28E+11 84 1 65 SOR 8.41E-11 3.28E+02 84 1 66 BiCG 7.45E-22 1.08E-03 20 67 CGS NaN NaN 84 1 68 BiCGSTAB 6.78E-16 2.86E+12 74 X 69 GMRESm 5.97E-18 9.33E+11 1 X 70 QMR 6.72E-16 1.08E-03 20 71 ------------------------------------------------------- 72Order 27 SPD 3-d Poisson matrix (no preconditioning) 73 74 CG 2.83E-17 3.33E-03 4 75 Chebyshev 9.50E-16 1.83E-02 68 76 SOR 9.92E-16 2.50E-03 24 77 BiCG 3.06E-17 2.91E-03 4 78 CGS 1.34E-17 2.70E-03 4 79 BiCGSTAB 1.42E-18 3.33E-03 4 80 GMRESm 2.53E-17 4.50E+15 1 X 81 QMR 4.77E-16 5.83E-03 4 82 Jacobi 7.35E-16 1.33E-02 98 83 ------------------------------------------------------- 84Order 27 SPD 3-d Poisson matrix (Jacobi preconditioning) 85 86 CG 2.41E-17 4.58E-03 4 87 Chebyshev 6.75E-14 4.79E-01 108 1 88 SOR 9.92E-16 2.50E-03 24 89 BiCG 2.70E-17 4.58E-03 4 90 CGS 4.09E-17 3.33E-03 4 91 BiCGSTAB 4.29E-18 4.99E-03 4 92 GMRESm 3.31E-17 5.25E+12 1 X 93 QMR 4.10E-16 4.99E-03 4 94 ------------------------------------------------------- 95Order 125 PDE1 nonsymmetric matrix (no preconditioning) 96 97 BiCG 1.03E-16 1.22E-03 62 98 CGS 8.11E-16 6.68E-03 91 99 BiCGSTAB 6.90E-16 5.12E-03 100 100 GMRESm 3.45E-16 1.30E+21 1 X 101 QMR 2.21E-15 1.08E-03 500 1 102 ------------------------------------------------------- 103Order 125 PDE1 nonsymmetric matrix (Jacobi preconditioning) 104 105 BiCG 8.62E-16 6.68E-02 61 106 CGS 3.76E-16 2.29E-02 71 107 BiCGSTAB 2.96E-16 4.05E-03 84 108 GMRESm 9.85E-16 4.17E+21 1 X 109 QMR 1.40E-13 1.42E-01 500 1 110 ------------------------------------------------------- 111Order 125 PDE2 nonsymmetric matrix (no preconditioning) 112 113 BiCG 2.06E-16 2.84E-02 33 114 CGS 9.46E-16 1.88E+00 40 115 BiCGSTAB 9.61E-03 1.36E+11 248 -10 116 GMRESm 6.00E-16 1.53E+22 1 X 117 QMR 1.26E-14 1.05E-01 500 1 118 ------------------------------------------------------- 119Order 125 PDE2 nonsymmetric matrix (Jacobi preconditioning) 120 121 BiCG 1.39E-16 4.96E-02 33 122 CGS 1.68E-16 1.87E+00 37 123 BiCGSTAB 2.62E-09 2.93E+04 500 1 124 GMRESm 1.62E-19 1.18E+19 1 X 125 QMR 2.76E-15 5.54E-02 500 1 126 ------------------------------------------------------- 127Order 125 PDE3 nonsymmetric matrix (no preconditioning) 128 129 BiCG 9.48E-16 2.47E-03 399 130 CGS 8.28E+12 4.14E+12 500 1 131 BiCGSTAB 1.11E+02 5.48E+11 116 -10 132 GMRESm 2.88E-17 4.79E+15 1 X 133 QMR 9.09E-14 3.02E-03 500 1 134 ------------------------------------------------------- 135Order 125 PDE3 nonsymmetric matrix (Jacobi preconditioning) 136 137 BiCG 9.51E-16 2.47E-03 447 138 CGS 2.64E+08 3.61E+12 500 1 139 BiCGSTAB 4.69E+00 9.06E+11 106 -10 140 GMRESm 1.28E-19 4.75E+12 1 X 141 QMR 1.10E-13 3.45E-03 500 1 142 ------------------------------------------------------- 143Order 36 PDE4 nonsymmetric matrix (no preconditioning) 144 145 BiCG 5.60E-16 5.56E-03 42 146 CGS 9.41E-01 4.60E+11 144 1 147 BiCGSTAB 1.25E-01 6.84E+10 144 1 148 GMRESm 5.94E-23 1.42E+13 1 X 149 QMR 2.20E-14 6.95E-03 144 1 150 ------------------------------------------------------- 151Order 36 PDE4 nonsymmetric matrix (Jacobi preconditioning) 152 153 BiCG 5.60E-16 5.56E-03 42 154 CGS 9.41E-01 4.60E+11 144 1 155 BiCGSTAB 1.25E-01 6.84E+10 144 1 156 GMRESm 7.21E-17 6.76E+12 1 X 157 QMR 2.20E-14 6.95E-03 144 1 158 ------------------------------------------------------- 159 160 ====== 161 LEGEND: 162 ====== 163 164 ================== 165 SYSTEM DESCRIPTION 166 ================== 167 168 SPD matrices: 169 170 WATH: "Wathen Matrix": consistent mass matrix 171 F2SH: 2-d Poisson problem 172 F3SH: 3-d Poisson problem 173 174 PDE1: u_xx+u_yy+au_x+(a_x/2)u 175 for a = 20exp[3.5(x**2+y**2 )] 176 177 Nonsymmetric matrices: 178 179 PDE2: u_xx+u_yy+u_zz+1000u_x 180 PDE3 u_xx+u_yy+u_zz-10**5x**2(u_x+u_y+u_z ) 181 PDE4: u_xx+u_yy+u_zz+1000exp(xyz)(u_x+u_y-u_z) 182 183 ===================== 184 CONVERGENCE CRITERION 185 ===================== 186 187 Convergence criteria: residual as reported by the 188 algorithm: ||AX - B|| / ||B||. Note that NaN may signify 189 divergence of the residual to the point of numerical overflow. 190 191 =================== 192 NORMALIZED RESIDUAL 193 =================== 194 195 Normalized Residual: ||AX - B|| / (||A||||X||*N*TOL). 196 This is an apostiori check of the iterated solution. 197 198 ==== 199 INFO 200 ==== 201 202 If this column is blank, then the algorithm claims to have 203 found the solution to tolerance (i.e. INFO = 0). 204 This should be verified by checking the normalizedresidual. 205 206 Otherwise: 207 208 = 1: Convergence not achieved given the maximum number of iterations. 209 210 Input parameter errors: 211 212 = -1: matrix dimension N < 0 213 = -2: LDW < N 214 = -3: Maximum number of iterations <= 0. 215 = -4: For SOR: OMEGA not in interval (0,2) 216 For GMRES: LDW2 < 2*RESTRT 217 = -5: incorrect index request by uper level. 218 = -6: incorrect job code from upper level. 219 220 <= -10: Algorithm was terminated due to breakdown. 221 See algorithm documentation for details. 222 223 ==== 224 FLAG 225 ==== 226 227 X: Algorithm has reported convergence, but 228 approximate solution fails scaled 229 residual check. 230 231 ===== 232 NOTES 233 ===== 234 235 GMRES: For the symmetric test matrices, the restart parameter is 236 set to N. This should, theoretically, result in no restarting. For 237 nonsymmetric testing the restart parameter is set to N / 2. 238 239 Stationary methods: 240 241 - Since the residual norm ||b-Ax|| is not available as part of 242 the algorithm, the convergence criteria is different from the 243 nonstationary methods. Here we use 244 245 || X - X1 || / || X ||. 246 247 That is, we compare the current approximated solution with the 248 approximation from the previous step. 249 250 - Since Jacobi and SOR do not use preconditioning, 251 Jacobi is only iterated once per system, and SOR loops over 252 different values for OMEGA (the first time through OMEGA = 1, 253 i.e. the algorithm defaults to Gauss-Siedel). This explains the 254 different residual norms for SOR with the same matrix. 255 256