Parallel algorithms for electromagnetic moment method formulations

[摘要] ENGLISH ABSTRACT:This dissertation investigates the moment method solution of electromagneticradiation and scattering problems using parallel computers. In particular,electromagnetically large problems with arbitrary geometries are considered.Such problems require a large number of unknowns to obtain adequate approximatesolutions, and make great computational demands. This dissertationconsiders in detail the efficient exploitation of the potential offered byparallel computers for solving such problems, and in particular the class oflocal memory Multiple Instruction, Multiple Data systems.A brief history of parallel computing is presented. Methods for quantifyingthe efficiency of parallel algorithms are reviewed. The use of pseudo-codefor documenting algorithms is discussed and a pseudo-code notation is definedthat is used in later chapters.A new parallel conjugate gradient algorithm, suitable for the solutionof general systems of linear equations with complex values, is presented.A method is described to handle efficiently the Hermitian transpose of thematrix required by the algorithm. Careful attention is paid to the theoreticalanalysis of the algorithm's parallel properties (in particular, speed-up andefficiency). Pseudo-code is presented for the algorithms. Timing results for amoment method code, running on a transputer array and using this conjugategradient solver, are presented and compared to the theoretical predictions.A parallel LU algorithm is described and documented in pseudo-code. Anew graphical description of the algorithm is presented that simplifies theidentification of the parallelism and the analysis of the algorithm. The useof formal methods for extracting parallelism via the use of invariants is presentedand new examples given. The speed-up and efficiency of the algorithmare analyzed theoretically, using new methods that are simpler than those describedin the literature. Techniques for optimizing the efficiency of parallelalgorithms are introduced, and illustrated with pseudo-code. New parallelforward and backward substitution algorithms using the data distributionrequired for the parallel LV algorithm are described, and documented withpseudo-code. Results obtained with a Occam 2 moment method code runningon a transputer array using these parallel LU solver and substitutionalgorithms are presented and compared with the theoretical predictions.PARNEC, a new Occam 2 implementation of the thin-wire core of NEC2,is discussed. The basic 'theory of NEC2 is reviewed. Problems with early attemptsat combining Occam and FORTRAN are reported. Methodologiesfor re-coding an old code written in an unstructured language in a. modernstructured language are discussed. Methods of parallelizing the matrix generationare discussed. The accuracy of large moment method formulationsis investigated, as is the effect of machine precision on the solutions. The use of the biconjugate gradient method to accelerate convergence is brieflyconsidered and rejected. The increased size of problem that can be handledby PARNEC, running on a transputer array, is demonstrated.Conclusions are dra.wn regarding the contributions of this dissertation tothe development of efficient parallel electromagnetic moment method algorithms.

[发布机构] Stellenbosch University