Overview

This WEB site provides a parallel implementation of an optimization method, called DACG (Deflation-Accelerated Conjugate Gradient).

DACG sequentially computes a number of the smallest eigenpairs of the generalized problem

Ax = c Bx,

A, B being NxN symmetric positive definite (SPD) matrices, by CG minimizations of the Rayleigh quotient over subspaces of decreasing size.

Our PDACG code is intended for giving a ready-to-use tool for computing a number of the smallest eigenpairs of a large, sparse SPD matrix.

Key features of our code are:

Robustness. Our code was tested on Finite Element (FE), Mixed Finite Element (MFE), and Finite Difference (FD) matrices, converging in all problems.
Applicability to large sparse matrices. Though available packages like ARPACK [15] and PRISM [9] are intended also for large problems, they are usually difficult to apply to very large (N > 100,000, say) ones. Our code was tested with matrices up to size N = 268,000, on a T3E machine with 256 MB RAM nodes.
Ready-to-use. Our code do not need any matrix-vector routine or other complementary code, like does the package documented in [15].

Acknowledgements

This work has been supported by the Italian MURST Project "Analisi Numerica: Metodi e Software Matematico". Free accounting units on the T3E Supercomputer were given by CINECA.

Bibliography

[1] M. Benzi, C. D. Meyer, and M. Tuma. A sparse approximate inverse preconditioner for the conjugate gradient method. SIAM J. Sci. Comput., 17(5):1135-1149, 1996.
[2] L. Bergamaschi, G. Gambolati, and G. Pini. Spectral analysis of large finite element problems by optimization methods. J. Shock and Vibr., 1(6):529-540, 1994.
[3] L. Bergamaschi, G. Gambolati, and G. Pini. Asymptotic convergence of conjugate gradient methods for the partial symmetric eigenproblem. Numer. Lin. Alg. Appl., 4(2):69-84, 1997.
[4] L. Bergamaschi, G. Gambolati, G. Pini, and M. Putti. Gradient eigenanalysis on nested finite elements. Adv. Eng. Soft. Comp. Sys. Eng., 27:155-165, 1996.
[5] L. Bergamaschi, G. Pini, and F. Sartoretto. Approximate inverse preconditioning in the parallel solution of sparse eigenproblems. Numer. Lin. Alg. Appl., 7(3):99-116, 2000.
[6] L. Bergamaschi, G. Pini, and F. Sartoretto. Factorized approximate inverse precon- ditioning of a sparse eigensolver. In E. H. Hollander, G. R. Joubert, F. J. Peters, and H. J. Sips, editors, Parallel Computing. Fundamentals & Applications, pages 267-274, London, UK, 2000. Imperial College Press.
[7] L. Bergamaschi, G. Pini, and F. Sartoretto. Parallel preconditioning of a sparse eigensolver. Journal of Parallel Computing, 2000. To appear.
[8] L. Bergamaschi and M. Putti. Efficient parallelization of preconditioned conjugate gradient schemes for matrices arising from discretizations of diffusion equations. In Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Com- puting, March, 1999. (CD-ROM).
[9] C. Bischof, W. L. George, S. Huss-Lederman, A. Tsao, T. Turnbull, R. van de Geijn, and Y.-J. Jason Wu. PRISM project, parallel symmetric eigen- solver. WEB "http://www-fp.mcs.anl.gov:80/ CCST/research/reports_pre1998/ al- gorithm_development/ prism/prism.html", July 7, 2000.
[10] G. Gambolati, G. Pini, and M. Putti. Nested iterations for symmetric eigenproblems. SIAM J. Sci. Comput., 16(1):173-192, 1995.
[11] G. Gambolati, G. Pini, and F. Sartoretto. Solution to large symmetric eigenproblems by an accelerated conjugate gradient technique. Environmental Software, 1(1):31-39, 1986.
[12] G. Gambolati, G. Pini, and F. Sartoretto. An improved iterative optimization tech- nique for the leftmost eigenpairs of large symmetric matrices. J. Comp. Phys., 74:41- 60, 1988.
[13] G. Gambolati, F. Sartoretto, and P. Florian. An orthogonal accelerated deflation technique for large symmetric eigenproblems. Comp. Methods App. Mech. Eng., 94:13- 23, 1992.
[14] L. Y. Kolotilina and A. Y. Yeremin. Factorized sparse approximate inverse precondi- tioning I. Theory. SIAM J. Matrix Anal. Appl., 14:45-58, 1993.
[15] K. J. Maschhoff and D. C. Sorensen. A portable implementation of ARPACK for distributed memory parallel architectures. In Proceedings of the Copper Mountain Conference on Iterative Methods, volume 1, April 9-13 1996.
[16] National Institute of Standards and Technology. Matrix Market. WEB "http://math.nist.gov/MatrixMarket", July 17, 2000.
[17] P. Pacheco. Parallel Programming with MPI. Morgan Kaufmann, San Francisco, 1997.
[18] G. Pini. Computation of minimum eigenvalue through minimization of Rayleigh's quotient for large sparse matrices using vector computers. Int. J. Computer Math., 36:89-99, 1990.
[19] G. Pini. A parallel algorithm for the partial eigensolution of sparse symmetric matrices on the CRAY Y/MP. Parallel Computing, 17:553-562, 1991.
[20] G. Pini. Parallel evaluation of leftmost eigenpairs of large unsymmetric matrices. Num. Meth. PDE, 10:533-544, 1994.
[21] G. Pini and F. Sartoretto. Vector and parallel codes for large sparse eigenproblems. Supercomputer, 50:29-39, 1992.
[22] Y. Saad. Iterative Methods for Sparse Linear Systems. PWS Publishing Company, Boston, MA, 1996.
[23] F. Sartoretto, G. Pini, and G. Gambolati. Accelerated simultaneous iterations for large finite element eigenproblems. J. Comp. Phys., 81:53-69, 1989.