The International Graduiertenkolleg IGK 710 "Complex processes: Modeling, Simulation and Optimization"
about IGK     
study program     

Prof. Dr. Dr.h.c. H.G. Bock
Graduiertenkolleg at IWR
University of Heidelberg
INF 368 Room 406
69120 Heidelberg
Phone: +49-6221/54-4944
Fax: +49-6221/54-8810


Possible Dissertation Projects

Direct Numerical Simulation of Two-Phase Flow Through Porous Media

next top

Supervisors: Bastian (IWR Heidelberg), Roth (IUP Heidelberg)

Keywords:Multiscale, Multilevel, Parallel Computing

Background: Multiphase flow is an important process arising in porous media with applications in the exploitation of natural resources or environmental problems of contaminated site remediation. Simulation of multiphase flow on large scales, as required by the applications above, is based on macroscopic models (Richards equation, extended Darcy law) where the interaction of the fluids with each other and the the pore-scale geometry is incorporated into nonlinear algebraic couplings.

Research Goal: In this project we aim at computing macroscopic parameters of incompressible two-phase flow from direct numerical simulation on the pore-scale in order to understand in more detail the influence of the pore-scale on the macroscopic parameters. One outcome would be a more rigorous understanding of the hysteresis of the capillary pressure saturation relationship, [1]. Numerical simulation of two-phase flow on the pore-scale has so far been accomplished with network models and Lattice-Boltzmann methods. The former oversimplifies the complicated pore-scale geometry of natural porous media while the latter method has so far not been able to treat water-gas flows with the true values for density and viscosity. We therefore attempt to numerically solve the governing PDE for two-phase flow in a true pore-scale geometry. This is possible due to recent advances in experimental techniques and high performance computing. High resolution X-ray tomography or the Nuclear Magnetic Resonance imaging technique are able to acquire 3D images of the pore space with a resolution of 1 µm while large scale parallel supercomputers allow the simulation of nonlinear time-dependent partial differential equations with up to 1 billion degrees of freedom per time step. We therefore think to be able to compute a volume containing 503...1003 grains.

The system of model equations is solved using a combination of level set and volume-of-fluid method. The complex geometry is tackled by using discontinuous Galerkin finite elements, [2], [3], on a structured three-dimensional mesh intersected with the pore space. This avoids the mesh generation issue and allows a massively parallel implementation.

This project contributes to the main topics of research in the Graduiertenkolleg as the upscaling of complex microscale process is considered and state-of-the-art mathematical techniques including multigrid methods and parallel computing are developed further to promote the application field.

[1] H.J. Vogel and K. Roth Quantitative morphology and network representation of soil pore structure
Advances in Water Resources, 24, 233-242 (2001).
[2] P.Bastian Higher order discontinuous Galerkin methods for flow and transport in porous media
in E. Bänsch, ed., Challenges in Scientific Computing -- CISC 2002, number 35 in LNCSE, 1--22, 2003.
[3] P. Bastian and B. Riviùre Superconvergence and H(div)-projection for discontinuous Galerkin methods
Int. J. Numer. Meth. Fluids., 42:1043--1057, 2003.

Efficient Parallel Inverse Modeling of Multiphase Transport in Variably Saturated Porous Media

next top

Supervisors: Bastian (IWR Heidelberg), Schlöder (IWR Heidelberg)

Keywords: All-at-once Optimization, Multilevel Methods, Parallel Computing

Background: The determination of hydraulic parameters necessary for the quantitative modeling of flow and transport in porous media is often tedious and time consuming. Direct measurements of the relative permeability/saturation function are hardly possible. For homogeneous porous media a combination of multistep outflow (MSO) experiments and inverse modeling is often the method of choice, [1], [2]. However, natural porous media are often heterogeneous. Our preliminary investigations showed that parameter estimation might still be possible if the sample is composed of a limited number of materials and their structural arrangement is known, e.g. from X-ray tomography, [2], [3].

Research Goal: Aim of this project is the development of efficient numerical inverse modeling methods for 3-D multiphase problems with data from MSO experiments. Basis of the methods will be a suitable multiple shooting parametrization and a generalized Gauss-Newton approach, [1], [4]. Essential will be the exploitation of parallelism on all levels, in particular in the generation of derivatives and the solution of the large-scale linear systems of discretized PDE. Alternative realizations of internal numerical differentiation based on forward and adjoint modes will be developed in order to determine the derivative generation method with lowest computational complexity. The algorithms will be implemented in such a way that models realized in the Distributed and Unified Numerics Environment Dune can easily be used. This allows for parameter estimation of the whole class of applications realizable within that framework.

[1] A. E. Altmann-Dieses, J. P. Schlöder, H. G. Bock, O. Richter: Optimal experimental design for parameter estimation in column outflow experiments,
Water Resources Research, 38(10), 1186--1196, 2002.
[2] S. I. Hwang and S. E. Powers. Estimating unique soil hydraulic parameters for sandy media from multi-step outflow experiments,
Advanced Water Resources, 26(4), 445--456, 2003.,
[3] O. Ippisch, A. Samouëlian, H.-J. Vogel, P. Bastian. Estimation of hydraulic parameters for heterogeneous porous media,
EGS 1st General Assembly, Nice, France, 25-30 April 2004.
[4] S. Körkel, E. Kostina, H. G. Bock and J. P. Schlöder. Numerical methods for optimal control problems in design of robust optimal experiments for nonlinear dynamic processes,
Optimization Methods and Software, 19, 327--338, 2004.

Nonlinear Mixed Integer Optimal Control

next top

Supervisors: Bock (IWR Heidelberg), Reinelt (IfI Heidelberg)

Keywords: Mixed Continuous-Discrete Optimization, Bio-Chemistry

Background: The project aims at the development of numerical methods for optimization problems that involve nonlinear differential algebraic equation models and decision variables that are both reals and integers, and that may be time dependent controls or time constant design parameters. This problem class is very important in applications, but its efficient numerical solution still presents a major difficulty for real world problems. To name just two examples from process engineering, design and operation of coupled distillation columns involves integer design variables that determine which trays are coupled, as well as continuous controls like flux rates. On the other hand, in the optimal scheduling and control of batch processes, time dependent integer controls arise together with continuous controls. The numerical solution of this type of problem is challanging due to the fact that algorithmic elements from dynamic process optimization need to be combined with techniques from the field of nonlinear mixed integer optimization.

Research Goals: The aim of the project is the development of an optimal control package for generic mixed integer control problems that is applicable to large scale nonlinear DAE models with continuous and integer decision variables. The algorithms shall not aim at finding global minima but shall be based on fast heuristics. These heuristics will be based on concepts from linear and nonlinear mixed integer optimization (branch-and-bound, cutting planes, generalized Benders decomposition) as well as on ideas from optimal control (bang bang solutions, indirect approach, homotopy and penalty methods, efficient derivative generation).

