Dynamic Programming
"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.
Linear 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 Simplex, 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:
Environmental Monitoring
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 |
|
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.
CUDA Supercomputers
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:
- Keras with Google's Tensorflow 2.0 for Deep Learning
- GNU Linear Programming Kit for Linear Programming
- Latest versions of Ubuntu Linux or Windows as Operating System
- CUDA Drivers
Most computers in the Computational Cluster can be defined as CUDA Supercomputers, as they are computers featuring several graphic cards.
Scientific Computing
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: