A Study On Fast Finding Algorithms For3-D Geometry Surface Discrete Elements

In order to solve the electromagnetic field problems in electrically large objects, somealgorithms have been developed including the method of moments (MoM), the Fast MultipoleMethod (FMM), the Multilevel Fast Multipole(MLFMA) etc.. The overall algorithmcomputational complexity is not only related to the performance of the calculation of solvingprocedure, but also to the arithmetic operations of pre-processing. The fast algorithm for findingthe common edges of adjacently quadrangles can be employed for the preprocessing of themoment method and the other fast algorithms for solving electromagnetic problems. The fastalgorithm is based on the concepts of the adjacency matrix and the incidence matrix in the graphtheory and the operations on sparse matrices for transpose and product. Thus the requirements ofstorage and computational time can be reduced.In this thesis, based on the algorithm for finding common edge of a pair of adjacenttriangular patches, the quadrilateral facets are employed to discrete the surface of thethree-dimensional geometry. Then, the two fast algorithms for finding the common edges ofquadrilateral elements can be obtained by the structured and unstructured fundamentalrelationships between nodes, edges and facets. The required time to find common edge is givenfor different cases of different common edge numbers. The computational complexity for findingthe common edges in the algorithm is linear. Then, the Roof-top functions are selected as basisfunctions and weight functions in the moment methodand the surface current coefficient ofobjects can be solved with the fast algorithm for finding the common edges. The bistatic RCSθθ and φφ of three-dimensional geometries are calculated. Finally, the RCS obtained fromquadrilateral surface element mesh and the those from triangular faces element mesh arecompared to verify the correctness of the proposed method. The results show that the fastalgorithms for finding the common edges in quadrilateral surface meshes are efficient for solvingelectromagnetic scattering and applicable to arbitrary shape geometry.