Besides applications in optimization problems in engineering, the algorithms may also be applied to model identification problems from cell biology, where measurement data shall be optimally reproduced by differential equation models with unknown structure, depending on the existence or non-existence of reaction pathways from a given set.

[1] S. Engell, A. Märkert, G. Sand, R. Schultz and C. Schulz: Online scheduling of multiproduct batch plants under uncertainty,
In M. Grötschel, S. O. Krumke and J. Rambau, editors, Online Optimization of Large Scale Systems: State of the Art, pages 649--678. Springer, 2001.
[2] I. E. Grossmann: Review of nonlinear mixed-integer and disjunctive programming techniques,
Optimization and Engineering, 3:227--252, 2002.
[3] M. Jünger and G. Reinelt: Combinatorial optimization and integer programming,
In U. Derigs, editor, Encyclopedia of Life Support Systems EOLSS, 6.5: Optimization and Operations Research, pages 321--327. Eolss Publishers, 2004.
[4] S. Sager, M. Diehl, H. G. Bock and G. Reinelt: Numerical methods for optimal control with binary control functions,
Poster at 12th French-German-Spanish Conference on Optimization, Avignon, September 2004.
[5] O. Stein, J. Oldenburg and W. Marquardt: Continuous reformulations of discrete-continuous optimization problems,
Comp. & Chem. Eng., 28(10):1951 -- 1966, 2004.

Optimal Control of Time Dependent Partial Differential Algebraic Equation (PDAE) Models

next top

Supervisors: Bock (IWR Heidelberg), Rannacher (IAM Heidelberg)

Keywords: All-at-once Optimization, Adaptivity

Background: Constrained optimal control problems in nonlinear time dependent partial differential algebraic equations (PDAE) pose important challenges for the development of numerical algorithms. To ensure a reliable and efficient solution to inequality constrained problems, algorithms are needed which employ a direct simultaneous approach that combines adaptive grid refinement techniques such as developed in [1] in time and space, inexact linear algebra solvers, and modern nonlinear optimization methods, with state-of-the-art techniques for efficient derivative generation. The combination of all these techniques has not been accomplished yet for realistic problems.

Research Goal: The algorithms to be developed will use a direct multiple shooting parameterization that divides the time horizon of interest into subintervals, on each of which adaptive grid refinement in time and space and important computations can be performed independently. In contrast to direct multiple shooting for differential algebraic equations, where the parameterized optimization problems are finite dimensional, adaptivity in space introduces the need to formulate the optimization problems in a function space setting, and continuity conditions need to be imposed in a weak formulation, [2]. The numerical solution of the resulting optimization problems in function space shall be achieved by tailored variants of sequential quadratic programming (SQP) with inexact Jacobians and inexact linear system solvers, [3]. For this aim it is of crucial importance that the Lagrange gradient can accurately and efficiently be computed. This shall be achieved by suitable generalization of adjoint derivative calculation methods similar to the reverse mode of automatic differentiation. A major focus will be the treatment of inequalities in the presence of inexact derivatives. An important aim of the project is the development of a software package that allows to treat generic time dependent optimal control problems in PDAE and can be easily coupled to existing modelling environments that are used in industry. Furthermore, the algorithms shall be designed in such a way that an extension to real-time optimization and nonlinear model predictive control is possible.

[1] R. Becker, H. Kapp, and R. Rannacher: Adaptive finite element methods for optimal control of partial differential equations: Basic concepts,
SIAM J. Control Optimization, 39:113--132, 2000.
[2] H. G. Bock, M. Diehl, E. A. Kostina and J. P. Schlöder: Constrained optimal feedback control of systems governed by large differential algebraic equations,
In Real-Time and Online PDE-Constrained Optimization (L. Biegler, et al., eds.), 2004, submitted.
[3] H. G. Bock, W. Egartner, W. Kappis and V. Schulz: Practical shape optimization for turbine and compressor blades by the use of PRSQP methods,
Optimization and Engineering, 3(4):395--414, 2002.

Numerical Solution of Large Eigenvalue Problems for Modeling Intermolecular Coulombic Decay

next top

Supervisors: Cederbaum (PCI Heidelberg), Rannacher (IAM Heidelberg)

Keywords: Multilevel, Adaptivity, Parallel Computing, Quantum Dynamics

Background: Several years ago we have predicted theoretically a new fundamental decay mechanism [1,2] termed Interatomic Coulombic Decay (ICD). This novel decay mechanism becomes the dominant decay channel once the excited atom is placed in an environment. Very recently, the ICD has been verified experimentally [3]. Currently, several groups are measuring the ICD with great success. To model the ICD, large complex symmetric matrices (n>105) have to be constructed and diagonalized. The classical Krylov-space approach is by far too slow for calculations on realistic systems. Other methods should be developed and utilized. The numerical solution of the large eigenvalue problem will provide the input data for the dynamic modelling of the total ICD process.

Research Goal: The classical Krylov-space methods require particularly for the computation of eigenvalue clusters of complex matrices such enormous CPU-times that parameter studies are hardly possible. This barrier can only be broken by the combination of proven Lanczos-Arnoldi methods, [4], with multilevel techniques. A further improvement in efficiency is reached by 'shift-and-invert' strategies for the computation of interior eigenpairs. First experiences with such a combined approach are reported in [5], where it is shown that large-scale eigenvalue problems with up to millions of unknowns can be efficiently treated on normal workstations. This method has since been further developed for computing groups of eigenvalues. By exploiting the inherent parallel structures of this algorithm the size of the manageable problems can be further increased.

Another performance enhancement could be reached by goal-oriented model reduction by adaptive choice of the Galerkin ansatz in the discretization. This approach is commonly used in the Galerkin finite element method for solving partial differential equations but has not been applied yet to spectral-type Galerkin methods. This approach could also be useful in other quantum dynamical simulations of large configurations which are presently not possible by standard methods.

[1] L. S. Cederbaum, J. Zobeley and F. Tarantelli: Giant intermolecular decay and fragmentation of clusters,
Phys. Rev. Lett. 79, 4778 (1997).
[2] R. Santra and L. S. Cederbaum: Coulombic energy transfer and triple ionization in clusters,
Phys. Rev. Lett. 90, 153401 (2003).
[3] S. Marburger, O. Kugeler, U. Hergenhahn and T. Moeller: Experimental evidence for interatomic Coulombic decay in Ne clusters,
Phys. Rev. Lett. (2003).
[4] V. Heuveline and M. Sadkane: Arnoldi-Faber method for large non-hermitian eigenvalue problems,
ETNA 5 (1997).
[5] V. Heuveline and C. Bertsch: On multigrid methods for the eigenvalue computation of non selfadjoint elliptic operators,
East-West J. Numer. Math. 8, 275--297(2000).

