Efficient Solution of Linear Systems with Multiple Right-Hand Sides

November 12, 2003
2:50pm - 4:00pm
Halligan 111

Abstract

In many applications one desires the solution of multiple linear systems involving the same NxN coefficient matrix but K different right-hand sides, all of which are available simultaneously. Such problems arise, for instance, in the numerical solution of frequency-domain electromagnetic scattering, where the right-hand sides might correspond to different incident fields over the scatterer.

In this work we consider the simultaneous solution of large, linear systems with multiple right-hand sides where the matrix is not necessarily Hermitian. Assuming matrix-vector products can be done quickly, each system is a good candidate for solution by Krylov-subspace solvers. However, this naive approach of treating each system separately does not exploit any underlying relationship among the right-hand sides. We describe single-seed and block-seed projection approaches that do exploit such relationships. These methods are based on the QMR and block QMR algorithms, respectively. We use (block) QMR to solve the (block) seed system and generate the relevant biorthogonal subspaces. Approximate solutions to the non-seed systems are simultaneously generated by minimizing their appropriately projected (block) residuals. Algorithmic details are discussed and memory advantages of the block-seed algorithm in serial and parallel environments are noted. The computational savings of our methods over using either QMR to solve each system individually or using stand-alone block QMR is illustrated in examples.