Theses supervised by Prof. Dr. Levent Gürel
10 theses · İhsan Doğramacı Bilkent University
Monostatik radar kesit alan problemlerinin çöz ümlerinin tekrar sıkıştırılmış yaklaşık adaptif çapraz algoritmasıyla hızlandırılması
We developed a method that incorporates an algebraic compression technique to accelerate the computation of multiple monostatic radar cross sections (RCSs) of arbitrary 3-D geometries. Since most radars rely on the backscattering from a target, computing the monostatic RCS (MRCS) is needed more often than the bistatic RCS. Computation of each MRCS value requires a separate solution, which may be costly depending on the size of the problem. The task becomes considerably harder when the goal is to compute multiple MRCS values with high angular resolution. The proposed technique compresses the excitation matrix using the adaptive cross approximation (ACA) algorithm in the first step. A recompression is applied on the matrices obtained from ACA by utilizing the QR decomposition and computing the singular value decomposition in an efficient manner. The solution of each excitation is accelerated by the multilevel fast multipole algorithm. The numerical results demonstrate the efficiency and accuracy of our proposed method.
Yüksek ve alçak elektromanyetik saçınım sonuçlarının matris kalem yöntemi ile birleştirilerek dış değerlemesi
Accurate frequency domain solutions of electromagnetic scattering problems areknown to require high computing resources as the solution frequency increases.On the other hand, high-frequency techniques provide us solutions with limitedaccuracy in the relatively high-frequency regions. In this thesis we aimed to ï¬llthe intermediate gap by using extrapolation techniques. Matrix pencil method(MPM) is presented to ï¬nd the parameters of the model in our model-based ex-trapolation approach. In order to fully incorporate the two separate availabledata sources, i.e., accurate low-frequency solvers and asymptotic high-frequencysolvers, we proposed two methods of coupling, namely coupled MPM and cou-pled deconvolution MPM. Results of proposed extrapolation methods are testedboth on analytically generated backscattering solution of conducting sphere andnumerical solutions of various three dimensional bodies.Keywords: Extrapolation, Matrix pencil method, Coupled extrapolation, RCS,COMPM, CDMPM.iv
Elektromanyetik hesaplamaları için paralel donanım ve yazılım uygulamaları
C¸ ok seviyeli hızlı cok kutup y¨otemi (C¸ SHC¸ Y) frekans alanında hassas sonu¸clar veren bir elektromanyetik ¸c¨oz¨uc¨us¨ud¨ur; bu ¸c¨oz¨uc¨u hesapsal karma¸sıklı˘gı ve bellek gereksinimi olduk¸ca azaltmı¸stır. C¸ SHC¸ Y'nin t¨um bu yararlarına kar¸sın, tek i¸slemcili bilgisayarların donanım kaynakları, ¨orne˘gin bellek miktarı ve i¸slemci hızı, ¸c¨oz¨ulebilen elektromanyetik problemlerin b¨uy¨ukl¨u˘g¨un¨u kısıtlamaktadır. Tek i¸slemcili sistemlerin bu kısıtlamalarını a¸sabilmek i¸cin, C¸ SHC¸ Y'nin paralelle¸stirilmesi ¨onerilmi¸stir. C¸ SHC¸ Y'nin paralelle¸stirilmesi kolay bir i¸slem de˘gildir, bu i¸slemin yapılabilmesi i¸cin paralel donanım ve yazılım alanında yo˘gun emek ve deneyim gerekmektedir. Elektromanyetik problemleri paralel ortamda ¸c¨ozebilmek icin kendi paralel bilgisayar k¨umemizi kurduk ve C¸ SHC¸ Y kodumuzu paralelle¸stirdik. Paralel bilgisayarlar ¨uzerindeki i¸s y¨uk¨un¨u ve bellek kullanımını dengeleyen verimli y¨uk dengeleme algoritmalarını ve y¨ontemlerini paralel kodumuza yerle¸stirdik. S¸u anda, paralel C¸ SHC¸ Y ¸c¨oz¨uc¨um¨uzle geli¸sig¨uzel ¸sekilli ¸cok b¨uy¨uk elektromanyetik problemleri paralel bilgisayar k¨umeleri ¨uzerinde ¸cok kısa bir zamanda ¸c¨ozebilmekteyiz.
Saçılım problemlerinin çözümü için belleğin verimli kullanıldığı çok seviyeli fiziksel optik algoritması
For the computation of electromagnetic scattering from electrically large targets, physical optics (PO) technique can provide approximate but very fast solutions. Moreover, higher order approximations, such as physical theory of diffraction (PTD) including the diffraction from the edges or sharp corners can also be added to the PO solution in order to enhance the accuracy of the PO. On the other hand, in real-life radar applications, where the computation of the scattering pattern over a range of frequencies and/or angles with sufficient number of samples is desired, further acceleration may be needed. Multilevel physical optics (MLPO) algorithm can be used for such applications, in which a remarkable speed-up can be achieved by evaluating the PO integral in a multilevel fashion. As the correction terms like PTD are evaluated independently just on the edges or sharp corners, whereas the PO integration is carried out on the entire target surface, PO integration is the dominant factor in the computational time of such higher order approximations. Therefore accelerating the PO integration will also reduce the computational time of such higher order approximations. In this thesis, we propose two different improvements on the MLPO algorithm. iii First improvement is the modification of the algorithm that enables the solution of the scattering problems involving nonuniform triangulations, thus decreasing the CPU time. Second improvement is the memory-efficient version, in which the O (N3) memory requirement is decreased to O (N2 logN). Efficiency of the two proposed improvements are demonstrated in numerical examples including a reallife scattering problem, with which the scattering pattern of a three-dimensional stealth target is evaluated as a function of elevation angle, azimuth angle, and frequency. Keywords: Physical optics; scattering problems; multilevel physical optics algorithm.
Elektromanyetik problemlerin çok seviyeli hızlı çokkutup yöntemiyle doğru ve verimli çözümleri
The multilevel fast multipole algorithm (MLFMA) is a powerful method for thefast and efficient solution of electromagnetics problems discretized with large numbers of unknowns. This method reduces the complexity of matrix-vector multiplications required by iterative solvers and enables the solution of large-scale problems that cannot be investigated by using traditional methods. On the other hand, efficiency and accuracy of solutions via MLFMA depend on many parameters, such as the integral-equation formulation, discretization, iterative solver, preconditioning, computing platform, parallelization, and many other details of the numerical implementation. This dissertation is based on our efforts to develop sophisticated implementations of MLFMA for the solution of real-life scattering and radiation problems involving three-dimensional complicated objects with arbitrary geometries.
Büyük ölçekli yüzey integral denklemi problemlerinin iteratif çözümleri için etkin öniyileştiriciler
A popular method to study electromagnetic scattering and radiation of threedimensionalelectromagnetics problems is to solve discretized surface integralequations, which give rise to dense linear systems. Iterative solution of suchlinear systems using Krylov subspace iterative methods and the multilevel fastmultipole algorithm (MLFMA) has been a very attractive approach for largeproblems because of the reduced complexity of the solution. This scheme workswell, however, only if the number of iterations required for convergence of theiterative solver is not too high. Unfortunately, this is not the case for manypractical problems. In particular, discretizations of open-surface problems andcomplex real-life targets yield ill-conditioned linear systems. The iterative solutionsof such problems are not tractable without preconditioners, which can beroughly defined as easily invertible approximations of the system matrices.In this dissertation, we present our efforts to design effective preconditioners forlarge-scale surface-integral-equation problems. We first address incomplete LU(ILU) preconditioning, which is the most commonly used and well-establishedpreconditioning method. We show how to use these preconditioners in a blackboxform and safe manner. Despite their important advantages, ILU preconditionersare inherently sequential. Hence, for parallel solutions, a sparseapproximate-inverse (SAI) preconditioner has been developed. We propose anovel load-balancing scheme for SAI, which is crucial for parallel scalability.Then, we improve the performance of the SAI preconditioner by using it for theiterative solution of the near-field matrix system, which is used to preconditionthe dense linear system in an inner-outer solution scheme. The last preconditionerwe develop for perfectly-electric-conductor (PEC) problems uses the sameinner-outer solution scheme, but employs an approximate version of MLFMA forinner solutions. In this way, we succeed to solve many complex real-life problemsincluding helicopters and metamaterial structures with moderate iteration countsand short solution times. Finally, we consider preconditioning of linear systemsobtained from the discretization of dielectric problems. Unlike the PEC case,those linear systems are in a partitioned structure. We exploit the partitionedstructure for preconditioning by employing Schur complement reduction. In thisway, we develop effective preconditioners, which render the solution of difficultreal-life problems solvable, such as dielectric photonic crystals.
Elektromanyetik saçılım problemlerinin lokal olarak düzeltilmiş nytsröm yöntemiyle çözümü
The locally corrected Nystr¨om (LCN) method is used to solve integral equationswith high accuracy and efficiency. Unlike commonly used methods, the LCNmethod employs high-order basis functions on high-order surfaces. Hence, thenumber of unknowns in the electromagnetic problem decreases substantially, thisalso reduces the total solution time of the problem. In this thesis, electromagneticscattering problems for arbitrary, three-dimensional, and conducting geometriesare solved with the LCN method. Both the electric-field integral equation (EFIE)and the magnetic-field integral equation (MFIE) are implemented. The solutiontime for Duffy integrals is reduced significantly by modifying the Duffy transform.Then, mixed-order basis functions are implemented to accurately represent thecharge density for EFIE. Finally, both the accuracy and the efficiency (in termsof solutions times and the number of unknowns) of the LCN method are comparedwith the method of moments and the multilevel fast multipole algorithm.
Elektromanyetik problemlerin eşdeğerlik prensibi yöntemiyle çözümleri
A domain decomposition scheme based on the equivalence principle for integral equations is studied. This thesis discusses the application of the equivalence principle algorithm (EPA) in solving electromagnetics scattering problems by multiple three-dimensional perfect electric conductor (PEC) objects of arbitraryshapes. The main advantage of EPA is to improve the condition number of the system matrix. This is very important when the matrix equation is solved iteratively, e.g., with Krylov subspace methods. EPA starts solving electromagnetics problems by separating a large complex structure into basic parts, which mayconsist of one or more objects with arbitrary shapes. Each one is enclosed by an equivalence surface (ES). Then, the surface equivalence principle operator is used to calculate scattering via equivalent surface, and radiation from one ES to an other can be captured using the translation operators. EPA loses its accuracy if ESs are very close to each other, or if an ES is very close to PEC object. As a remedy of this problem, tangential-EPA (T-EPA) is introduced. Properties of both algorithms are investigated and discussed in detail. Accuracy and the efficiency of the methods are compared to those of the multilevel fast multipole algorithm.
Newton enküçültme yaklaşımı kullanarak üç boyutlu iletken cisimlerin elektromanyetik görüntülenmesi
The main goal of shape reconstruction is to retrieve the location and shape of an unknown target. This approach is used in a wide range of areas, from detecting cancer tumors to finding buried objects. Various methods can be applied to detect objects in di fferent applications. One of the important challenges in many of these methods is to solve the non-linearity and non-uniqueness of the solutions. Inverse scattering is one of the most e fficient ways to retrieve shapes and locations of targets. By illuminating the objects with electromagnetic waves and collecting the scattering fi elds using appropriate methods, we try to obtain the shape of unknown object. To achieve this goal, we start with an initial guess of the unknown object, then by comparing the scattered far- eld patterns of the guess and the real object, we evolve that object and update it iteratively such that we decrease the di fference between the patterns and finally achieve the shape of the unknown object. In this thesis, we model the object by one of its parameters, such as the location of the nodes on the surface of the object, or by the conductivity, permittivity, and permeability of the discretized space in which the object is placed. Then, the model parameters are updated iteratively by minimizing the mismatch between the measured data of the target and the collected data from the modeled object. Using surface nodes to model a three-dimensional object is a good choice because we decrease the number of unknowns.
Paralel çok sevıyeli hızlı çokkutup algoritmasının çekirdek dışı uygulaması
We developed an out-of-core (OC) implementation of the parallel multilevel fast multipole algorithm (MLFMA) to solve electromagnetic problems with reduced memory. The main purpose of the OC method is to reduce in-core memory (primary storage) by using mass storage (secondary storage) units. Depending on the OC implementation, the in-core data may be left in one piece or divided into partitions. If the latter, the partitions are written out into mass storage unit(s) and read into in-core memory when required. In this way, memory reduction is achieved. However, the proposed method causes time delays because reading and writing large data using massive storage units is a long procedure. In our case, repetitive access to data partitions from the mass storage increases the total time of the iterative solution part of MLFMA. Such time delays can be minimized by selecting the right data type and optimizing the sizes of the data partitions. We run the optimization tests on different types of mass storage devices, such as hard disks and solid state drives. This thesis explores OC implementation of the parallel MLFMA. To be more precise, it presents the results of optimization tests done on different partition sizes and shows how computation time is minimized despite the time delays. This thesis also presents full-wave solutions of scattering problems including hundreds of millions of unknowns by employing an OC-implemented parallel MLFMA.