Multi--Dimensional Quantum Dynamics: Development of Efficient Algorithms, Parallelization

next top

Supervisors: Meyer (IWR Heidelberg), Bastian (IWR Heidelberg)

Keywords: Parallel Computing, Molecular Dynamics

Background: The numerical treatment of quantum dynamics of molecules with four or more atoms is a very difficult and numerically demanding problem. A very efficient method [1] for solving the time-dependent Schrödinger equation has been developed in the Theoretical Chemistry group. This multiconfiguration time-dependent Hartree (MCTDH) method shall be further developed and improved. This will allow us to solve the dynamics of larger molecules. The numerical-mathematical methods, e.g. integration schemes and representation techniques, used in MCTDH are to be improved.

Research Goals: Due to the high dimensionality of the problem the MCTDH algorithm is computationally very intensive and all possibilities of decreasing its run-time should be exploited. A very attractive and not yet explored way of improvement is parallelization. The IWR group has extensive experience in the parallelization of algorithms for the numerical solution of partial differential equations including adaptive parallel multigrid methods [2,3]. In [3] we demonstrated the solution of very large systems on the order of 1 billion equations on 400 processors of the IWR LINUX cluster. In a detailled analysis the inherent parallelism of the MCTDH algorithm will be explored and possible ways of improving parallelizability will be investigated. The aim of the project is a data-parallel implementation of the MCTDH algorithm for message passing architectures. Thus it will be portable to any type of parallel computer from cluster of PCs to supercomputers.

[1] M. H. Beck, A. Jäckle, G. A. Worth and H.-D. Meyer: The multiconfiguration time-dependent Hartree method: A highly efficient algorithm for propagating wavepackets,
Phys. Rep. 324(2000), 1--105.
[2] P. Bastian, R. Helmig: Efficient fully-coupled solution techniques for two-phase flow in porous media. Parallel multigrid solution and large scale computations.
Advances in Water Resources, 23, 199-216, 1999.
[3] P. Bastian, M. Droske, C. Engwer, R. Klöfkorn, T. Neubauer, M. Ohlberger, and M. Rumpf: Towards a unified framework for scientific computing.
Proc. 15th Conf. Domain Decomposition Methods (R. Kornhuber, et al.), LNCSE. Springer-Verlag, 2004.

Multiscale Modeling for Processes on Surfaces and in Channels of Membranes

next top

Supervisors: Jäger (IAM Heidelberg), Bastian (IWR Heidelberg)

Keywords: Multiscale Modeling, Biochemical Processes

Background: The transport of ions through channels of membranes is modeled mainly by diffusion-transport systems coupled by transition conditions, adapted to experimental data, [1]. Since detailed information on the processes on the surfaces and the channels of the membranes is available, macroscopic description should include this information. Multiscale modeling is providing the tools for this task. Assuming that the transported ions are changing distributions of charged molecules on the channel wall, W. Jäger and M. Neuss-Radu derived with new two scale techniques transmission conditions similar to those used by Choi and coauthors. There are no chemical reactions and processes on the surfaces considered, as it is necessary e.g. for the transport through nuclear pores of a cell. Special transporter molecules are used to move molecules through the membranes. In this project new mathematical methods have to be developed to derive a priori estimates for the strongly nonlinear differential equation on the microscopic level and to perform the homogenization limit,[2].

Research Goals: In this project new mathematical methods have to be developed to derive a priori estimates for the strongly nonlinear differential equation on the microscopic level and to perform the homogenization limit. The theoretical results will be incorporated into a numerical simulation code. The discontinuous Galerkin method [3] is especially suited to incorporate transmission conditions at interfaces in an efficient way because it computes fluxes at inter-element boundaries (local mass conservation) and is able to represent discontinuous functions. A method currently being developed in the Bastian group is able to handle geometrically complex interfaces between subdomains. The aim of the numerical part of this project is to extend this method by nonlinear transmission conditions. The resulting numerical code can then be applied to a variety of models in computational biology, e.g. cell nucleus interchange, which then also enables comparison with experimental data.

[1] Y. S. Choi, D. Resasco, J. Schaff, B. Slepchenko: Electrodiffusion of ions inside living cells,
IMA Journal of Applied Mathematics, 62, 227-244, (1999)
[2] H. Gajewski, I.V. Skrypnik: Existence and uniqueness results for reaction-diffusion processes of electrically charged particles,
Preprint 904, WIAS Berlin 2004
[3] P. Bastian: Higher order discontinuous Galerkin methods for flow and transport in porous media.
Challenges in Scientific Computing -- CISC 2002 (E. Bänsch, ed.), number 35 in LNCSE, 1-22, 2003.

Optimization with Partial Differential Equations by Adaptive Discretization and SQP-Multigrid Methods

next top

Supervisors: Rannacher (IAM Heidelberg), Bock (IWR Heidelberg)

Keywords: All-at-once Optimization, Adaptivity, Multilevel Methods

Background: As a result of the increasing demand for quantitatively correct description of technical processes the underlying mathematical models involve more and more complex partial differential equations. The optimization with such models necessarily requires the discretization of the state equation which limits the achievable accuracy. The control of this approximation can be accomplished by global `duality techniques' similar to those used in the optimization process itself. The resulting large discrete optimization problems have to be solved by efficient methods such as SQP-multigrid methods which largely exploit the structure of the problem inherited from the underlying continuous model.

Research goal: In this project the emphasize is on the economical discretization of PDE-constrained optimization as a crucial step towards problem-oriented model reduction. Starting point is the reformulation of the optimal control problem as a system of coupled PDE using the all-at-once approach. The coupling of fast optimization algorithms (reduced SQP-techniques) with a posteriori controlled discretization and multigrid iteration is to be developed for certain classes of optimization problems. Prototypical applications are sought in the optimal design of chemical flow reactors and heat exchangers. The main difficulty in these problems are the very anisotropic geometries and the strong nonlinearities due to the chemistry which require a fully implicit solution process. However, this is very expensive on fine discretization meshes and model reduction by systematic mesh adaptition is highly dersirable. A coupling of optimization and multilevel solution has been achieved in [1], while in [2] a general concept for combining optimization and mesh adaption has been developed. This adaptive discretization in optimization has been used in [3] for problems in optimal flow control such as drag minimization in pipe flow and the identification of viscosity parameters. The goal-oriented mesh adaptation results in an accurate discretization which is coarse enough to allow for the use of highly efficient optimization algorithms. First steps have also been done in the direction towards optimal control of time-dependent models using so-called `check pointing' techniques.

