Coarse space (numerical analysis)

Last updated February 25, 2024

This article deals with a component of numerical methods. For coarse space in topology, see coarse structure.

In numerical analysis, coarse problem is an auxiliary system of equations used in an iterative method for the solution of a given larger system of equations. A coarse problem is basically a version of the same problem at a lower resolution, retaining its essential characteristics, but with fewer variables. The purpose of the coarse problem is to propagate information throughout the whole problem globally.

In multigrid methods for partial differential equations, the coarse problem is typically obtained as a discretization of the same equation on a coarser grid (usually, in finite difference methods) or by a Galerkin approximation on a subspace, called a coarse space. In finite element methods, the Galerkin approximation is typically used, with the coarse space generated by larger elements on the same domain. Typically, the coarse problem corresponds to a grid that is twice or three times coarser.

Coarse spaces (coarse model, surrogate model) are the backbone of algorithms and methodologies exploiting the space mapping concept for solving computationally intensive engineering modeling and design problems.^[1]^[2]^[3]^[4]^[5]^[6]^[7]^[8] In space mapping, a fine or high fidelity (high resolution, computationally intensive) model is used to calibrate or recalibrate—or update on the fly, as in aggressive space mapping—a suitable coarse model. An updated coarse model is often referred to as surrogate model or mapped coarse model. It permits fast, but more accurate, harnessing of the underlying coarse model in the exploration of designs or in design optimization.

In domain decomposition methods, the construction of a coarse problem follows the same principles as in multigrid methods, but the coarser problem has much fewer unknowns, generally only one or just a few unknowns per subdomain or substructure, and the coarse space can be of a quite different type that the original finite element space, e.g. piecewise constants with averaging in balancing domain decomposition or built from energy minimal functions in BDDC. The construction of the coarse problem in FETI is unusual in that it is not obtained as a Galerkin approximation of the original problem, however.

In Algebraic Multigrid Methods and in iterative aggregation methods in mathematical economics and Markov chains, the coarse problem is generally obtained by the Galerkin approximation on a subspace. In mathematical economics, the coarse problem may be obtained by the aggregation of products or industries into a coarse description with fewer variables. In Markov chains, a coarse Markov chain may be obtained by aggregating states.

The speed of convergence of multigrid and domain decomposition methods for elliptic partial differential equations without a coarse problem deteriorates with decreasing mesh step (or decreasing element size, or increasing number of subdomains or substructures), thus making a coarse problem necessary for a scalable algorithm.

Related Research Articles

Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

Reinforcement learning (RL) is an interdisciplinary area of machine learning and optimal control concerned with how an intelligent agent ought to take actions in a dynamic environment in order to maximize the cumulative reward. Reinforcement learning is one of three basic machine learning paradigms, alongside supervised learning and unsupervised learning.

Numerical methods for partial differential equations is the branch of numerical analysis that studies the numerical solution of partial differential equations (PDEs).

The boundary element method (BEM) is a numerical computational method of solving linear partial differential equations which have been formulated as integral equations, including fluid mechanics, acoustics, electromagnetics, fracture mechanics, and contact mechanics.

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.

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.

In mathematics, in the area of numerical analysis, Galerkin methods are named after the Soviet mathematician Boris Galerkin. They convert a continuous operator problem, such as a differential equation, commonly in a weak formulation, to a discrete problem by applying linear constraints determined by finite sets of basis functions.

<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.

A surrogate model is an engineering method used when an outcome of interest cannot be easily measured or computed, so an approximate mathematical model of the outcome is used instead. Most engineering design problems require experiments and/or simulations to evaluate design objective and constraint functions as a function of design variables. For example, in order to find the optimal airfoil shape for an aircraft wing, an engineer simulates the airflow around the wing for different shape variables. For many real-world problems, however, a single simulation can take many minutes, hours, or even days to complete. As a result, routine tasks such as design optimization, design space exploration, sensitivity analysis and "what-if" analysis become impossible since they require thousands or even millions of simulation evaluations.

In numerical mathematics, relaxation methods are iterative methods for solving systems of equations, including nonlinear systems.

In numerical analysis, BDDC (balancing domain decomposition by constraints) is a domain decomposition method for solving large symmetric, positive definite systems of linear equations that arise from the finite element method. BDDC is used as a preconditioner to the conjugate gradient method. A specific version of BDDC is characterized by the choice of coarse degrees of freedom, which can be values at the corners of the subdomains, or averages over the edges or the faces of the interface between the subdomains. One application of the BDDC preconditioner then combines the solution of local problems on each subdomains with the solution of a global coarse problem with the coarse degrees of freedom as the unknowns. The local problems on different subdomains are completely independent of each other, so the method is suitable for parallel computing. With a proper choice of the coarse degrees of freedom (corners in 2D, corners plus edges or corners plus faces in 3D) and with regular subdomain shapes, the condition number of the method is bounded when increasing the number of subdomains, and it grows only very slowly with the number of elements per subdomain. Thus the number of iterations is bounded in the same way, and the method scales well with the problem size and the number of subdomains.

