"Those who cannot remember the past, are condemnded to repeat it", Dynamic Programming

Dynamic Programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions using a memory-based data structure (array, map,etc).

Each of the subproblem solutions is indexed in some way, typically based on the values of its input parameters, so as to facilitate its lookup. So the next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time. 

For example, the creation of phylogenetic trees once DNA is known can be tackled easily with Dynamic Programming:

 

Click here for a complete list of problems that can be solved with Dynamic Programming.

 

 

deep space computing AG is able to implement solutions to problem that can be solved with Linear Programming. We use the GLPK (GNU Linear Programming Kit) to implement our solutions. As soon as there will be Linear Solvers running on GPUs, deep space computing is committed to deliver them to customers through the Computational Cluster.

Center of the model is an objective function expressed over a feasible region. The objective function is linear and is expressed with the linear coefficient vector c . 

The feasible region is a convex polyhedron with the same dimensionality of c , bounded by a set of linear inequality constraints representing limits in the model. Additional linear equalities define conservation laws and current stati of the system. All linear equalities and inequalities are expressed in the matrix A and vector b.

The linear programming algorithm CPLEX, originally developed at IBM, finds a point in the polyhedron where this function has the largets value if such a point exists.

Before running the algorithm, it is necessary to convert the problem in augmented form. This form introduces non-negative slack variables to replace inequalities with equalities in the constraints. The problems can then be written in the following block matrix form:

where xs are the newly introduced slack variables, and Z is the variable to be maximized.

Here a simple example of a hydro power plant optimization done by deep space with GLPK:

 

 

 

 

deep space computing offers two services around environmental monitoring, one being health monitoring and the other house automation.

Environmental Monitoring

deep space computing can check household devices and rooms in a house and verify that the following environmental parameters do not present a danger to health of people living in the building. 

Environmental Parameter  Device Unit  Acceptable Range Typical Tests on

 Radioactivity through Geiger Counter

 microsievert per hour

  • Cosmic radiation: 1 millisievert/year 
  • Additional exposure: 2 millisievert/year due to other factors
  • Maximal exposure for a worker in a nuclear plant: 20 millisievert per year

 Living room Sleeping room, Ceiling, Basement (Radon)

 Electric Field

   Volt per Meter  0-15 V/m  Microwave Oven, Induction Cooker, Computer Screen, Television, Sleeping room, Electric Lines and Plug Sockets
 Magnetic Field same as previous row   microTesla  0-5 microTesla same as previous row 
 Thermal Imaging    Celsius Depending on room and purpose  Identify thermal leaks in buildings, check devices that run 24 hours a day for components running too hot

 

 

House Automation

deep space computing collected knowledge about domotics while running its Computational Cluster. It now offers services about advanced house automation to customers using the Homematic system.

 

deep space computing AG builds computers with several graphic cards supporting CUDA, a programming model invented by NVidia to support parallel programming.

The software stack includes:

Most computers in the Computational Cluster can be defined as CUDA Supercomputers, as they are computers featuring several graphic cards. 

Orbit Reconstruction Simulation and Analysis

deep space computing developed a software to simulate planetary orbits by porting C++ source code of the ORSA project by Pasquale Tricarico to Delphi. In the screenshot below it is possible to see the irregular orbit of Iapetus around Saturn. More screenshots and details are available on the project site.

Climate Simulation

deep space computing developed a simple software to simulate climate based on a Science in School article. In the screenshot below it is possible to see how the simulated ashes of volcano Eyjafjallajökull move toward Europe and block aircraft traffic. More screenshots and details are availabe on the project website

In the screenshot below one can see an attempt to model CO2 production over industrial countries and how wind spreads CO2 concentration over the globe: