Multiple Solutions to Dense Systems in Radar Scattering using a Preconditioned Block GMRES Solver

	William E. Boyse
	Advanced Software Resources, Inc.
	3375 Scott Boulevard, Suite 420
	Santa Clara, CA 95054
	(415) 328-5271
	Boyse@netcom.com

	Special Topic:	Linear Systems with Multiple Right-hand Sides

Multiple right-hand sides occur in radar scattering calculations in
the computation of the simulated radar return from a body at a large
number of angles.  Each desired angle requires a right-hand side
vector to be computed and the solution generated.  These right-hand
sides are naturally smooth functions of the angle parameters and this
property is utilized in a novel way to compute solutions an order of
magnitude faster than LINPACK.  

The modeling technique addressed is the Method of Moments (MOM), i.e a
boundary element method for time harmonic Maxwell's equations.
Discretization by this method produces general complex dense systems
of rank 100's to 100,000's.  The usual way to produce the required
multiple solutions is via LU factorization and solution routines such
as found in LINPACK.  

Our method uses the block GMRES iterative method to directly iterate a
subset of the desired solutions to convergence.  The computed Krylov
sub-space is then used to approximate solutions to the remaining
right-hand sides.  We use the property that the right-hand sides are
smooth functions of angle to select the subset of right-hand sides to
directly iterate that will provide for optimal solution times.  

The convergence rate of the GMRES algorithm is enhanced both by the
block algorithm and by preconditioning the system with a sparse
incomplete LU factorization generated by an ILU(T) algorithm with
partial pivoting.  This "drop tolerance" algorithm permits adjustment
of the completeness of the preconditioner and guidelines are shown for
choosing the most beneficial completeness percentage.  

This algorithm is analyzed on a realistic MOM matrix problem of rank
3,400 to determine the parameters for efficient operation.  The error
in computed RCS values, the equation residual error and solution error
are all used in this analysis.  A method, based on Nyquist sampling
theory, is shown to predict an optimal method of choosing the angles
to directly iterate such that the total solution process is most
efficient.  It is shown in this case that the solver runs nearly an
order of magnitude faster than single precision LINPACK.