The filter algorithm for solving large-scale eigenproblems from accelerator simulations

One of the most important aspects in accelerator simulations is the accurate calculation of some low frequency electromagnetic fields within accelerator cavities, i.e., accurate eigensolutions of the frequency domain Maxwell's equations (FDME). Discretizations of FDME via edge-based finite element methods result in generalized matrix eigenproblems, K x = λ M x. In a typical accelerator simulation, the matrix size is usually large and the eigenvalues of interest are tightly clustered small interior eigenvalues out of a large-eigenvalue dominated spectrum. Developing an efficient algorithm for this type of eigenproblem is the primary goal of this thesis.; The Shift-Invert Lanczos method (SIL) is theoretically ideal for our eigenproblems. However, it requires accurate solutions of the shifted linear systems, which are often large and ill-conditioned. The computational difficulty associated with SIL is the key motivation for this thesis. We desire to develop an algorithm whose convergence properties are comparable to those of SIL but without demanding accurate solutions of any linear systems. In addition, the algorithm should be highly parallelizable.; We start our efforts by seeking a better understanding of SIL and other subspace methods. We introduce a filter model for general subspace methods; we show that, for our eigenproblems, even though the shifted linear systems are solved only approximately, an efficient band-pass filter is achieved. Based on the band-pass filter, we propose an Inexact Shift-Invert Lanczos method (ISIL) that efficiently obtains good eigenvector approximations. We then propose an inexact Newton-type method to refine the eigenvector approximations to the desired accuracy. We develop an eigenspectrum error analysis approach to study approximate solutions from iterative linear solvers. In particular, we unveil an important property of certain linear systems: Property G. We propose the complete filter algorithm that optimally combines ISIL and the inexact Newton-type method.; The software implementation of the filter algorithm exhibits desirable parallel performance that scales up to hundreds of processors. We discuss important parallel implementation issues of the algorithm.; The filter algorithm and its parallel implementation have already proved valuable to accelerator designs. We provide some accelerator applications of the algorithm.