1.
Numerical analysis
–
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis. Being able to compute the sides of a triangle is important, for instance, in astronomy, carpentry. Numerical analysis continues this tradition of practical mathematical calculations. Much like the Babylonian approximation of the root of 2, modern numerical analysis does not seek exact answers. Instead, much of numerical analysis is concerned with obtaining approximate solutions while maintaining reasonable bounds on errors, before the advent of modern computers numerical methods often depended on hand interpolation in large printed tables. Since the mid 20th century, computers calculate the required functions instead and these same interpolation formulas nevertheless continue to be used as part of the software algorithms for solving differential equations. Computing the trajectory of a spacecraft requires the accurate numerical solution of a system of differential equations. Car companies can improve the safety of their vehicles by using computer simulations of car crashes. Such simulations essentially consist of solving differential equations numerically. Hedge funds use tools from all fields of analysis to attempt to calculate the value of stocks. Airlines use sophisticated optimization algorithms to decide ticket prices, airplane and crew assignments, historically, such algorithms were developed within the overlapping field of operations research. Insurance companies use programs for actuarial analysis. The rest of this section outlines several important themes of numerical analysis, the field of numerical analysis predates the invention of modern computers by many centuries. Linear interpolation was already in use more than 2000 years ago, to facilitate computations by hand, large books were produced with formulas and tables of data such as interpolation points and function coefficients. The function values are no very useful when a computer is available. The mechanical calculator was developed as a tool for hand computation. These calculators evolved into electronic computers in the 1940s, and it was found that these computers were also useful for administrative purposes. But the invention of the computer also influenced the field of analysis, since now longer
2.
Computer simulation
–
Computer simulations reproduce the behavior of a system using a model. Simulation of a system is represented as the running of the systems model and it can be used to explore and gain new insights into new technology and to estimate the performance of systems too complex for analytical solutions. The scale of events being simulated by computer simulations has far exceeded anything possible using traditional paper-and-pencil mathematical modeling, other examples include a 1-billion-atom model of material deformation, a 2. Because of the computational cost of simulation, computer experiments are used to perform such as uncertainty quantification. A computer model is the algorithms and equations used to capture the behavior of the system being modeled, by contrast, computer simulation is the actual running of the program that contains these equations or algorithms. Simulation, therefore, is the process of running a model, thus one would not build a simulation, instead, one would build a model, and then either run the model or equivalently run a simulation. It was a simulation of 12 hard spheres using a Monte Carlo algorithm, Computer simulation is often used as an adjunct to, or substitute for, modeling systems for which simple closed form analytic solutions are not possible. The external data requirements of simulations and models vary widely, for some, the input might be just a few numbers, while others might require terabytes of information. Because of this variety, and because diverse simulation systems have common elements. Systems that accept data from external sources must be careful in knowing what they are receiving. While it is easy for computers to read in values from text or binary files, often they are expressed as error bars, a minimum and maximum deviation from the value range within which the true value lie. Even small errors in the data can accumulate into substantial error later in the simulation. While all computer analysis is subject to the GIGO restriction, this is true of digital simulation. Indeed, observation of this inherent, cumulative error in digital systems was the main catalyst for the development of chaos theory, another way of categorizing models is to look at the underlying data structures. For time-stepped simulations, there are two classes, Simulations which store their data in regular grids and require only next-neighbor access are called stencil codes. Many CFD applications belong to this category, if the underlying graph is not a regular grid, the model may belong to the meshfree method class. Equations define the relationships between elements of the system and attempt to find a state in which the system is in equilibrium. Such models are used in simulating physical systems, as a simpler modeling case before dynamic simulation is attempted
3.
Scientific visualization
–
Scientific visualization is an interdisciplinary branch of science. It is also considered a subset of computer graphics, a branch of computer science, the purpose of scientific visualization is to graphically illustrate scientific data to enable scientists to understand, illustrate, and glean insight from their data. One of the earliest examples of scientific visualisation was Maxwells thermodynamic surface. This prefigured modern scientific techniques that use computer graphics. Scientific visualization using computer graphics gained in popularity as graphics matured, primary applications were scalar fields and vector fields from computer simulations and also measured data. The primary methods for visualizing two-dimensional scalar fields are color mapping and drawing contour lines, 2D vector fields are visualized using glyphs and streamlines or line integral convolution methods. For 3D scalar fields the primary methods are volume rendering and isosurfaces, methods for visualizing vector fields include glyphs such as arrows, streamlines and streaklines, particle tracing, line integral convolution and topological methods. Later, visualization techniques such as hyperstreamlines were developed to visualize 2D, computer animation is the art, technique, and science of creating moving images via the use of computers. It is becoming common to be created by means of 3D computer graphics, though 2D computer graphics are still widely used for stylistic, low bandwidth. Sometimes the target of the animation is the computer itself, but sometimes the target is another medium and it is also referred to as CGI, especially when used in films. Computer simulation is a program, or network of computers. The simultaneous visualization and simulation of a system is called visulation, computer simulations vary from computer programs that run a few minutes, to network-based groups of computers running for hours, to ongoing simulations that run for months. Information visualization focused on the creation of approaches for conveying information in intuitive ways. The key difference between scientific visualization and information visualization is that information visualization is often applied to data that is not generated by scientific inquiry, some examples are graphical representations of data for business, government, news and social media. Interface technology and perception shows how new interfaces and an understanding of underlying perceptual issues create new opportunities for the scientific visualization community. Rendering is the process of generating an image from a model, the model is a description of three-dimensional objects in a strictly defined language or data structure. It would contain geometry, viewpoint, texture, lighting, the image is a digital image or raster graphics image. The term may be by analogy with a rendering of a scene
4.
Morse/Long-range potential
–
Owing to the simplicity of the Morse potential, it is not used in modern spectroscopy. The MLR potential is a version of the Morse potential which has the correct theoretical long-range form of the potential naturally built into it. Cases of particular note include, the c-state of Li2, where the MLR potential was able to bridge a gap of more than 5000 cm−1 in experimental data. Two years later it was found that Dattanis MLR potential was able to predict the energies in the middle of this gap. The accuracy of these predictions was much better than the most sophisticated ab initio techniques at the time and this lithium oscillator strength is related to the radiative lifetime of atomic lithium and is used as a benchmark for atomic clocks and measurements of fundamental constants. It has been said that work by Le Roy et al. was a landmark in diatomic spectral analysis. The a-state of KLi, where a global potential was successfully built despite there only being a small amount of data near the top of the potential. The MLR potential is based on the classic Morse potential which was first introduced in 1929 by Philip M. Morse, a primitive version of the MLR potential was first introduced in 2006 by professor Robert J. Le Roy and colleagues for a study on N2. This primitive form was used on Ca2, KLi and MgH, before the modern version was introduced in 2009 by Le Roy, Dattani. A further extension of the MLR potential referred to as the MLR3 potential was introduced in a 2010 study of Cs2, and it is clear to see that, lim r → ∞ = y n r x, so lim r → ∞ β = β ∞. More sophisticated versions are used for polyatomic molecules, examples of molecules for which the MLR has been used to represent ab initio points are KLi, KBe
5.
Lennard-Jones potential
–
The Lennard-Jones potential is a mathematically simple model that approximates the interaction between a pair of neutral atoms or molecules. A form of this potential was first proposed in 1924 by John Lennard-Jones. At rm, the function has the value −ε. The distances are related as rm = 21/6σ ≈1. 122σ and these parameters can be fitted to reproduce experimental data or accurate quantum chemistry calculations. Due to its simplicity, the Lennard-Jones potential is used extensively in computer simulations even though more accurate potentials exist. Differentiating the L-J potential with respect to r gives an expression for the net inter-molecular force between 2 molecules and this inter-molecular force may be attractive or repulsive, depending on the value of r. When r is very small, the 2 molecules repel each other, whereas the functional form of the attractive term has a clear physical justification, the repulsive term has no theoretical justification. It is used because it approximates the Pauli repulsion well, and is convenient due to the relative computing efficiency of calculating r12 as the square of r6. The Lennard-Jones potential was improved by the Buckingham potential later proposed by R. A. Buckingham, in which the part is an exponential function. The L-J potential is a good approximation. Due to its simplicity, it is used to describe the properties of gases. It is especially accurate for noble gas atoms, and is an approximation at long and short distances for neutral atoms. The lowest energy arrangement of a number of atoms described by a Lennard-Jones potential is a hexagonal close-packing. On raising temperature, the lowest free energy arrangement becomes cubic close packing, under pressure, the lowest energy structure switches between cubic and hexagonal close packing. Real materials include BCC structures also, other more recent methods, such as the Stockmayer potential, describe the interaction of molecules more accurately. Quantum chemistry methods, Møller–Plesset perturbation theory, coupled cluster method, or full configuration interaction can give accurate results. There are many different ways to formulate the Lennard-Jones potential. This form is a formulation that is used by some simulation software, V L J = A r 12 − B r 6
6.
Yukawa potential
–
The potential is monotone increasing in r and it is negative, implying the force is attractive. In the SI system, the unit of the Yukawa potential is, the Coulomb potential of electromagnetism is an example of a Yukawa potential with e−kmr equal to 1 everywhere. This can be interpreted as saying that the mass m is equal to 0. In interactions between a field and a fermion field, the constant g is equal to the gauge coupling constant between those fields. In the case of the force, the fermions would be a proton. Hideki Yukawa showed in the 1930s that such a potential arises from the exchange of a scalar field such as the field of a massive boson. Since the field mediator is massive the corresponding force has a certain range, if the mass is zero, then the Yukawa potential equals a Coulomb potential, and the range is said to be infinite. In fact, we have, m =0 ⇒ e − m r = e 0 =1, consequently, the equation V Yukawa = − g 2 e − m r r simplifies to the form of the Coulomb potential V Coulomb = − g 21 r. A comparison of the long range potential strength for Yukawa and Coulomb is shown in Figure 2 and it can be seen that the Coulomb potential has effect over a greater distance whereas the Yukawa potential approaches zero rather quickly. However, any Yukawa potential or Coulomb potential are non-zero for any large r, the easiest way to understand that the Yukawa potential is associated with a massive field is by examining its Fourier transform. One has V = − g 23 ∫ e i k ⋅ r 4 π k 2 + m 2 d 3 k where the integral is performed all possible values of the 3-vector momentum k. In this form, the fraction 4 π / is seen to be the propagator or Greens function of the Klein–Gordon equation, the Yukawa potential can be derived as the lowest order amplitude of the interaction of a pair of fermions. The Yukawa interaction couples the fermion field ψ to the meson field ϕ with the coupling term L i n t = g ψ ¯ ϕ ψ. The scattering amplitude for two fermions, one with initial momentum p 1 and the other with momentum p 2, exchanging a meson with momentum k, is given by the Feynman diagram on the right. The Feynman rules for each associate a factor of g with the amplitude. The line in the middle, connecting the two lines, represents the exchange of a meson. The Feynman rule for an exchange is to use the propagator. Thus, we see that the Feynman amplitude for this graph is nothing more than V = − g 24 π k 2 + m 2, from the previous section, this is seen to be the Fourier transform of the Yukawa potential
7.
Morse potential
–
The Morse potential, named after physicist Philip M. Morse, is a convenient interatomic interaction model for the potential energy of a diatomic molecule. It is an approximation for the vibrational structure of the molecule than the QHO because it explicitly includes the effects of bond breaking. It also accounts for the anharmonicity of real bonds and the transition probability for overtone. The Morse potential can also be used to other interactions such as the interaction between an atom and a surface. Due to its simplicity, it is not used in modern spectroscopy, however, its mathematical form inspired the MLR potential, which is the most popular potential energy function used for fitting spectroscopic data. The dissociation energy of the bond can be calculated by subtracting the zero point energy E from the depth of the well. Since the zero of energy is arbitrary, the equation for the Morse potential can be rewritten any number of ways by adding or subtracting a constant value. This form approaches zero at r and equals − D e at its minimum. It clearly shows that the Morse potential is the combination of a short-range repulsion term, like the quantum harmonic oscillator, the energies and eigenstates of the Morse potential can be found using operator methods. One approach involves applying the method to the Hamiltonian. Whereas the energy spacing between levels in the quantum harmonic oscillator is constant at h ν0, the energy between adjacent levels decreases with increasing v in the Morse oscillator. Mathematically, the spacing of Morse levels is E − E = h ν0 −2 /2 D e and this trend matches the anharmonicity found in real molecules. However, this equation fails above some value of v m where E − E is calculated to be zero or negative, specifically, v m =2 D e − h ν0 h ν0. This failure is due to the number of bound levels in the Morse potential. For energies above v m, all the energy levels are allowed. Below v m, E is an approximation for the true vibrational structure in non-rotating diatomic molecules. An important extension of the Morse potential that made the Morse form very useful for spectroscopy is the MLR potential. The MLR potential is used as a standard for representing spectroscopic and/or virial data of diatomic molecules by a potential energy curve
8.
Computational fluid dynamics
–
Computational fluid dynamics is a branch of fluid mechanics that uses numerical analysis and data structures to solve and analyze problems that involve fluid flows. Computers are used to perform the required to simulate the interaction of liquids. With high-speed supercomputers, better solutions can be achieved, ongoing research yields software that improves the accuracy and speed of complex simulation scenarios such as transonic or turbulent flows. Initial experimental validation of such software is performed using a tunnel with the final validation coming in full-scale testing. The fundamental basis of almost all CFD problems is the Navier–Stokes equations and these equations can be simplified by removing terms describing viscous actions to yield the Euler equations. Further simplification, by removing terms describing vorticity yields the full potential equations, finally, for small perturbations in subsonic and supersonic flows these equations can be linearized to yield the linearized potential equations. Historically, methods were first developed to solve the potential equations. Two-dimensional methods, using conformal transformations of the flow about a cylinder to the flow about an airfoil were developed in the 1930s. One of the earliest type of calculations resembling modern CFD are those by Lewis Fry Richardson, in the sense that these calculations used finite differences and divided the physical space in cells. Although they failed dramatically, these calculations, together with Richardsons book Weather prediction by numerical process, set the basis for modern CFD, in fact, early CFD calculations during the 1940s using ENIAC used methods close to those in Richardsons 1922 book. The computer power available paced development of three-dimensional methods, probably the first work using computers to model fluid flow, as governed by the Navier-Stokes equations, was performed at Los Alamos National Lab, in the T3 group. This group was led by Francis H. Harlow, who is considered as one of the pioneers of CFD. Fromms vorticity-stream-function method for 2D, transient, incompressible flow was the first treatment of strongly contorting incompressible flows in the world, the first paper with three-dimensional model was published by John Hess and A. M. O. Smith of Douglas Aircraft in 1967 and this method discretized the surface of the geometry with panels, giving rise to this class of programs being called Panel Methods. Their method itself was simplified, in that it did not include lifting flows and hence was mainly applied to ship hulls, the first lifting Panel Code was described in a paper written by Paul Rubbert and Gary Saaris of Boeing Aircraft in 1968. In time, more advanced three-dimensional Panel Codes were developed at Boeing, Lockheed, Douglas, McDonnell Aircraft, NASA, some were higher order codes, using higher order distributions of surface singularities, while others used single singularities on each surface panel. The advantage of the lower order codes was that they ran much faster on the computers of the time, today, VSAERO has grown to be a multi-order code and is the most widely used program of this class. It has been used in the development of submarines, surface ships, automobiles, helicopters, aircraft
9.
Finite difference method
–
Today, FDMs are the dominant approach to numerical solutions of partial differential equations. First, assuming the function whose derivatives are to be approximated is properly-behaved, by Taylors theorem, we can create a Taylor Series expansion f = f + f ′1. H n + R n, where n. denotes the factorial of n, the error in a methods solution is defined as the difference between the approximation and the exact analytical solution. To use a finite difference method to approximate the solution to a problem and this is usually done by dividing the domain into a uniform grid. Note that this means that finite-difference methods produce sets of numerical approximations to the derivative. An expression of general interest is the truncation error of a method. Typically expressed using Big-O notation, local truncation error refers to the error from an application of a method. That is, it is the quantity f ′ − f i ′ if f ′ refers to the exact value, the remainder term of a Taylor polynomial is convenient for analyzing the local truncation error. Using the Lagrange form of the remainder from the Taylor polynomial for f, N +1, where x 0 < ξ < x 0 + h, the dominant term of the local truncation error can be discovered. For example, again using the formula for the first derivative. 2, and with some algebraic manipulation, this leads to f − f i h = f ′ + f ″2, a final expression of this example and its order is, f − f i h = f ′ + O. This means that, in case, the local truncation error is proportional to the step sizes. The quality and duration of simulated FDM solution depends on the discretization equation selection, the data quality and simulation duration increase significantly with smaller step size. Therefore, a balance between data quality and simulation duration is necessary for practical usage. Large time steps are useful for increasing speed in practice. However, time steps which are too large may create instabilities, the von Neumann method is usually applied to determine the numerical model stability. For example, consider the differential equation u ′ =3 u +2. The last equation is an equation, and solving this equation gives an approximate solution to the differential equation
10.
Finite volume method
–
The finite volume method is a method for representing and evaluating partial differential equations in the form of algebraic equations. Similar to the finite difference method or finite element method, values are calculated at discrete places on a meshed geometry, Finite volume refers to the small volume surrounding each node point on a mesh. In the finite volume method, volume integrals in a differential equation that contain a divergence term are converted to surface integrals. These terms are then evaluated as fluxes at the surfaces of finite volume. Because the flux entering a given volume is identical to that leaving the adjacent volume, another advantage of the finite volume method is that it is easily formulated to allow for unstructured meshes. The method is used in computational fluid dynamics packages. Consider a simple 1D advection problem defined by the partial differential equation ∂ ρ ∂ t + ∂ f ∂ x =0, t ≥0. Here, ρ = ρ represents the variable and f = f represents the flux or flow of ρ. Conventionally, positive f represents flow to the right while negative f represents flow to the left, if we assume that equation represents a flowing medium of constant area, we can sub-divide the spatial domain, x, into finite volumes or cells with cell centres indexed as i. Integrating equation in time, we have, ρ = ρ − ∫ t 1 t 2 f x d t and we assume that f is well behaved and that we can reverse the order of integration. Also, recall that flow is normal to the area of the cell. Equation is exact for the averages, i. e. no approximations have been made during its derivation. This method can also be applied to a 2D situation by considering the north and south faces along with the east and west faces around a node. We can also consider the conservation law problem, represented by the following PDE. Here, u represents a vector of states and f represents the corresponding flux tensor, again we can sub-divide the spatial domain into finite volumes or cells. For a particular cell, i, we take the integral over the total volume of the cell, v i. So, finally, we are able to present the general equivalent to. Again, values for the fluxes can be reconstructed by interpolation or extrapolation of the cell averages
11.
Finite element method
–
The finite element method is a numerical method for solving problems of engineering and mathematical physics. It is also referred to as finite element analysis, typical problem areas of interest include structural analysis, heat transfer, fluid flow, mass transport, and electromagnetic potential. The analytical solution of these problems generally require the solution to boundary value problems for partial differential equations, the finite element method formulation of the problem results in a system of algebraic equations. The method yields approximate values of the unknowns at discrete number of points over the domain, to solve the problem, it subdivides a large problem into smaller, simpler parts that are called finite elements. The simple equations that model these finite elements are assembled into a larger system of equations that models the entire problem. FEM then uses variational methods from the calculus of variations to approximate a solution by minimizing an associated error function, the global system of equations has known solution techniques, and can be calculated from the initial values of the original problem to obtain a numerical answer. To explain the approximation in this process, FEM is commonly introduced as a case of Galerkin method. The process, in language, is to construct an integral of the inner product of the residual. In simple terms, it is a procedure that minimizes the error of approximation by fitting trial functions into the PDE, the residual is the error caused by the trial functions, and the weight functions are polynomial approximation functions that project the residual. These equation sets are the element equations and they are linear if the underlying PDE is linear, and vice versa. In step above, a system of equations is generated from the element equations through a transformation of coordinates from the subdomains local nodes to the domains global nodes. This spatial transformation includes appropriate orientation adjustments as applied in relation to the coordinate system. The process is carried out by FEM software using coordinate data generated from the subdomains. FEM is best understood from its application, known as finite element analysis. FEA as applied in engineering is a tool for performing engineering analysis. It includes the use of mesh generation techniques for dividing a complex problem into small elements, FEA is a good choice for analyzing problems over complicated domains, when the domain changes, when the desired precision varies over the entire domain, or when the solution lacks smoothness. For instance, in a crash simulation it is possible to increase prediction accuracy in important areas like the front of the car. Another example would be in weather prediction, where it is more important to have accurate predictions over developing highly nonlinear phenomena rather than relatively calm areas
12.
Riemann solver
–
A Riemann solver is a numerical method used to solve a Riemann problem. They are heavily used in fluid dynamics and computational magnetohydrodynamics. Godunov is credited with introducing the first exact Riemann solver for the Euler equations, modern solvers are able to simulate relativistic effects and magnetic fields. For the hydrodynamic case latest research showed the possibility to avoid the iterations to calculate the exact solution for the Euler equations. As iterative solutions are too costly, especially in Magnetohydrodynamics, some approximations have to be made, the most popular solvers are, Roe used the linearisation of the Jacobian, which he then solves exactly. The HLLE solver is a solution to the Riemann problem, which is only based on the integral form of the conservation laws. The stability and robustness of the HLLE solver is closely related to the signal velocities, the description of the HLLE scheme in the book mentioned below is incomplete and partially wrong. The reader is referred to the original paper, actually, the HLLE scheme is based on a new stability theory for discontinuities in fluids, which was never published. The HLLC solver was introduced by Toro and it restores the missing Rarefaction wave by some estimates, like linearisations, these can be simple but also more advanced exists like using the Roe average velocity for the middle wave speed. They are quite robust and efficient but somewhat more diffusive and these solvers were introduced by Nishikawa and Kitamura, in order to overcome the carbuncle problems of the Roe solver and the excessive diffusion of the HLLE solver at the same time. In particular, the one derived from the Roe and HLLE solvers, called Rotated-RHLL solver, is extremely robust, godunovs scheme Computational fluid dynamics Computational magnetohydrodynamics Toro, Eleuterio F. Riemann Solvers and Numerical Methods for Fluid Dynamics, Berlin, Springer Verlag, ISBN 3-540-65966-8
13.
Smoothed-particle hydrodynamics
–
Smoothed-particle hydrodynamics is a computational method used for simulating the dynamics of continuum media, such as solid mechanics and fluid flows. It was developed by Gingold and Monaghan and Lucy initially for astrophysical problems and it has been used in many fields of research, including astrophysics, ballistics, volcanology, and oceanography. It is a mesh-free Lagrangian method, and the resolution of the method can easily be adjusted with respect to such as the density. The smoothed-particle hydrodynamics method works by dividing the fluid into a set of discrete elements and these particles have a spatial distance, over which their properties are smoothed by a kernel function. This means that the quantity of any particle can be obtained by summing the relevant properties of all the particles which lie within the range of the kernel. For example, using Monaghans popular cubic spline kernel the temperature at position r depends on the temperatures of all the particles within a radial distance 2 h of r. The contributions of each particle to a property are weighted according to their distance from the particle of interest, mathematically, this is governed by the kernel function. Kernel functions commonly used include the Gaussian function and the cubic spline, the latter function is exactly zero for particles further away than two smoothing lengths. This has the advantage of saving computational effort by not including the relatively minor contributions from distant particles, similarly, the spatial derivative of a quantity can be obtained easily by virtue of the linearity of the derivative. ∇ A = ∑ j m j A j ρ j ∇ W, although the size of the smoothing length can be fixed in both space and time, this does not take advantage of the full power of SPH. By assigning each particle its own smoothing length and allowing it to vary with time, for example, in a very dense region where many particles are close together the smoothing length can be made relatively short, yielding high spatial resolution. Conversely, in low-density regions where particles are far apart and the resolution is low. Combined with an equation of state and an integrator, SPH can simulate hydrodynamic flows efficiently, however, the traditional artificial viscosity formulation used in SPH tends to smear out shocks and contact discontinuities to a much greater extent than state-of-the-art grid-based schemes. The Lagrangian-based adaptivity of SPH is analogous to the adaptivity present in grid-based adaptive mesh refinement codes, in some ways it is actually simpler because SPH particles lack any explicit topology relating them, unlike the elements in FEM. Adaptivity in SPH can be introduced in two ways, either by changing the particle smoothing lengths or by splitting SPH particles into daughter particles with smaller smoothing lengths, the first method is common in astrophysical simulations where the particles naturally evolve into states with large density differences. However, in hydrodynamics simulations where the density is constant this is not a suitable method for adaptivity. For this reason particle splitting can be employed, with conditions for splitting ranging from distance to a free surface through to material shear. Often in astrophysics, one wishes to model self-gravity in addition to pure hydrodynamics, the particle-based nature of SPH makes it ideal to combine with a particle-based gravity solver, for instance tree gravity code, particle mesh, or particle-particle particle-mesh
14.
Monte Carlo method
–
Monte Carlo methods are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. Their essential idea is using randomness to solve problems that might be deterministic in principle and they are often used in physical and mathematical problems and are most useful when it is difficult or impossible to use other approaches. Monte Carlo methods are used in three distinct problem classes, optimization, numerical integration, and generating draws from a probability distribution. In principle, Monte Carlo methods can be used to any problem having a probabilistic interpretation. By the law of numbers, integrals described by the expected value of some random variable can be approximated by taking the empirical mean of independent samples of the variable. When the probability distribution of the variable is parametrized, mathematicians often use a Markov Chain Monte Carlo sampler, the central idea is to design a judicious Markov chain model with a prescribed stationary probability distribution. That is, in the limit, the samples being generated by the MCMC method will be samples from the desired distribution, by the ergodic theorem, the stationary distribution is approximated by the empirical measures of the random states of the MCMC sampler. In other problems, the objective is generating draws from a sequence of probability distributions satisfying a nonlinear evolution equation, in other instances we are given a flow of probability distributions with an increasing level of sampling complexity. These models can also be seen as the evolution of the law of the states of a nonlinear Markov chain. In contrast with traditional Monte Carlo and Markov chain Monte Carlo methodologies these mean field particle techniques rely on sequential interacting samples, the terminology mean field reflects the fact that each of the samples interacts with the empirical measures of the process. Monte Carlo methods vary, but tend to follow a particular pattern, generate inputs randomly from a probability distribution over the domain. Perform a deterministic computation on the inputs, for example, consider a circle inscribed in a unit square. Given that the circle and the square have a ratio of areas that is π/4, uniformly scatter objects of uniform size over the square. Count the number of objects inside the circle and the number of objects. The ratio of the two counts is an estimate of the ratio of the two areas, which is π/4, multiply the result by 4 to estimate π. In this procedure the domain of inputs is the square that circumscribes our circle and we generate random inputs by scattering grains over the square then perform a computation on each input. Finally, we aggregate the results to obtain our final result, there are two important points to consider here, Firstly, if the grains are not uniformly distributed, then our approximation will be poor. Secondly, there should be a number of inputs
15.
Monte Carlo integration
–
In mathematics, Monte Carlo integration is a technique for numerical integration using random numbers. It is a particular Monte Carlo method that computes a definite integral. While other algorithms usually evaluate the integrand at a regular grid and this method is particularly useful for higher-dimensional integrals. There are different methods to perform a Monte Carlo integration, such as sampling, stratified sampling, importance sampling, Sequential Monte Carlo. In numerical integration, methods such as the Trapezoidal rule use a deterministic approach, Monte Carlo integration, on the other hand, employs a non-deterministic approach, each realization provides a different outcome. In Monte Carlo, the outcome is an approximation of the correct value with respective error bars. This is because the law of large numbers ensures that lim N → ∞ Q N = I, given the estimation of I from QN, the error bars of QN can be estimated by the sample variance using the unbiased estimate of the variance. V a r ≡ σ N2 =1 N −1 ∑ i =1 N2. Which leads to V a r = V2 N2 ∑ i =1 N V a r = V2 V a r N = V2 σ N2 N, as long as the sequence is bounded, this variance decreases asymptotically to zero as 1/N. The estimation of the error of QN is thus δ Q N ≈ V a r = V σ N N and this is standard error of the mean multiplied with V. While the naive Monte Carlo works for simple examples, this is not the case in most problems, a large part of the Monte Carlo literature is dedicated in developing strategies to improve the error estimates. In particular, stratified sampling—dividing the region in sub-domains—, and importance sampling—sampling from non-uniform distributions—are two of such techniques, a paradigmatic example of a Monte Carlo integration is the estimation of π. Consider the function H = {1 if x 2 + y 2 ≤10 else, notice that I π = ∫ Ω H d x d y = π. Keep in mind that a random number generator should be used. On each recursion step the integral and the error are estimated using a plain Monte Carlo algorithm, if the error estimate is larger than the required accuracy the integration volume is divided into sub-volumes and the procedure is recursively applied to sub-volumes. The ordinary dividing by two strategy does not work for multi-dimensions as the number of sub-volumes grows far too quickly to keep track, instead one estimates along which dimension a subdivision should bring the most dividends and only subdivides the volume along this dimension. The popular MISER routine implements a similar algorithm, the MISER algorithm is based on recursive stratified sampling. This technique aims to reduce the overall integration error by concentrating integration points in the regions of highest variance, the MISER algorithm proceeds by bisecting the integration region along one coordinate axis to give two sub-regions at each step
