A parallel block Lanczos algorithm and its implementation for the evaluation of some eigenvalues of large sparse symmetric matrices on multicomputers

Mario Guarracino; Francesca Perla; Paolo Zanetti

International Journal of Applied Mathematics and Computer Science (2006)

  • Volume: 16, Issue: 2, page 241-249
  • ISSN: 1641-876X

Abstract

top
In the present work we describe HPEC (High Performance Eigenvalues Computation), a parallel software package for the evaluation of some eigenvalues of a large sparse symmetric matrix. It implements an efficient and portable Block Lanczos algorithm for distributed memory multicomputers. HPEC is based on basic linear algebra operations for sparse and dense matrices, some of which have been derived by ScaLAPACK library modules. Numerical experiments have been carried out to evaluate HPEC performance on a cluster of workstations with test matrices from Matrix Market and Higham's collections. A comparison with a PARPACK routine is also detailed. Finally, parallel performance is evaluated on random matrices, using standard parameters.

How to cite

top

Guarracino, Mario, Perla, Francesca, and Zanetti, Paolo. "A parallel block Lanczos algorithm and its implementation for the evaluation of some eigenvalues of large sparse symmetric matrices on multicomputers." International Journal of Applied Mathematics and Computer Science 16.2 (2006): 241-249. <http://eudml.org/doc/207789>.