[1] T. Dreyer, H. G. Bock, V. H. Schulz and T. Speer: Optimum Shape Design of Turbine Blades:
Operations Research Proceedings 1995 (P. Kleinschmidt et al., eds), pp. 190-195, Springer, Heidelberg, 1996.
[2] R. Becker, H. Kapp and R. Rannacher: Adaptive finite element methods for optimal control of partial differential equations: basic concepts,
SIAM J. Optim.Control. 39, 113--132 (2000).
[3] R. Becker: Mesh adaptation for stationary flow control,
J. Math. Fluid Mech. 3, 317-341 (2001).

Numerical Simulation of Flows in Micro-Channels

next top

Supervisors: Rannacher (IAM Heidelberg), Wolfrum (PCI Heidelberg)

Keywords: Multiscale, Adaptivity

Background: Micro-technology belongs to the most promising new technologies. Its potential relies on the better efficiency and controllability of mechanical and chemical processes on small spatial scales. After the first development, one is now in the phase of exploring new applications and systematic system optimization, [1]. This has to be supported by numerical simulation and experimental validation. In this project special `diagnostic chips' and `DNA chips' are considered. In these systems fluid mechanical and chemical processes happen on the µm scale and nonstandard multiscale effects such as capillary forces and slip-boundary conditions become important. Their simulation and experimental diagnostics for system optimization possess high requirements which are not met by standard commercial software. Hence, new specially adapted numerical methods are to be developed.

