CVT_BASIS_FLOW
PDE Model Reduction by Voronoi Techniques


CVT_BASIS_FLOW is a FORTRAN90 program which extracts representative solution modes of a set of solutions to a fluid flow PDE.

The selection process uses K-Means clustering, which can be considered to be a discrete version of the CVT algorithm (Centroidal Voronoi Tessellation).

The selected modes will generally be "well spread out" in the space spanned by the set of solutions. Such a set of modes might be useful as a basis for a low-dimensional approximation of new solutions, as long as it may be assumed that these new solutions do not have significant components that were not evident in the original solution data.

Specifically, a partial differential equation (PDE) has been defined, specifying the time dependent flow of a fluid through a region. The PDE specification includes a parameter ALPHA whose value strongly affects the behavior of the flow. The steady state solution S0 is computed for a particular value of ALPHA. Then the time dependent problem is solved over a fixed time interval, with ALPHA varying from time to time. A set of several hundred solutions S(T(I),ALPHA(I)) are saved.

The need is to try to extract from this solution data the typical modes of behavior of the solution. Such a set of modes may then be used as a finite element basis that is highly tuned to the physics of the problem, so that a very small set of basis functions can be used to closely approximate the behavior of the solution over a range of values of ALPHA.

The method of extracting information from the solution data uses a form of K-Means clustering. The program will try to cluster the data, that is, to organize the data by defining a number of cluster centers, which are also points in N dimensional space, and assigning each record to the cluster associated with a particular center.

The method of assigning data aims to minimize the cluster energy, which is taken to be the sum of the squares of the distances of each data point from its cluster center.

In some contexts, it makes sense to use the usual Euclidean sort of distance. In others, it may make more sense to replace each data record by a normalized version, and to assign distance by computing angles between the unit vectors.

Because the data comes from a finite element computation, and the results may be used as a new reduced basis, it may be desirable to carry out mass matrix preconditioning of the data, so that output vectors (cluster generators) are pairwise orthogonal in the L2 inner product (integration of the product of the finite element functions over the domain).

Because the results may be used as a new reduced basis, it may be desirable, once the results have been computed, to apply a Gram-Schmidt orthogonalization procedure, so that the basis vectors have unit Euclidean norm, and are pairwise orthogonal.

The current version of the program assumes that a steady state solution SS of the PDE is known, and that a multiple of SS is to be subtracted from each solution vector before processing.

FILES: the program assumes the existence of the following files: (the actual names of the files are specified by the user at run time. The names used here are just suggestions.)

INPUT: at run time, the user specifies:

OUTPUT: the program computes basis_num basis vectors. The first vector is written to the file gen_001.txt; again, the output vectors are written with two values per line, since this represents the two components of velocity at a particular node.

Linkage:
The program calls numerous LAPACK routines for the processing of the mass matrix. The text for these routines is not included in the source code. The compiled program must be linked to the LAPACK library.

Licensing:

The computer code and data files described and made available on this web page are distributed under the MIT license

Languages:

CVT_BASIS_FLOW is available in a FORTRAN90 version.

Related Data and Programs:

BRAIN_SENSOR_POD, a MATLAB program which applies the method of Proper Orthogonal Decomposition to seek underlying patterns in sets of 40 sensor readings of brain activity.

CVT_BASIS, a FORTRAN90 program which is similar to CVT_BASIS_FLOW, but handles any general set of data vectors.

CVTP, a FORTRAN90 library which creates a CVTP, that is, a Centroidal Voronoi Tessellation on a periodic domain.

POD_BASIS_FLOW, a FORTRAN90 program which is similar to CVT_BASIS_FLOW, but uses POD methods to extract representative modes from the data.

Reference:

  1. Franz Aurenhammer,
    Voronoi diagrams - a study of a fundamental geometric data structure,
    ACM Computing Surveys,
    Volume 23, Number 3, pages 345-405, September 1991.
  2. John Burkardt, Max Gunzburger, Hyung-Chun Lee,
    Centroidal Voronoi Tessellation-Based Reduced-Order Modelling of Complex Systems,
    SIAM Journal on Scientific Computing,
    Volume 28, Number 2, 2006, pages 459-484.
  3. John Burkardt, Max Gunzburger, Janet Peterson and Rebecca Brannon,
    User Manual and Supporting Information for Library of Codes for Centroidal Voronoi Placement and Associated Zeroth, First, and Second Moment Determination,
    Sandia National Laboratories Technical Report SAND2002-0099,
    February 2002.
  4. Qiang Du, Vance Faber, Max Gunzburger,
    Centroidal Voronoi Tessellations: Applications and Algorithms,
    SIAM Review, Volume 41, 1999, pages 637-676.
  5. Lili Ju, Qiang Du, Max Gunzburger,
    Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations,
    Parallel Computing,
    Volume 28, 2002, pages 1477-1500.
  6. Wendy Martinez, Angel Martinez,
    Computational Statistics Handbook with MATLAB,
    Chapman and Hall / CRC, 2002.