@article{Guarracino2006,
abstract = {In the present work we describe HPEC (High Performance Eigenvalues Computation), a parallel software package for the evaluation of some eigenvalues of a large sparse symmetric matrix. It implements an efficient and portable Block Lanczos algorithm for distributed memory multicomputers. HPEC is based on basic linear algebra operations for sparse and dense matrices, some of which have been derived by ScaLAPACK library modules. Numerical experiments have been carried out to evaluate HPEC performance on a cluster of workstations with test matrices from Matrix Market and Higham's collections. A comparison with a PARPACK routine is also detailed. Finally, parallel performance is evaluated on random matrices, using standard parameters.},
author = {Guarracino, Mario, Perla, Francesca, Zanetti, Paolo},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {paralleleigensolver; cluster architecture; symmetric block Lanczos algorithm; sparse matrices; parallel eigensolver; Numerical experiments; comparison; performance; random matrices},
language = {eng},
number = {2},
pages = {241-249},
title = {A parallel block Lanczos algorithm and its implementation for the evaluation of some eigenvalues of large sparse symmetric matrices on multicomputers},
url = {http://eudml.org/doc/207789},
volume = {16},
year = {2006},
}

TY - JOUR
AU - Guarracino, Mario
AU - Perla, Francesca
AU - Zanetti, Paolo
TI - A parallel block Lanczos algorithm and its implementation for the evaluation of some eigenvalues of large sparse symmetric matrices on multicomputers
JO - International Journal of Applied Mathematics and Computer Science
PY - 2006
VL - 16
IS - 2
SP - 241
EP - 249
AB - In the present work we describe HPEC (High Performance Eigenvalues Computation), a parallel software package for the evaluation of some eigenvalues of a large sparse symmetric matrix. It implements an efficient and portable Block Lanczos algorithm for distributed memory multicomputers. HPEC is based on basic linear algebra operations for sparse and dense matrices, some of which have been derived by ScaLAPACK library modules. Numerical experiments have been carried out to evaluate HPEC performance on a cluster of workstations with test matrices from Matrix Market and Higham's collections. A comparison with a PARPACK routine is also detailed. Finally, parallel performance is evaluated on random matrices, using standard parameters.
LA - eng
KW - paralleleigensolver; cluster architecture; symmetric block Lanczos algorithm; sparse matrices; parallel eigensolver; Numerical experiments; comparison; performance; random matrices
UR - http://eudml.org/doc/207789
ER -

References

top
  1. Baglama J., Calvetti D. and Reichel L. Irbleigs (2003): A MATLAB program for computing a few eigenpairs of a large sparsei Hermitian matrix. - ACM TOMS, Vol. 29, No. 5, pp. 337-348. Zbl1070.65529
  2. Bai Z. (1994): Error analysis of the Lanczos algorithm for the nonsymmetric eigenvalues problem. - Math. Comp., Vol. 62, No. 205, pp. 209-226. Zbl0809.65029
  3. Boisvert R.F., Pozo R., Remington K., Barrett R. and Dongarra J. (1997): The Matrix Market: A web resource for test matrix collections, In: Quality of Numerical Software, Assessment and Enhancement (Ronald F. Boisvert, Ed.). - London: Chapman and Hall, pp. 125-137. 
  4. Choi J., Demmel J., Dhillon I., Dongarra J., Ostrouchov S., Petitet A., Stanley K., Walker D. and Whaley R.C., ScaLAPACK (1996): Aportable linear algebra library for distributed memory computers: Design and performance. - Comput. Phys. Comm., Vol. 97, No. 1-2, pp. 1-15. Zbl0926.65148
  5. Choi J., Dongarra J., Ostrouchov S., Petitet A., Walker D. and Whaley R.C. (1995): A proposal for a set of parallel basic linear algebra subprograms. - Tech. Rep. UT-CS-95-292, University of Tennessee, Knoxville. 
  6. Cline A.K., Golub G.H. and Platzman G.W. (1976): Calculationsof normal modes of oceans using a Lanczos method, In: Sparse Matrix Computations (J.R. Bunch and D.J. Rose, Eds.). - London: Academic Press. Zbl0358.65031
  7. Cullum J.K. and Willoughby R.A. (2002): Lanczos Algorithmsfor Large Symmetric Eigenvalue Computations, Vol.I: Theory. - Phildelphia: SIAM. Zbl1013.65033
  8. Dongarra J., Du Croz J., Hammarling S. and Duff I. (1990): A set of level 3 basic linear algebra subprograms. - ACMi Trans. Math. Software, Vol. 16, No. 1, pp. 1-17. Zbl0900.65115
  9. Dongarra J. and Whaley R.C. (1995): A user's guide to the BLACS v1.1. - Tech. Rep. UT-CS-95-281, University of Tennessee, Knoxville. 
  10. Filippone S. and Colajanni M. (2000): PSBLAS: A library for parallel linear algebra computation on sparse matrices. - ACM Trans. Math. Software, Vol. 26, No. 4, pp. 527-550. 
  11. Golub G.H. and Van Loan C.F. (1989): Matrix Computations, 2nd Ed. - Baltimore, MD: Johns Hopkins Univ. Press. Zbl0733.65016
  12. Gropp W., Lusk E. and Skjellum A. (1999): Using MPI - 2nd Edition: Portable Parallel Programming with the Message Passing Interface. - Cambridge, MA: MIT Press. 
  13. Guarracino M.R. and Perla F. (1994): A parallel block Lanczos algorithm for distributed memory architectures. - J.Par. Alg. Appl., Vol. 4, No. 1-2, pp. 211-221. Zbl1049.68899
  14. Guarracino M.R. and Perla F. (1995a): A parallel modified block Lanczos' algorithm for distributed memory architectures, In: Proc. Euromicro Workshop Parallel and Distributed Processing, San Remo, Italy, pp. 424-431. 
  15. Guarracino M.R. and Perla F. (1995b): A sparse, symmetric eigensolver for distributed memory architectures: Parallel implementation and numerical stability. - Tech. Rep. 11, Center for Research on Parallel Computing and Supercomputers, Naples, Italy. 
  16. Hernandez V., Roman J.E. and Vidal V. (2003): SLEPc: Scalable library for eigenvalue problem computations. - Lect. Notes Comput. Sci., Vol. 2565, pp. 377-391. Zbl1027.65504
  17. Higham N.J. (1995): The test matrix toolbox for MATLAB(version 3.0) - Tech. Rep. Vol. 276, Manchester Centre for Computational Mathematics. 
  18. Jones M.T. and Patrick M.L. (1989): The use of Lanczos's method to solve the large generalized symmetric definite eigenvalue problem. - Tech. Rep. ICASE89-67, Langley Research Center. 
  19. Lanczos C. (1950): An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. - J. Res. Nat. Bur. Stand., Vol. 45,No. 4, pp. 225-281. 
  20. Lehoucq R.B., Sorensen D.C. and Yang C. (1998): ARPACK Users' Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods. - Phildelphia: SIAM. Zbl0901.65021
  21. Paige C. (1976): Error analysis of the Lanczos algorithm for tridiagonalizing a symmetric matrix. - J. Inst. Math. Appl., Vol. 18, No. 3, pp. 341-349. Zbl0347.65018
  22. Parlett B.N. (1980): The Symmetric Eigenvalues Problem. - Englewood Cliffs, NJ: Prentice-Hall. Zbl0431.65017
  23. Parlett B.N. and Scott D.S. (1979): The Lanczos algorithm with selective orthogonalization. - Math. Comp., Vol. 33, No. 145, pp. 217-238. Zbl0405.65015
  24. Saad Y. (1992): Numerical Methods for Large Eigenvalues Problems. - Manchester: Manchester Univ. Press, Halsted Press. Zbl0991.65039
  25. Saad Y. and Malevsky A.V., P-SPARSLIB (1995): A portable library of distributed memory sparse iterative solvers, In: Proceedings of Parallel Computings Technologies (V.E. Malyshkin et. al., Eds.) (PaCT-95), 3rd International Conference, St.Petersburg. - Heidelberg: Springer. 
  26. Webster F. and Lo G. (1996): Projective block Lanczos algorithm for dense, Hermitianeigensystems. - J. Comput. Phys., Vol. 124, No. 1, pp. 146-161. Zbl0851.65021
  27. Wilkinson J.H. (1965): The Algebraic Eigenvalue Problem. - Oxford: Clarendon Press. Zbl0258.65037
  28. Wu K. and Simon H. (1999a): Parallel efficiency of the Lanczos method for eigenvalue problems. - Tech. Rep. LBNL-42828. 
  29. Wu K. and Simon H. (1999b): TRLAN user guide. - Tech. Rep. Lawrence Berkeley National Laboratory, LBNL-42953. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.