Research goal: Goal of the numerical part of the project is the development of simulation tools for the design of micro-chips in which the flow of liquid and particle transport is driven by capillary or electro-magnetic forces. The software basis is provided by the flow-solver package `Gascoigne' ( which has been developed in the Rannacher group. For the simulation and optimization efficient methods as described in [2] will be used. These methods employ higher-order spatial and time discretization by finite elements and automatic mesh and time-step adaptativity. For handling the new physical effects such as travelling capillary fronts and slip boundary conditions, these methods will be combined with front tracking/level set techniques. In order to capture small-scale wall effects the combination with particle-oriented methods such as the Lattice-Boltzmann method may be necessary. For a validated simulation and optimization of micro-chips, quantitative data about wall properties and flow behavior are necessary. These will be provided by measurements of real configurations within a cooperation with the Wolfrum group, [3].

[1] H. Herwig: Flow and heat transfer in micro systems: Is everything different or just smaller?,
Z. Angew. Math. Mech. 82, 579-586 (2002).
[2] R. Becker, M. Braack, R. Rannacher: Numerical simulation of chemical reacting flows,
Proc. Workshop on Interdisciplinary Design and Simulation Tools for Micro- and Biomedical Fluid Applications, IMM,, 2000.
[3] M. Sauer, J. Wolfrum, et al. : Single molecule DNA sequencing in submicrometer channels:State of the art and future prospects,
J. Biotechnology 86, 181-201 (2001).

Adaptive Transition Networks for Molecular Systems

next top

Supervisors: Reinelt (IfI Heidelberg), Smith (IWR Heidelberg)

Keywords: Adaptivity, Multigrid, Molecular Dynamics

Background: he generation of transition networks for molecular systems is computationally expensive since the addition of each node and edge requires an optimization of a function in thousands of variables. It is thus vital to keep the transition network as small as possible while still obtaining sufficient information on the desired macroscopic properties. For the computation of effective rates, it is sufficient to have a good resolution at the highest separating energy barrier. This highest barrier corresponds to a minimum cut in a network where the edge weights correspond to the rates of microtransitions.

Research Goals: In this PhD project we aim at computing adaptive transition networks for small molecular systems with relatively low energy barriers (as e.g., short peptides). A very efficient method to generate transition networks, in the spirit of adaptive multigrid methods, is to generate nodes and edges at different levels of resolution, until the highest barrier of the network has converged. The required methodology will also be developed in this project.

For systems considered here, the macroscopic properties which are available with transition networks can also be obtained from a direct molecular dynamics simulation. The validity of the generated transition networks can therefore be tested by comparing the values of these properties.

The project is based on the complementary expertise of the two participating groups. The Smith group has expert knowledge in the analysis of protein structures (see e.g., [1]) and the Reinelt group provides the necessary algorithmic approaches from graph theory and combinatorial optimization (see e.g., [2]). Current work of the Phd student No\'e has already exhibited promising perspectives of integrating combinatorial optimization methods into analysis tools in molecular dynamics.

[1] F. Noe, S.M. Schwarzl, S. Fischer and J.C. Smith: Computational tools for analyzing structural changes in proteins in solution,
Applied Bioinformatics. 2(3): 11--17 (2003)
[2] M. Jünger and G. Reinelt Combinatorial Optimization and Integer Programming,
In: 6.5: Optimization and Operations Research, U. Derigs (ed.), Encyclopedia of Life Support Systems, EOLSS publishers, 321--327 (2004)

Exploring Protein Energy Landscapes: Optimization of Protein Conformational Pathways

next top

Supervisors: Smith (IWR Heidelberg), Bock (IWR Heidelberg)

Keywords: Direct Multiple Shooting, Molecular Dynamics

Background: Protein landscapes are highly complex hypersurfaces of many thousands of dimensions. Their exploration in particular involves finding optimal pathways for conformal transitions and thus gives insight into the kinetics of proteins, [1]. Determining lowest energy pathways between two conformations can be regarded as an optimal control problem. The high dimension of the underlying differential equation, its strong nonlinearity and the high number of controls provide hard challenges for the numerical methods.

Project Goals: This dissertation project will first investigate numerically appropriate formulations of the problem (selection of performance index, choice and parametrization of controls, boundary conditions, path and control constraints, etc) and consider direct optimal control methods for their numerical treatment.

Based on the direct multiple shooting method, [2,3], novel simultaneous optimization methods will be developed that take advantage of the structure of the problem, in particular of the large-scale differential equation system.

The new methods will be compared to currently used tools for the analysis of structural changes in proteins [1] and applied to problems investigated in the Smith group including the mechanism of muscle contraction and G-protein molecular switches.

[1] F. Noe, S. M. Schwarzl, S. Fischer and J. C. Smith (2003): Computational tools for analysing structural changes in proteins in solution}, in: Appl Bioinformatics, vol 2, pp S11-S17.
[2] D. B. Leineweber, I. Bauer, H. G. Bock and J. P. Schlöder (2003) : An efficient multiple shooting based reduced SQP strategy for large-scale dynamic process optimization - part I: theoretical aspects,
Comput. Chem. Engng. 27, pp. 157-166.
[3] A. Schäfer (2004): Effiziente reduzierte Newton-ähnliche Verfahren zur Behandlung hochdimensionaler strukturierter Optimierungsprobleme mit Anwendung bei biologischen und chemischen Prozessen, Dissertation, Uni Heidelberg.

Multiscale Modeling of Chromatin

next top

Supervisors: Langowski (DKFZ Heidelberg), Smith (IWR Heidelberg)

Keywords: Model Reduction, Parallel Computing, Molecular Dynamics

Background: The goal of this project is to build a "coarse-grained" model of interaction between DNA and the histone octamer. Molecular dynamics simulation on the atomic scale will be used to identify relevant degrees of freedom of motion in the nucleosome, and to build realistic large-scale interaction potentials between its components. These parameters will be used in Monte Carlo and Brownian dynamics simulations to reproduce in silico various experiments revealing structure and dynamics of mono- and oligonucleosomes. The simulations will be important for understanding of chromatin organization and functioning; furthermore, the methodological development of connecting MD with higher-level simulations will be a major advance in biomolecular simulation techniques.

From the biological side, we plan to contribute some answers to the following questions:

  • What is the geometry of the linker DNA in mono- and oligonucleosomes as a function of buffer composition, presence/absence of H1 and degree of histone acetylation?
  • What parameters are necessary to describe the known structural properties of the chromatin fiber and their variations due to histone modifications and external conditions?

Since so far only little reliable data on the physical behavior of chromatin exists, the results gained here are expected to contribute significantly to our understanding of chromatin function in its different states in the cell.

Research Goals: In the framework of the IGK, this project will combine multiple methods, multiple time and length scales by transferring information of atomic-level molecular dynamics to larger-scale Brownian dynamics and Monte-Carlo simulations. For this, strategies of homogenization and model reduction need to be developed. We shall also need to make extensive use of parallelization in our software. Our interaction partners within the GK will be Prof. Jeremy Smith (IWR) and Prof. Antosiewicz in Warsaw. In addition, Dr. Rebecca Wade (EML) will participate with her expertise in atomic-scale Brownian dynamics and electrostatics.

[1] G. Wedemann, J. Langowski 2002 : Computer simulation of the 30-nanometer chromatin fiber,
Biophys J 82(6):2847-59.
[2] K. Tóth, N. Brun, J. Langowski 2001: Trajectory of nucleosomal linker DNA studied by fluorescence resonance energy transfer,
Biochemistry 40(23):6921-6928.

Optimization of Brownian Dynamics Simulation of Entangled Polymer Chains, Application to Chromatin in the Cell Nucleus

next top

Supervisors: Langowski (DKFZ Heidelberg), Smith (IWR Heidelberg)

Keywords: Model Reduction, Parallel Computing, Brownian Dynamics

Background: Here we plan to develop methods for fast simulation of the distribution of flexible polymer chains in a confined space. This problem is important for our understanding of the distribution of chromosomes in the cell nucleus; in particular the question, whether and how chromosomes keep their relative arrangement after cell division and how this changes through the cell cycle is not understood at all at the moment.

The ensemble of chromosomes in the human cell nucleus constitutes a very complex system, comprising 46 chromosomes with a total of 6*109 base pairs of DNA, which are compacted at several levels of folding hierarchies. In previous work, we developed a parallelized hybrid Monte-Carlo model that allows simulation of properties of interphase chromosomes, using a chain of about 1.5*106 polymer segments that are interconnected in a topology given by the known biological and structural properties [1, 2].

Research Projects: In this project, we will develop a new Brownian dynamics model that allows to simulate the behavior of the 30 nm chromatin filament in the restricted space of the cell nucleus and under topological restriction such as attachment to the nuclear membrane and other organizing centers. The results of these simulations will be compared to experimental data on the in vivo mobility of chromosomes in yeast and higher eukaryotes. For this project, we need to develop modeling strategies for the dynamics of entangled polymer chains; this work will require cooperation with the Simulation/Optimization group of Prof. Bock. The fractal nature of the interphase chromatin folding makes this system an obvious target for model reduction.

[1] C. Münkel and J. Langowski (1998): Chromosome structure described by a polymer model,
Physical Review E 57, 5888-5896.
[2] C. Münkel, R. Eils, S. Dietzel, D. Zink, C. Mehring, G. Wedemann, T. Cremer and J. Langowski (1999): Compartmentalization of interphase chromosomes observed in simulation and experiment,
Journal of Molecular Biology 285, 1053-1065.

Modeling and Simulation of Chemistry and Transport in SOFC Porous Electrodes

next top

Supervisors: Warnatz (IWR Heidelberg), Bastian (IWR Heidelberg)

Keywords: Parallel Computing, Power Cells

Background: Solid oxide fuel cell (SOFC) technology offers a unique potential for efficient energy conversion without pollutant emission in stationary applications. Since SOFCs can be operated with hydrocarbon fuels (e.g. natural gas), they are expected to play an important mid-term role in sustainable energy supply. The core of an SOFC consists of an assembly of anode, electrolyte and cathode. Our investigations focus on the anode, which is typically a porous structure consisting of a metallic and a ceramic component.

Research Goals: The goal of this project is the development of detailed models of the electrochemical fuel oxidation reaction and multi-scale mass transport within the anode. The electrochemical reaction takes place at the three-phase boundary of gas phase and the two solid phases of electrode and electrolyte. Its mechanism, however, is subject of widely differing hypotheses [1]. Besides surface chemistry, effects of surface diffusion and surface phase transitions will be implemented in the model, as well as interactions with the gas phase, all of which are taking place on different spatial and temporal scales [2].

A large body of empirical evidence shows the large influence of porous electrode microstructure on fuel cell performance. However, these effects cannot be resolved with currently-applied homogenized transport models. In collaboration with the Bastian group, simulations of porous diffusion will be performed on a microscopic scale. This approach is based on the numerical tools and parallel computing capabilities of the Bastian group. The governing partial differential equations will be discretized with the discontinuous Galerkin method [3] which is especially suited to tackle the complex pore scale geometry. The parallel implementation will be based on the software framework DUNE [4].

[1] W. G. Bessler and J. Warnatz : Calculation of impedance by transient numerical simulation of SOFC elementary electrochemistry,
Proc. of the 6th European SOFC Forum (Lucerne, Switzerland, 2004), 754-763.
[2] F. Behrendt, O. Deutschmann, B. Ruf, R. Schmidt and J. Warnatz: Simulation of Heterogeneous Reaction Systems,
In: Gas phase chemical reaction systems: experiment and models, 100 years after Max Bodenstein, J. Wolfrum, et al., Editors (Springer, 1996), pp. 265-278.
[3] P. Bastian: Higher order discontinuous Galerkin methods for flow and transport in porous media}, in E. Bänsch, editor,
Challenges in Scientific Computing -- CISC 2002}, number 35 in LNCSE, pages 1--22, 2003.
[4] P. Bastian, M. Droske, C. Engwer, R. Klöfkorn, T. Neubauer, M. Ohlberger and M. Rumpf: Towards a unified framework for scientific computing,
Proc. 15th Conf. Domain Decomposition Methods (R. Kornhuber, et al., eds.), LNCSE. Springer, 2004.

Parallel Adaptive Multigrid Methods for Protein Folding and Dynamics

next top

Supervisors: Wittum (IWR Heidelberg), Smith (IWR Heidelberg)

Keywods: Parallel Computing, Multilevel

Background: In atomic-detail computer simulations of biological macromolecules in aqeous solution electrostatic interactions are usually represented via Coulomb interactions between partial charges positioned on the atoms of the macromolecule and its surrounding explicit solvent molecules. Thus, a large amount of computation time is wasted on solvent dynamics. To avoid this, methods have been developed that represent the solvent as a polarisable continuum. Such implicit-solvent techniques rely on the numerical solution of the Poisson-Boltzmann equation (PBE) and have been shown to yield accurate results at reasonable computational expense in the context of ligand binding studies, [1]. However, current implementations to solve the PBE are not optimized and thus slower than the state of the art would allow. An optimized numerical protocol and implementation to be used with the macromolecular modeling package CHARMM [2] would therefore be highly desirable.

Research Goals: As computers become faster it becomes more and more possible to tackle the question how enzymes achieve their remarkable efficiency in speeding up chemical reactions by up to 1021-fold. Such simulations require the highly-complex combination of quantum mechanical (QM) and molecular mechanical (MM) simulation techniques. An implicit-solvent treatment of long-range electrostatic effects to be used with QM/MM calculations has to date not been mathematically formulated. The development and implementation of such a formalism would enhance the capability to understand the functioning of biological macromolecules at an atomic and subatomic level of detail. An important issue in all the above as well as several of the following projects is modeling the effects of solvent/water molecules. To attack this problem, we plan to continue our development of continuum methods using the Poisson-Boltzmann representation in combination with the UG multigrid method being developed in the Wittum group. The simulation system UG provides parallel adaptive multigrid methods for complex application problems, [3]. In the framework of a diploma thesis, we already started a cooperation on this topic. In this project we want to extend this work to more realistic configurations.

[1] S. M. Schwarzl, T. B. Tschopp, J. C. Smith, S. Fischer: Can the Calculation of Ligand Binding Free Energies Be Improved with Continuum Solvent Electrostatics and an Idel-Gas Entropy Correction?,
J. Comput. Chem. 2002, 23, 1143-1149
[2] B. R. Brooks, R. E. Bruccoleri, B. D. Olafson, D. J. States, S. Swaminathan, M. Karplus: CHARMM: A program for macromolecular energy, minimization and dynamics calculations,
J. Comp. Chem. 1983, 4, 187-217.
[3] P. Bastian, K. Birken, K. Johannsen, S. Lang, V. Reichenberger, C. Wieners, G. Wittum, C. Wrobel: A parallel software-platform for solving problems of partial differential equations using unstructured grids and adaptive multigrid methods,
In High Performance Computing in Science and Engineering (W. Jäger and E. Krause, eds.), p 326-339 Springer, 2000.

Numerical Modeling of Nonlinear Diffusion on Complex Domains

next top

Supervisors: Bastian (IWR Heidelberg), Niezgódka (ICM Warsaw)

Keywords: Parallel Computing, Multiscale

Background: Nonlinear diffusion over domains of complex geometry represents a challenge equally to analysts and numerical analysts. To gain a qualitative knowledge on local effects, in particular for large time intervals, in subdomains of strongly different geometric and topological characteristics is of high interest for many real-world applications such as those arising from the modeling of chemical or biological systems. Of high applied relevance is the formation of spatial structures due to diffusion-driven developments in heterogeneous populations, [1].

Research Goals: Within the proposed project, of special interest will be to develop a systematic classification of models according to the geometric/topological characteristics of the domains involved. This will be possible through the combination of the modeling techniques of the ICM group with the computational techniques developed in the IWR group. In particular in the numerical part of this project we propose to:

  • Extend the discontinuous Galerkin method to systems of nonlinear diffusion-reaction equations and implement different stabilization schemes such as the symmetric and nonsymmetric interior penalty Galerkin method, the Oden-Babuska-Baumann method and the local discontinuous Galerkin method.
  • Compare the different schemes with respect to accuracy and robustness for applications including complex geometries and highly varying diffusion coefficients. So far, thorough comparisons are only available for simple model problems. In particular, some methods have a stabilization parameter and the sensitivity of the accuracy with respect to this parameter in real applications shall be investigated.
  • Develop fast, parallel and robust solvers for the arising linear systems which allow us to solve very large problems on large scale distributed memory parallel computers, [2]. One possibility here is to extend aggregation based algebraic multigrid methods. These methods are very robust for systems arising from standard discretizations and are highly parallelizable, [3].
[1] N. Kenmochi, M. Niezgódka, M. Otani, eds.: Mathematical Aspects of Modelling Structure Formation Phenomena,
Math. Sciences and Applications, Vol. 17, Gakkotosho, Tokyo, 2001.
[2] P. Bastian, M. Droske, C. Engwer, R. Klöfkorn, T. Neubauer, M. Ohlberger, and M. Rumpf: Towards a unified framework for scientific computing,
Proc. 15th Conf. on Domain Decomposition Methods(R. Kornhuber et al., eds.), LNCSE. Springer-Verlag, 2004, accepted for publication.
[3] M. Blatt: Parallel aggregation based algebraic multigrid,
Master's thesis, Faculty of Mathematics and Computer Science, University Heidelberg, 2004.

Efficient Techniques for Global Optimization

next top

Supervisors: Bock (IWR Heidelberg), Piela (ICM, Warsaw)

Keywords: Global Optimization, Multiscale

Background: Functions with numerous local minima are ubiquitous in many branches of natural sciences and one is interested in finding the global minimum (GM). In chemistry, e.g., the GM conformation may tell us about the function an enzyme performs. But for flexible molecules (e.g. enzymes) the number of minima (conformations) may easily attain 10100. Any systematic search of the conformational space based on local approaches seems to be hopeless.

There are many different approaches to global optimization in the literature, e.g. [4], differing from incomplete methods as genetic algorithms over asymptotically complete ones to rigorous methods that usually make use of outer approximation of the feasible set, underestimation of the objective function and interval arithmetic in a Branch-and-Bound scheme. While these methods work well on a large set of problems, they seem unfit to treat the very high-dimensional problem class under investigation, simply due to the exponential worst-case behaviour of Branch-and-Bound algorithms. To overcome these problems a promising heuristics have been proposed in [2]. There a non-convolutional way of smoothing of the objective function is considered. Imagine a wheelbarrow (of the wheel radius r) rolling under the target function f(x) and at any instance tangent to f(x). Then, the wheelbarrow axis trajectory F(x;r) for sufficiently large r has as the only minima those at the exact positions of the GM of the original function f(x).

Research Goals: The first part of the proposed thesis could be a study of 1D cases. It might be to `highlight' or `stress' the GM by a recursive transformation,

