List of Algorithms

Arnoldi's method

Arnoldi’s method is an algorithm that was originally used to reduce an arbitrary matrix \(A \in \mathbb{C}^{n \times n}\) to Hessenberg form. However, it can also be used to approximate eigenvalues as shown in the following.

Finite Difference Methods

Finite different methods (FDM) is a general numerical method for solving ordinary differential equations (ODE) or partial differential equations (PDE) raising from approximating (non-)linear physical and mathematical problems. The original differential equation is solved on a grid of points where finite difference formulas are used to approximate the solution using the surrounding values. This way, we can transform a differential equation into a system of algebraic equations to solve.

Programs: OpenMP Critical ·

Finite Element Method

Finite Element Method (FEM) is a general numerical method for solving physical problems in engineering analysis and design. It is used for modelling of a continuum in steady-state, propagation (transient), and eigenvalue problems in many domains, e.g. structural mechanics, CFD, thermodynamics, electromagnetics, etc. It is a robust universal method able to solve large complex systems for the price of relatively high computational demands.

Fast Fourier Transformation

A Fast Fourier Transform (FFT) is an algorithm that computes the Discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). The algorithm can be applied to both real (\(\mathbb{R}\)) and complex (\(\mathbb{C}\)) input, and can result in both a real or a complex output. This is because it is possible to express an even-length real-input DFT as a complex DFT of half its length. From a mathematical perspective a Discrete Fourier Transform (DFT) transforms a sequence of \(N\) complex numbers from one space to another sequence of complex numbers in the reciprocal space.

Programs: FFTXlib · juKKR kloop ·

Generalized minimal residual method (GRMRES)

The generalized minimal residual method (GMRES) is an iterative method for the numerical solution of a nonsymmetric system of linear equations. The method approximates the solution by the vector in a Krylov subspace with minimal residual. The algorithm builds an orthogonal basis of the Krylov subspaces and then solves the least square problem to find this vector. To built an orthogonal basis, one may use the Arnoldi iterations. After the orthogonalization, we solve the least square by the QR decomposition, where the Given rotation is used.

Programs: BEM4I miniApp · CalculiX solver ·

Link Cell Algorithm

The link cell algorithm comes from the domain of Molecular Dynamics Simulations. Here, for a set of molecules, pairwise interactions have to be computed under the constrain of a limited interaction range. The idea of the link cell algorithm is to divide the simulation domain into cells and sorting the molecules into the cells based on their spatial position. Traversing over interaction partners is then achieved by iterating over the molecules in the neigbouring cells instead of the entire domain. In this way the link cell algorithm reduces the original O(N^2) problem to an O(N) problem.