Solutions of large linear systems arising from ODEs and PDEs

Parallel preconditioning techniques for the solution of linear systems arising from fluid dynamics problems
Pierluigi Amodio & Aldo Bonfiglioli
(Dipartimento di Matematica, Università di Bari, Italy)

We analyze the solution of sparse linear systems arising from the discretization of CFD (Computational Fluid Dynamics) problems simulating both compressible and incompressible flows. The coefficient matrix of the linear system has a symmetric sparsity structure, and each element is a square block of fixed size (from 1 to 4) which contains information as velocity, pressure, etc.

The number of nonzero blocks per rows depends on the position of the discretized element in the domain, but it is less or equal to 7. Moreover, after a suitable reordering, the coefficient matrix has a band structure with a small bandwidth.

For the solution of the above system it is necessary to consider an iterative method (for example GMRES) with a proper preconditionings. We analyze parallel preconditionings known as Additive Schwarz methods which are among the most used for CFD problems.

In such methods the original domain is divided in subdomains which are elaborated by different processors, but the boundaries of each subdomain are overlapped among the processors in order to speed the convergence.

After an overview about the properties of such algorithms, we analyze a new preconditioning which increases the convergence rate of the iterative method and reduces the number of communications among the processors.

Title Preconditioning of iterative eigensolvers
Luca Bergamaschi & G. Gambolati& G. Pini & M. Putti & F. Sartoretto
(Dipartimento di Metodi e Modelli Matematici per le Scienze Applicate, Università di Padova, Italy)

The Jacobi-Davidson method (JD) has been recently proposed [5] to find a number of eigenpairs close to a prescribed value.

In this communication we present a comparison [3] of this method with ARPACK [4] and the DACG method [1] in the solution of large sparse spd eigenproblems arising from discretization of the diffusion equation. In particular, we analyze the role of preconditioning in the solution of the indefinite system of the form (A - *I)x = b which is required at every step of the Jacobi-Davidson iteration [2]. Numerical tests show the high sensitivity of JD to preconditioning.

We parallelized the preconditioned JD obtaining an appreciable degree of parallelism when using both the Jacobi and AINV preconditioners, the latter revealing, on the average, more robust and efficient.

References

[1]

L. Bergamaschi, G. Gambolati, and G. Pini, Asymptotic convergence of conjugate gradient methods for the partial symmetric eigenproblem, Numer. Lin. Alg. Appl., 4 (1997), pp. 69-84.

[2]

L. Bergamaschi, G. Pini, and F. Sartoretto, Designing a parallel Jacobi Davidson method for large sparse matrices, (2001). Submitted.

[3]

L. Bergamaschi and M. Putti, Numerical comparison of iterative methods for the eigensolution of large sparse symmetric matrices, (2001). (submitted).

[4]

R. B. Lehoucq, D. C. Sorensen, and C. Yang, ARPACK Users Guide. Solution of Large Scale Eigenvalue Problem with Implicit Restarted Arnoldi Methods, SIAM, 1998.

[5]

G. L. G. Sleijpen and H. A. van der Vorst, A Jacobi-Davidson method for linear eigenvalue problems, SIAM J. Matrix Anal. Appl., 17 (1996), pp. 401-425.

On the Convergence of Krylov Linear Equation Solvers
M.T. Vespucci & C.G. Broyden
(University of Bergamo, Italy)

In this paper we show that the reduction in residual norm at each iteration of CG and GMRES is related to the first column of the inverse of an upper Hessenberg matrix that is obtained from the original coefficient matrix by way of an orthogonal transformation. The orthogonal transformation itself is uniquely defined by the coefficient matrix of the equations and the initial vector of residuals. We then apply this analysis to MINRES and show that, under certain circumstances, this algorithm can exhibit an unusual (and very slow) type of convergence that we refer to as QTRoscillatory convergence.