F(n,x,a)=a{-exp[-F(n-1,x,a)/a]+1} for n=1,2,3, and a>0,

with f(x)= F(0,x,a). Then, a method of rolling the wheel has to be designed. Next, the method has to be generalized to the so-called global optimization standard test functions of higher dimension [1]. As benchmarks for the method the well known GM for the Lennard-Jones atomic clusters may be taken. The mathematical properties of the new heuristics will be investigated and compared to established exact methods of global optimization [3]. In particular the complexity of the new techniques will be investigated and comparisons to exact methods will be performed.

[1] L. Piela: Handbook of Global Optimization,
P.M.Pardalos, H.E.Romeijn, eds., Vol.2, 461--488, Kluwer Acad.Publishers, 2002.
[2] J. Pillardy, L. Piela: J. Comput. Chem., 18, 2040--2049, 1997.
[3] C.A. Floudas and P.M. Pardalos: Optimization in Computational Chemistry and Molecular Biology: Local and Global Approaches,
Kluwer, 2000.
[4] A. Neumaier: Complete Search in Continuous Global Optimization and Constraint Satisfaction,
pp. 271--369 in: Acta Numerica 2004 (A. Iserles, ed.), Cambridge University Press, 2004.

Modeling Bose-Einstein Condensates by Non-Linear Quantum Dynamics

