DOC PREVIEW
primme

This preview shows page 1-2-17-18-19-35-36 out of 36 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Technical Report WM-CS-2006-08College ofWilliam & MaryDepartment of Computer ScienceWM-CS-2006-08PRIMME: PReconditioned Iterative MultiMethod Eigensolver:Methods and software descriptionAndreas StathopoulosNovember 2006PRIMME: PRECONDITIONED ITERATIVE MULTIMETHOD EIGENSOLVER:METHODS AND SOFTWARE DESCRIPTION∗ANDREAS STATHOPOULOS†AND JAMES R. MCCOMBS†Abstract. This paper describes the PRIMME software package for the solving large, sparse Hermitian and realsymmetric eigenvalue problems. The difficulty and importance of these problems have increased over the years,necessitating the use of preconditioning and near optimally converging iterative methods. On the other hand, thecomplexity of tuning or even using such methods has kept them outside the reach of many users. Responding to thisproblem, our goal was to develop a general purpose software that requires minimal or no tuning, yet it provides thebest possible robustness and efficiency. PRIMME is a comprehensive package that brings state-of-the-art methodsfrom “bleeding edge” to production, with a flexible, yet highly usable interface. We review the theory that givesrise to the near optimal methods GD+k and JDQMR, and present the various algorithms that constitute the basis ofPRIMME. We also describe the software implementation, interface, and provide some sample experimental results.1. Introduction. PRIMME, or PReconditioned Iterative Multi-Method Eigensolver, isa software package for the solution of large, sparse Hermitian and real symmetric eigenvalueproblems. We view PRIMME as a significant step toward an “industrial strength” eigenvaluecode for large, difficult eigenproblems, where it is not possible to factorize the matrix, andusers can only apply the matrix operator, and possibly a preconditioning operator, on vectors.If the matrix can be factorized, the shift-invert Lanczos code by Grimes, Lewis, andSimon has set a high standard for robustness [31]. However, even in factorizable cases,the factorization and back-substitutions can be very expensive, and a Lanczos method or amethod that uses preconditioning can be more efficient, especially for extreme eigenvalues.On the other end, if only matrix-vector multiplication is available, the software ARPACKby Lehoucq, Sorensen, and Yang has set the standard for good quality code that is easyto use with very little parameter tuning [44]. Yet, the implicitly restarted Lanczos method[64], on which ARPACK is based, does not converge optimally, and it cannot directly usepreconditioning,which is required for verydifficult problems. The range of problems targetedby PRIMME is between the easy ones and the ones that must, and can be factorized. Asproblem sizes in applications continue to grow, so does PRIMME’s target range.Based on both research and integration, PRIMME’s design philosophy is1. to provide preconditioned eigenvalue methods that converge near optimally underlimited memory2. to provide the maximum robustness possible without matrix factorization,3. to provide flexibility in mixing and matching among most currently known features,4. to achieve efficiency at all architectural levels, and5. to achieve all the above with a friendly user interface that requires no parametersetting from end-users, but allows full experimentation by experts.This paper is organized as follows: In section 2 we describe the problem, its importance anddifficulty, and discuss the advantages and shortcomings of other current eigenvalue software.In section 3 we present the main algorithmic framework for PRIMME, including the two nearoptimal methods, GD+k and JDQMR. We also discuss how a host of other algorithms can beparameterized within this framework. In section 4 we discuss how the PRIMME softwaremeets its design goals. In section 5 we present sample comparisons with other state-of-the-art software. We conclude in section 6 with some discussion on on-going work and futureextensions to PRIMME.∗Work supported partially by National Science Foundation grants: ITR/DMR 0325218, ITR/AP-0112727,ITR/ACS-0082094.†Department of Computer Science, College of William and Mary, Williamsburg, Virginia 23187-8795,(andreas,[email protected]).2PRIMME 3PRIMME implements a multitude of features, algorithms, techniques, and heuristics thathave emerged in research papers and software by this and other groups over many years.When their description is beyond the scope of this paper,we refer to the appropriate literature.2. A difficult problem and current approaches. Given a real symmetric, or com-plex Hermitian matrix A of dimension N, we consider the problem of seeking numEvalssmallest, largest or interior eigenvalues λi, and their corresponding eigenvectors xi, i =1,.. .,numEvals. The numerical solution of this problem when A is large and sparse is one ofthe most computationally intensive tasks in a variety of applications.One such application is structural engineering, where finite element models are used toperform vibrational and buckling analysis [31]. Electromagnetics is another area that dependson the solution of large, real symmetric eigenproblems [26, 37]. A particular demandingapplication comes from lattice Quantum Chromodynamics (QCD) where the pseudo-inverseof a very large Hermitian operator is approximated on the space of several of its smallesteigenpairs [22]. Recently, electronic structure applications from atomic scale physics [20]to molecular scale materials science [11] and nanotechnology, with symmetric and hermitianeigenproblems at their core, have been rivaling QCD as the top supercomputer cycle user.The challenge is twofold; First, the matrix size, N, in these applications is routinely morethan a million, while an order of a billion has also been tried [54]. Second, many applications,especially in electronic structure calculations, require the computation of hundreds or eventhousands of extreme eigenpairs. Often the number of required eigenpairs, numEvals, isdescribed as a small percentage of the problem size. In such cases, orthogonalization ofnumEvals vectors, an O(numEvals2N) task, becomes O(N3), making the scaling to largerproblem sizes practically infeasible.Iterative methods are the only means of addressing these large problems. Yet, iterativemethods may converge slowly, especially as the problem size grows. As with linear systems,preconditioning can be used to speed up convergence, but theoretical understanding of how itshould be used in eigenvalue methods has only started to


primme

Download primme
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view primme and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view primme 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?