RF microwave CAE CAD is computer-aided design (CAD) using computer technology to aid in the design, modeling, and simulation of an RF or microwave product. It is a visual and symbol-based method of communication whose conventions are particular to RF/microwave engineering.

Engineering optimization is the subject which uses optimization techniques to achieve design goals in engineering. It is sometimes referred to as design optimization.

The space mapping methodology for modeling and design optimization of engineering systems was first discovered by John Bandler in 1993. It uses relevant existing knowledge to speed up model generation and design optimization of a system. The knowledge is updated with new validation information from the system when available.

John William Bandler was a Canadian professor, engineer, entrepreneur, artist, speaker, playwright, and author of fiction and nonfiction. Bandler is known for his invention of space mapping technology and his contributions to device modeling, computer-aided design, microwave engineering, mathematical optimization, and yield-driven design.

Optimization Systems Associates (OSA) was founded by John Bandler in 1983. OSA produced the first commercial implementation of space mapping optimization to enhance the speed and accuracy of engineering design. OSA’s primary thrust was in computer-aided design (CAD) and simulation and optimization of radio-frequency and microwave circuits and systems. Its products included developments of Bandler's space mapping concept and methodology, which facilitates effective modeling and design optimization of computationally intensive engineering systems.

The proper generalized decomposition (PGD) is an iterative numerical method for solving boundary value problems (BVPs), that is, partial differential equations constrained by a set of boundary conditions, such as the Poisson's equation or the Laplace's equation.

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.

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

↑ J.W. Bandler, R.M. Biernacki, S.H. Chen, P.A. Grobelny, and R.H. Hemmers, “Space mapping technique for electromagnetic optimization,” IEEE Trans. Microwave Theory Tech., vol. 42, no. 12, pp. 2536–2544, Dec. 1994.
↑ J.W. Bandler, R.M. Biernacki, S.H. Chen, R.H. Hemmers, and K. Madsen, “Electromagnetic optimization exploiting aggressive space mapping,” IEEE Trans. Microwave Theory Tech., vol. 43, no. 12, pp. 2874–2882, Dec. 1995.
↑ A.J. Booker, J.E. Dennis, Jr., P.D. Frank, D.B. Serafini, V. Torczon, and M.W. Trosset,"A rigorous framework for optimization of expensive functions by surrogates," Structural Optimization, vol. 17, no. 1, pp. 1–13, Feb. 1999.
↑ J.W. Bandler, Q. Cheng, S.A. Dakroury, A.S. Mohamed, M.H. Bakr, K. Madsen and J. Søndergaard, "Space mapping: the state of the art," IEEE Trans. Microwave Theory Tech., vol. 52, no. 1, pp. 337–361, Jan. 2004.
↑ T.D. Robinson, M.S. Eldred, K.E. Willcox, and R. Haimes, "Surrogate-Based Optimization Using Multifidelity Models with Variable Parameterization and Corrected Space Mapping," AIAA Journal, vol. 46, no. 11, November 2008.
↑ M. Redhe and L. Nilsson, “Optimization of the new Saab 9–3 exposed to impact load using a space mapping technique,” Structural and Multidisciplinary Optimization, vol. 27, no. 5, pp. 411–420, July 2004.
↑ J.E. Rayas-Sanchez, "Power in simplicity with ASM: tracing the aggressive space mapping algorithm over two decades of development and engineering applications", IEEE Microwave Magazine, vol. 17, no. 4, pp. 64–76, April 2016.
↑ J.W. Bandler and S. Koziel "Advances in electromagnetics-based design optimization", IEEE MTT-S Int. Microwave Symp. Digest (San Francisco, CA, 2016).

Jan Mandel and Bedrich Sousedik, "Coarse space over the ages", Nineteenth International Conference on Domain Decomposition, Springer-Verlag, submitted, 2009. arXiv:0911.5725
Olof B. Widlund, "The Development of Coarse Spaces for Domain Decomposition Algorithms", in: Domain Decomposition Methods in Science and Engineering XVIII, Bercovier, M. and Gander, M.J. and Kornhuber, R. and Widlund, O. (eds.), Lecture Notes in Computational Science and Engineering 70, Springer-Verlag, 2009, Proceedings of 18th International Conference on Domain Decomposition, Jerusalem, Israel, January 2008, doi : 10.1007/978-3-642-02677-5_26.

Coarse space (numerical analysis)

Related Research Articles

References

See also