next top

Supervisors:Cederbaum (PCI Heidelberg), Lesyng (ICM Warsaw)

Keywords: Parallel Computing, Nonlinear Quantum Dynamics

Background: Non-linear Schrödinger equations are widely used in many areas of physics and chemistry. A particularly interesting field of high current actuality, where the non-linear Schrödinger equation (also called the Gross-Pitaevskii (GP) equation) is often used, refers to dilute gas Bose-Einstein condensates. The GP equation is a mean-field equation which has been successfully applied in many cases, but fails to describe several phenomena of interest, like fragmentation of condensates. Recently, a general mean-field has been introduced and shown to be able to handle fragmentation [1], [2].

Research Goals: This best mean-field leads to a set of n (n>1) coupled non-linear equations and the objective of the project is to develop numerical methods to solve them efficiently in one, two and three dimensions of space and for several n. For a given problem, the number n of coupled equations is determined by the variational principle. The solution of the new non-linear Schrödinger equation provides a wavefunction describing the condensate. This wavefunction is discretized using discrete variable representations (DVR). The resulting non-linear working equations are solved iteratively until self-consistency is obtained.

The group of Lesyng (ICM Warsaw) has experience in parallel and vector-parallel architectures, [3], and has already started working with the GP equation [4]. In addition, their vast experience with efficient implementations of dynamics of multidimensional quantum subsystems embedded in large classical environments will be most helpful for treating also the dynamics of condensates efficiently.

The doctoral student is expected to develop the code following the above lines and, in particular, to parallelize the algorithm. Simulations of realistic condensates like those experimentally prepared in Heidelberg in the group of J. Schmiedmayer and M. Oberthaler (Physics Department) should be carried out.

[1] L. S. Cederbaum and A. I. Streltsov: Best mean-field for condensates,
Phys. Lett. A 318, 564 (2003).
[2] L. S. Cederbaum and A. I. Streltsov: Self-consistent fragmented excited states of trapped condensates,
Phys. Rev. A 70, 023610 (2004).
[3] P. Bala, T. Clark, P. Grochowski, B. Lesyng, J. A. McCammon: Parallel version of the combined quantum classical molecular dynamics code for complex molecular and biomolecular systems,
in "Recent Advances in Parallel Virtual Machine and Message Passing Interface", pp. 409-416, Springer-Verlag (1997)
[4] A. Gorecki, P. Bala and B. Lesyng: Parallelization of the quantum dynamics code for cluster architecture and its application to the Gross-Pitaevskii equation,
Int. J. Quant. Chem. (submitted).

Ignition of Liquid Fuel Sprays in Air in the Counterflow Configuration

next top

Supervisors: Gutheil (IAM Heidelberg), Rychter (ICM Warsaw)

Keywords: Multiscale, Combustion Processes

Background: The ignition of sprays has not been successfully studied to the extend that the ignition behavior of interacting droplets can be implemented into computer codes for technical spray applications. The counterflow configuration has been identified as a powerful tool to study steady spray flames with both experimental and numerical methods.

Research Goals: An existing computer code for a steady system [1] will be extended to unsteady conditions to investigate the ignition behavior of laminar sprays with parameter studies for the initial droplet size and velocity as well as the dispersity of the spray. The parametric ignition times obtained will be implemented into the KIVA 3V (Release 2) code for turbulent spray ignition and combustion [2] where methods such as the PDF (probability density function) method [3] will be used to account for the turbulent character of the flow. The application is a diesel engine where both injection and ignition are major issues in the determination of the entire combustion process. The combined expertise of knowledge on heterogeneous ignition by the first supervisor and modeling of injection characteristics in connection with the use of the KIVA 3V code of the second supervisor will be extremely beneficial for the success of the proposed project.

[1] E. Gutheil: Structure and Extinction of Laminar Ethanol/Air Spray Flames,
Combustion Theory and Modeling 5: 1-15 (2001).
[2] R. Jarnicki, T. J. Rychter: Theoretical Study of Combustion Intensification in SI Piston Engines,
SAE Paper No. 2002-01-1742, 2002; Also in the book: Engine Modeling Techniques: SI and Diesel., SP-1711.
[3] H.-W. Ge, E. Gutheil: PDF Modeling of Turbulent Spray Flows,
Atomization and Sprays, 2004, submitted.

Proton Transfer and Keto--Enol Tautomerization in Malonaldehyde

next top

Supervisors: Meyer (IWR Heidelberg), Dodziuk (ICM Warsaw)

Keywords: Adaptive Methods, Molecular Dynamis

Background: Malonaldehyde (C3H4O2) exists in the Keto and Enol form. The Enol form is cyclic with the two Oxygen atoms sharing one Hydrogen. By proton transfer this Hydrogen exchanges the Oxygen to which it is bound. These dynamical processes, i.e. the tautomerization and the proton transfer, shall be studied theoretically with the multiconfiguration time-dependent Hartree(MCTDH) method [1]. MCTDH has been developed in Heidelberg over the last decade. A program package (250,000 lines, including the documentation) has been written, which allows to propagate a multidimensional (3 to 30 degrees of freedom, say) wavepacket very efficiently, as well as to analyse this propagated wavepacket to obtain cross-sections, spectra, etc. Problems which were not feasible before, have become feasible through the advent of MCTDH. MCTDH is a novel, powerful, and convenient tool to attack problems of molecular quantum dynamics. MCTDH has proven its power in several applications (see the MCTDH web-site for a list of applications).

