Multilevel fast multipole method

Last updated

The multilevel fast multipole method (MLFMM) is used along with method of moments (MoM) a numerical computational method of solving linear partial differential equations which have been formulated as integral equations of large objects almost faster without loss in accuracy. [1] This method is an alternative formulation of the technology behind the MoM and is applicable to much larger structures like radar cross-section (RCS) analysis, antenna integration on large structures, reflector antenna design, finite size antenna arrays, etc., making full-wave current-based solutions of such structures a possibility. [2] [3]

Method

The MLFMM is based on the Method of Moments (MoM), but reduces the memory complexity from to , and the solving complexity from to , where represents the number of unknowns and the number of iterations in the solver. This method subdivides the Boundary Element mesh into different clusters and if two clusters are in each other's far field, all calculations that would have to be made for every pair of nodes can be reduced to the midpoints of the clusters with almost no loss of accuracy. For clusters not in the far field, the traditional BEM has to be applied. That is MLFMM introduces different levels of clustering (clusters made out of smaller clusters) to additionally enhance computation speed. [4] [5] [6] [7] [8] [9]

Related Research Articles

<span class="mw-page-title-main">Computational chemistry</span> Branch of chemistry

Computational chemistry is a branch of chemistry that uses computer simulation to assist in solving chemical problems. It uses methods of theoretical chemistry, incorporated into computer programs, to calculate the structures and properties of molecules, groups of molecules, and solids. The importance of this subject stems from the fact that, with the exception of some relatively recent findings related to the hydrogen molecular ion, achieving an accurate quantum mechanical depiction of chemical systems analytically, or in a closed form, is not feasible. The complexity inherent in many-body problem exacerbates the challenge of providing detailed descriptions in quantum mechanical systems. While computational results normally complement the information obtained by chemical experiments, it can in some cases predict unobserved chemical phenomena.

<span class="mw-page-title-main">Hierarchical clustering</span> Statistical method of analysis which seeks to build a hierarchy of clusters

In data mining and statistics, hierarchical clustering is a method of cluster analysis that seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into two categories:

In numerical analysis, a multigrid method is an algorithm for solving differential equations using a hierarchy of discretizations. They are an example of a class of techniques called multiresolution methods, very useful in problems exhibiting multiple scales of behavior. For example, many basic relaxation methods exhibit different rates of convergence for short- and long-wavelength components, suggesting these different scales be treated differently, as in a Fourier analysis approach to multigrid. MG methods can be used as solvers as well as preconditioners.

<span class="mw-page-title-main">Finite-difference time-domain method</span>

Finite-difference time-domain (FDTD) or Yee's method is a numerical analysis technique used for modeling computational electrodynamics. Since it is a time-domain method, FDTD solutions can cover a wide frequency range with a single simulation run, and treat nonlinear material properties in a natural way.

<span class="mw-page-title-main">Computational electromagnetics</span> Branch of physics

Computational electromagnetics (CEM), computational electrodynamics or electromagnetic modeling is the process of modeling the interaction of electromagnetic fields with physical objects and the environment using computers.

Electromagnetic field solvers are specialized programs that solve Maxwell's equations directly. They form a part of the field of electronic design automation, or EDA, and are commonly used in the design of integrated circuits and printed circuit boards. They are used when a solution from first principles or the highest accuracy is required.

Dassault Systèmes Simulia Corp. is a computer-aided engineering (CAE) vendor. Formerly known as Abaqus Inc. and previously Hibbitt, Karlsson & Sorensen, Inc., (HKS), the company was founded in 1978 by David Hibbitt, Bengt Karlsson and Paul Sorensen, and has its headquarters in Providence, Rhode Island.

In applied mathematics, polyharmonic splines are used for function approximation and data interpolation. They are very useful for interpolating and fitting scattered data in many dimensions. Special cases include thin plate splines and natural cubic splines in one dimension.

Characteristic modes (CM) form a set of functions which, under specific boundary conditions, diagonalizes operator relating field and induced sources. Under certain conditions, the set of the CM is unique and complete (at least theoretically) and thereby capable of describing the behavior of a studied object in full.

In mathematics, a Cauchy matrix, named after Augustin-Louis Cauchy, is an m×n matrix with elements aij in the form

The fast multipole method (FMM) is a numerical technique that was developed to speed up the calculation of long-ranged forces in the n-body problem. It does this by expanding the system Green's function using a multipole expansion, which allows one to group sources that lie close together and treat them as if they are a single source.

Feko is a computational electromagnetics software product developed by Altair Engineering. The name is derived from the German acronym "Feldberechnung für Körper mit beliebiger Oberfläche", which can be translated as "field calculations involving bodies of arbitrary shape". It is a general purpose 3D electromagnetic (EM) simulator.

<span class="mw-page-title-main">Top tree</span>

A top tree is a data structure based on a binary tree for unrooted dynamic trees that is used mainly for various path-related operations. It allows simple divide-and-conquer algorithms. It has since been augmented to maintain dynamically various properties of a tree such as diameter, center and median.

