Implementation of Self-Organizing Maps for Mesh Generation

Note!?The full version of the article and the corresponding MATLAB scripts are available on my?GitHub.

Self-Organizing Map (SOM) is an unsupervised approach in machine learning used for dimensionality reduction and clustering unlabeled data points by building a self-organizing network of neurons. In clustering, a huge amount of data points is divided into a limited number of clusters based on their similarity and proximity. Indeed, each cluster is representative of multiple data points with similar characteristics. The mesh generation process can be considered a clustering problem since each computational cell (i.e., cluster) is representative of many physical points (or an infinite number of points due to the continuum paradigm) that exist in it. Accordingly, the SOM approach has the potential to generate an appropriate grid for a computational domain by clustering it into a limited number of computational cells. The unstructured grid with triangular cells is considered in the current article.?

How SOM Works?

The SOM starts by creating a set of so-called "neurons" randomly located in the domain of interest. The available data points in the dataset are introduced to the SOM one by one, causing the neurons to change their positions based on the induced gravity force. For each data point introduced to the SOM, the nearest neuron (called the winner neuron) will have the maximum displacement. Other neurons receive a marginal shift in the location based on their distance to the introduced data point. The n-dimensional Euclidean distance is usually used to measure the proximity of neurons to the data points.

The following formula indicates the procedure of updating the neurons' locations based on the original data points, where f_mn indicates the lateral feedback coefficient of the algorithm. the term g(t) is a dissipating term that reduces the gravity effect with time (i.e., iterations) to ensure the stability of the algorithm.

The following figure depicts the schematic of the SOM algorithm.

Mesh Generation with SOM

For mesh generation with SOM, we need to generate a random sample of the point in the computational domain (2D or 3D) and introduce them to the SOM algorithm to build the grid nodes (i.e., SOM neurons). In mesh generation, it is always important to control the mesh size, which can be achieved by limiting the number of SOM neurons. The following figures illustrate mesh generation with SOM for two different grid sizes on a simple rectangular domain.

Another requirement of mesh generation is the ability to increase the mesh density over important locations where a sharp gradient in a physical property happens. For instance, the boundary layer in fluid mechanics, or a region with tension concentration would be a candidate for a higher mesh density. For this purpose, there should be a distribution function with a higher probability for the regions of interest for selecting data points from the domain. the figure below depicts the implementation of a nonuniform distribution function for generating a mesh with a higher density in a certain region.

If you are interested in the procedure of selecting random points from an arbitrary distribution function, please read my article about How to Generate a Random Variable Picked from a Given Probability Distribution.

Some sample results of the implementation of SOM in mesh generation are provided in the following figures. The full version of the article in conjunction with the corresponding MATLAB scripts is available on my GitHub account.