Research Goals: In parallel Malonaldehyde shall be studied experimentally by Dodziuk (ICM Warsaw) using IR, UV, and NMR spectroscopic techniques [2]. This will lead to a deeper understanding of the complicated dynamics of this molecule [3]. Experimentally, the probes will consist of a mixture of isomers. The calculation of NMR parameters [4] is hence important for interpreting the spectra.

[1] M. H. Beck, A. Jäckle, G. A. Worth and H.-D. Meyer: The multiconfiguration time-dependent Hartree method: A highly efficient algorithm for propagating wavepackets,
Phys. Rep. 324 (2000), 1--105.
[2] H. Dodziuk: Rigidity versus flexibility. A review of experimental and theoretical studies pertaining to the cyclodextrin nonrigidity,
J. Mol. Struct. 614 (2002), 33.
[3] S. Yamabe, N. Tsuchida and K. Miyajima: Reaction path of keto--enol tautomerization of Þ-diketones,
J. Phys. Chem. A 108 (2004), 2750--2757.
[4] M. Jaszunski, G. Dolgonos, and H. Dodziuk: An ab initio study of NMR chemical shifts and spin-spin coupling constants of Bicyclobutane,
Theor. Chem. Acc. 108 (2002). 240--245.

Numerical Modeling of the Dynamics of Structured Biopopulations: Diffusion-Driven Structural Transformation

next top

Supervisors Rannacher (IAM Heidelberg), Niezgódka (ICM Warsaw)

Keywords: Multiscale, Adaptivity

Background: Diffusive phase separation is a phenomenon exhibiting multiple temporal scales. In multi-component systems, possibly with intrinsic multi-phase nature, this process contributes to formation of spatial structures subject to thermodynamic non-equilibrium forcing. The class of mathematical models to be considered in their diffusion part involves a rather subtle interplay of two driving phenomena: thermodynamically destabilizing non-monotonicity of bulk constitutive relations, in the simplest case resembling van der Waals functions, [2], and the stabilizing contribution due to surface forcing, in form of Ginzburg terms, [3].

Those effects heavily differ in their magnitude, up to several orders, often getting close to floating-point accuracy of real implementations. An additional challenge concerns the shape of geometric domain, with a special interest in the case of few large subdomains connected by thin segments. It would be also highly interesting to tackle the case of dynamic couplings of diffusion to convection and diffusion to heat transfer. The latter effect plays a special role for large times, where due to experimental evidence thermal fluctuations have strong impact on the developments.

Research goal: For dealing with the problems desribed above, we need to develop numerical approaches capable of reproducing localized in space large-time behavior of the system. The presence of extremely fast temporal modes versus rather slow ones, manifesting only for very long time intervals and, even then, on quite low level of articulation, contributes to severe difficulties with designing efficient computational approaches. This requires the use of adaptive methods such as described in [1]. The contribution to the error by the local residuals at the various scales, i.e. their sensitivities, is captured by numerically solving approporiate dual problems. Here, the crucial question is whether dual information obtained on an intermediate scale can actually describe the effect by the finest scales on the coarse scale phenomena. This requires intensive test calculations with nonlinear multiscale problems. This is related to the even more challenging question of turbulence simulation by adaptive LES (Large Eddy Simulation) approaches as recently proposed in [4]. The techniques used in this field should also be tried on partially chaotic biological models.

[1] R. Becker, V. Heuveline, R. Rannacher: An optimal control approach to adaptivity in computational fluid mechanics,
Int. J. Numer. Meth. Fluids. 40, 105-120 (2002).
[2] J. Cahn, A. Novick-Cohen: Evolution equations for phase separation and modelling in binary alloys,
J. Stat. Phys. 76, 877-909 (1994).
[3] N. Kenmochi, M. Niezgódka, I. Pawlow: Subdifferential approach to the Chan-Hilliard equation with constraint,
J. Diff. Equations 117, 320-356 (1995).
[4] T. J. R Hughes, G. R. Feijoo, L. Mazzei, and J.-B. Quincy: The variational multiscale method - a paradigm for computational mechanics,
Comput. Methods Appl. Mech. Eng., 166:3--24, 1998.

Calculation of Thermodynamic Potentials and Response Functions for Large-Scale Networks


Supervisors: Reinelt (IfI Heidelberg), Wislicki (ICM Warsaw)

Keywords: Graph Algorithms, Statistical Thermodynamics

Background: Finding equilibria for a large-scale choice-model network needs an extensive simulation and integration over the state space whose size depends factorially on the network size. Computational shortcuts are certainly needed for problems of the size comparable to real life problems in transportation, energy routing or communication in large groups, where the numbers of nodes are of the order of thousands and the number of agents exceeds the number of nodes by one or more orders of magnitudes. For simulating the system thermodynamic partition functions are to be computed. These are sums over all states of the system where the number of states not only depends on the size of the network but also depends on the size of the population of agents distributed on such a network. This is a very hard computational task.

Simulations so far have been performed for rather small systems only. In this collatboration numerical simulations will be extended to larger systems. This task requires finding algorithmic shortcuts in order to simplify the problem. For example, one can suppress a large number of the largest-utility paths as negligibly contributing to the partition function. Effective combinatorial algorithms on graphs are needed and a detailed analysis of an estimator's bias is necessary.

Research Goals: In a first PhD project in this area we want to consider a population of communicating agents, represented by a directed graph with a non-fixed, emergent topology with reinforcement learning as a topology formation formalism and to attempt to define a realistic utility function for such a system. The system's behaviour with respect to special network features as node transmittivity, link transmittivity or connectivity of nodes will be investigated.

For research work in this area the expertises of the two participating groups (statistical thermodynamics, see e.g., [1], [2], and efficient graph algorithms, see e.g., [3], [4]) ideally complement one another.

[1] A. Majka and W. Wislicki: Uniformity of the phase space and fluctuations in thermal equilibrium,
Physica A, 322C, 313 (2003)
[2] A. Majka and W. Wislicki: Statistical thermodynamics for choice models on graphs,
Physica A 337, 645 - 663 (2004)
[3] D. Ahr and G. Reinelt: A Tabu Search Algorithm for the Min-Max k-Chinese Postman Problem,
To appear in: Computers and Operations Research, Special Issue on Arc Routing, (2004)
[4] G. Reinelt: The Traveling Salesman: Computational Solutions for TSP Applications,
Lecture Notes in Computer Science 840, Springer (1994)

Last modified: April 14 2008 14:37:27. by Igor Doktorski