Using parallel banded linear system solvers in generalized eigenvalue problems

DOI10.1016/0167-8191(94)90070-1MaRDI QIDQ1334518zbMATH OpenOpenAlexFDO

Authors Hong Zhang, William F. Moss

Publication date 25 September 1994

Published in Parallel Computing (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2060/19940017111

zbMATH Keywords

banded systemdiagonally dominant algorithmdistributed memoryeigenvaluesgeneralized eigenproblemmethod of subspace iterationmultiprocessornumerical examplesoptimal shift selection strategyparallel computationpartition LU algorithm

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Computational methods for sparse matrices (65F50) Parallel numerical computation (65Y05)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 434535
• Parallel block Jacobi-Davidson method for solving large generalized eigenvalue problems and its application
• scientific article; zbMATH DE number 833717
• scientific article; zbMATH DE number 822157
• scientific article; zbMATH DE number 741162

Cited in

(7)

• A new alternating group explicit-implicit algorithm with high accuracy for dispersive equation
• A difference scheme with intrinsic parallelism for fractional diffusion-wave equation with damping
• Parallel difference schemes with interface extrapolation terms for quasi-linear parabolic systems
• scientific article; zbMATH DE number 434535 (Why is no real title available?)
• Parallel iterative methods for parabolic equations
• Unconditional stability of parallel difference schemes with variable time steplengths for heat equations^∗
• Alternating segment explicit-implicit scheme for nonlinear third-order KdV equation

This page was built for publication: Using parallel banded linear system solvers in generalized eigenvalue problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1334518)