Using parallel banded linear system solvers in generalized eigenvalue problems (Q1334518)

This paper discusses a method of subspace iteration for the positive definite banded symmetric generalized eigenproblem. The authors begin by extending two parallel tridiagonal solvers, the parallel partition LU (PPT) and parallel diagonally dominant (PDD) algorithms, to banded systems. The PPT algorithm performs well for narrow bands with a small number of processors while the PDD algorithm is more efficient if the off-diagonal blocks are small. Each requires solution of a reduced linear system, causing a computational and communication bottleneck. The main algorithm described is a parallel subspace iteration for finding the \(q\) \((\ll n)\) smallest eigenvalues of the symmetric eigenproblem \(Ax= \lambda Bx\), with \(B\) positive definite. Assuming the matrix pencil \((A,B)\) is positive definite (it can be made so if necessary using a shift \(s\)) the basic subspace algorithm first selects a starting subspace of dimension \(>q\) and then uses the Rayleigh-Ritz procedure to extract \(q\) eigenvalue and vector approximations. The authors' parallel version of this is then given. The algorithm incorporates the shift \(s\) to decompose the banded system into relatively independent subsystems and a detailed optimal shift selection strategy is described. The paper concludes with numerical examples of execution times of the parallel subspace iterations for a range of examples and number of processors.