1 Iterative solvers

Since the coefficient matrix in (2) is dense, the arithmetic complexity for Gaussian elimination grows cubically in N (the number of cells). For large values of N, this arithmetic cost becomes prohibitively high. A possible remedy is to use a rapidly convergent iterative method instead, where the arithmetic complexity might be as low as O(N^{2}). Thus, there is a potential to reduce the arithmetic work by an order of magnitude in N.

1.1 Krylov subspace methods

The state of the art for iterative solution of linear systems is to employ some Krylov subspace method [1]. For simplicity and robustness, we advocate the restarted generalized minimal residual (GMRES(ℓ)) algorithm [3], where ℓ is the restarting length. Within the current project, a serial version of restarted GMRES has been thoroughly implemented (by K. Otto and B. L. Andersson) in Fortran 90.

1.2 Preconditioning

In order to achieve an acceptable rate of convergence and, more importantly, a short total execution time, it is crucial to construct an effective, parallelizable preconditioner. For the type of systems that we are considering, standard preconditioning techniques like incomplete LU factorizations are likely to perform poorly. A viable alternative is to use preconditioners based on sparse approximate inverses [2], the construction of which are inherently parallel. Furthermore, they are possible to tune by sharpening a tolerance ε.

References

[1] R. W. Freund, G. H. Golub, and N. M. Nachtigal, Iterative solution of linear systems, Acta Numer., 1 (1992), pp. 57–100.

[2] M. J. Grote and T. Huckle, Parallel preconditioning with sparse approximate inverses, SIAM J. Sci. Comput., 18 (1997), pp. 838–853.

[3] Y. Saad and M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7 (1986), pp. 856–869.