In numerical mathematics, hierarchical matrices (H-matrices) are used as data-sparse approximations of non-sparse matrices. While a sparse matrix of dimension can be represented efficiently in units of storage by storing only its non-zero entries, a non-sparse matrix would require units of storage, and using this type of matrices for large problems would therefore be prohibitively expensive in terms of storage and computing time. Hierarchical matrices provide an approximation requiring only units of storage, where is a parameter controlling the accuracy of the approximation. In typical applications, e.g., when discretizing integral equations, preconditioning the resulting systems of linear equations, or solving elliptic partial differential equations, a rank proportional to with a small constant is sufficient to ensure an accuracy of . Compared to many other data-sparse representations of non-sparse matrices, hierarchical matrices offer a major advantage: the results of matrix arithmetic operations like matrix multiplication, factorization or inversion can be approximated in operations, where

<span class="mw-page-title-main">Levent Gürel</span> Turkish scientist

Levent Gürel is a Turkish scientist and electrical engineer. He was the director of Computational Electromagnetics Research Center (BiLCEM) and a professor in the Department of Electrical and Electronics Engineering at the Bilkent University, Turkey until November 2014. Currently, he is serving as an adjunct professor at the University of Illinois Urbana-Champaign, Department of Electrical and Computer Engineering. He is also serving as the founder and CEO of ABAKUS Computing Technologies.

Ulrich Jakobus is Senior Vice President - Electromagnetic Solutions of Altair, Germany and was awarded Fellow of the Institute of Electrical and Electronics Engineers (IEEE) in 2013 for leadership in hybrid computational tool development and commercialization. His research laid the foundations for the commercial electromagnetics code FEKO which is used in antenna design, antenna placement, electromagnetic compatibility, microwave components, bioelectromagnetics, radar cross section and related fields.

<span class="mw-page-title-main">Weng Cho Chew</span> Malaysian-American electrical engineer

Weng Cho Chew is a Malaysian-American electrical engineer and applied physicist known for contributions to wave physics, especially computational electromagnetics. He is a Distinguished Professor of Electrical and Computer Engineering at Purdue University.

Roger Fuller Harrington is an American electrical engineer and professor emeritus at Syracuse University. He is best known for his contributions to computational electromagnetics with his development of method of moments (MoM). Harrington's 1968 book, Field Computation by Moment Methods, is regarded as a pivotal textbook on the subject.

Tapan Kumar Sarkar was an Indian-American electrical engineer and Professor Emeritus at the Department of Electrical Engineering and Computer Science at Syracuse University. He was best known for his contributions to computational electromagnetics and antenna theory.

<span class="mw-page-title-main">Method of moments (electromagnetics)</span> Numerical method in computational electromagnetics

The method of moments (MoM), also known as the moment method and method of weighted residuals, is a numerical method in computational electromagnetics. It is used in computer programs that simulate the interaction of electromagnetic fields such as radio waves with matter, for example antenna simulation programs like NEC that calculate the radiation pattern of an antenna. Generally being a frequency-domain method, it involves the projection of an integral equation into a system of linear equations by the application of appropriate boundary conditions. This is done by using discrete meshes as in finite difference and finite element methods, often for the surface. The solutions are represented with the linear combination of pre-defined basis functions; generally, the coefficients of these basis functions are the sought unknowns. Green's functions and Galerkin method play a central role in the method of moments.

References

  1. "Multilevel Fast Multipole Method (MLFMM)". Austrian Academy of Sciences – Acoustics Research Institute. Retrieved 20 April 2014.
  2. "Multilevel Fast Multipole Method (MLFMM)". Feko. Retrieved 20 April 2014.
  3. "Multilevel Fast Multipole Method (MLFMM)". E field. 2013-04-30. Retrieved 20 April 2014.
  4. P.-L. Rui; R.-S. Chen; Z.-W. Liu & Y.-N. Gan (2008). "Schwarz-Krylov Subspace Method for MLFMM Analysis of Electromagnetic Wave Scattering Problems". Progress in Electromagnetics Research. PIER. 82: 51–63. doi: 10.2528/PIER08013003 .
  5. Bingle, M Burger, E.; Jakobus, U.; van Tonder, J.J. (7–9 Nov 2011). "Theory and application of an MLFMM/FEM hybrid framework in FEKO". 2011 IEEE International Conference on Microwaves, Communications, Antennas and Electronic Systems (COMCAS 2011). pp. 1–3. doi:10.1109/COMCAS.2011.6105819. ISBN   978-1-4577-1694-2. S2CID   39160247.{{cite book}}: CS1 maint: multiple names: authors list (link)
  6. D'Ambrosio, K.; Pirich, R.; Kaufman, A.; Mesecher, D. (11 May 2009). "Parallel computation methods for enhanced MOM and MLFMM performance". 2009 IEEE Long Island Systems, Applications and Technology Conference. pp. 1–4. doi:10.1109/LISAT.2009.5031571. ISBN   978-1-4244-2347-7. S2CID   18786124.
  7. Ulrich Jakobus; Johann van Tonder & Marlize Schoeman. "Advanced EMC Modeling by Means of a Parallel MLFMM and Coupling with Network Theory" (PDF). EMSS. Retrieved 20 April 2014.
  8. "(Electrically) Large Applications & Integral Equation solver" (PDF). CST. Retrieved 20 April 2014.
  9. "Multilevel Fast Multipole Method (MLFMM)". ESI. Archived from the original on 20 April 2014. Retrieved 20 April 2014.