Source Code:

Examples and Tests:

PDE solution datasets you may copy include:

This program has been run with a number of different datasets, and with various requirements as to normalization and so on. The purpose of most of the runs is to find a generator set of given size. The input and output of each run is stored in a separate subdirectory.

Now we worked with 500 flow solutions in the TCELL region. We subtract 5/3 of steady solution from 1-250, and 1/3 from 251 through 500. We DON'T normalize the PDE solutions.

The next set of runs worked with 500 flow solutions in the TCELL region. We subtract 5/3 of steady solution from 1-250, and 1/3 from 251 through 500. Now we NORMALIZE the PDE solutions before processing them.

The next set of runs worked with 500 flow solutions in the TCELL region. We subtract 5/3 of steady solution from 1-250, and 1/3 from 251 through 500. We DON'T normalize the PDE solutions. We discard half the data, keeping the EVEN steps, 2, 4, ..., 500.

The next set of runs works with 500 flow solutions in the INOUT region. We subtract 5/3 of steady solution from 1-250, and 1/3 from 251 through 500. We DON'T normalize the PDE solutions.

The next set of runs works with 500 flow solutions in the INOUT region. We subtract 5/3 of steady solution from 1-250, and 1/3 from 251 through 500. We NORMALIZE the PDE solutions.

The next set of runs works with 500 flow solutions in the INOUT region. We subtract 5/3 of steady solution from 1-250, and 1/3 from 251 through 500. We DON'T normalize the PDE solutions. Before we proceed, we DROP the ODD numbered PDE solutions

The next set of runs works with 500 flow solutions in the CAVITY region. We subtract 5/3 of steady solution from 1-250, and 1/3 from 251 through 500. We DON'T normalize the PDE solutions.

The next set of runs works with 500 flow solutions in the CAVITY region. We subtract 5/3 of steady solution from 1-250, and 1/3 from 251 through 500. We NORMALIZE the PDE solutions.

The next set of runs works with 500 flow solutions in the CAVITY region. We subtract 5/3 of steady solution from 1-250, and 1/3 from 251 through 500. We DON'T normalize the PDE solutions. Before we proceed, we DROP the ODD numbered PDE solutions

The next set of runs works with 500 flow solutions in the CAVITY region. We subtract 5/3 of steady solution from 1-250, and 1/3 from 251 through 500. We normalize the PDE solutions. We use MASS MATRIX preconditioning.

The next set of runs works with 500 flow solutions in the INOUT region. We subtract 5/3 of steady solution from 1-250, and 1/3 from 251 through 500. We normalize the PDE solutions. We use MASS MATRIX preconditioning.

The next set of runs works with 500 flow solutions in the TCELL region. We subtract 5/3 of steady solution from 1-250, and 1/3 from 251 through 500. We normalize the PDE solutions. We use MASS MATRIX preconditioning.

The next set of runs works with 500 flow solutions in the CAVITY region. We subtract 5/3 of steady solution from 1-250, and 1/3 from 251 through 500. We do not normalize the PDE solutions. We use MASS MATRIX preconditioning.

The next set of runs works with 500 flow solutions in the INOUT region. We subtract 5/3 of steady solution from 1-250, and 1/3 from 251 through 500. We do not normalize the PDE solutions. We use MASS MATRIX preconditioning.

The next set of runs works with 500 flow solutions in the TCELL region. We subtract 5/3 of steady solution from 1-250, and 1/3 from 251 through 500. We do not normalize the PDE solutions. We use MASS MATRIX preconditioning.

The next set of runs works with 500 flow solutions in the CAVITY region. We subtract 5/3 of steady solution from 1-250, and 1/3 from 251 through 500. We do not normalize the PDE solutions. We drop the odd numbered data vectors. We use MASS MATRIX preconditioning.

The next set of runs works with 500 flow solutions in the INOUT region. We subtract 5/3 of steady solution from 1-250, and 1/3 from 251 through 500. We do not normalize the PDE solutions. We drop the odd numbered data vectors. We use MASS MATRIX preconditioning.

The next set of runs works with 500 flow solutions in the TCELL region. We subtract 5/3 of steady solution from 1-250, and 1/3 from 251 through 500. We do not normalize the PDE solutions. We drop the odd numbered data vectors. We use MASS MATRIX preconditioning.

The next set of runs works with 800 flow solutions in the INOUT2 region. We subtract 5/3 of steady solution from 1-400, and 1/3 from 401 through 800. We DON'T normalize the PDE solutions.

The next set of runs works with 800 flow solutions in the INOUT2 region. We subtract 5/3 of steady solution from 1-400, and 1/3 from 401 through 800. We DON'T normalize the PDE solutions. We use mass matrix preconditioning.

The next set of runs works with 40 scalar flow solutions in the one-dimensional BURGERS equation.

List of Routines:

You can go up one level to the FORTRAN90 source codes.


Last revised on 12 November 2006.