Skip to main content

Über dieses Buch

This book constitutes the thoroughly refereed post-conference proceedings of the 7th International Conference on Numerical Methods and Applications, NMA 2010, held in Borovets, Bulgaria, in August 2010. The 60 revised full papers presented together with 3 invited papers were carefully reviewed and selected from numerous submissions for inclusion in this book. The papers are organized in topical sections on Monte Carlo and quasi-Monte Carlo methods, environmental modeling, grid computing and applications, metaheuristics for optimization problems, and modeling and simulation of electrochemical processes.



Invited Papers

Space-Time Discontinuous Galerkin Finite Element Method for Convection-Diffusion Problems and Compressible Flow

This paper is concerned with the numerical solution of nonstationary, nonlinear, convection-diffusion problems by the space-time discontinuous Galerkin finite element method (DGFEM) and applications to compressible flow. The first part is devoted to theoretical analysis of error estimates of the method. In the second part, this technique is applied to the numerical solution of compressible flow in time-dependent domains and the simulation of flow induced airfoil vibrations.

Miloslav Feistauer, Jan Česenek

Stochastic Algorithms in Linear Algebra - beyond the Markov Chains and von Neumann - Ulam Scheme

Sparsified Randomization Monte Carlo (SRMC) algorithms for solving systems of linear algebraic equations introduced in our previous paper [34] are discussed here in a broader context. In particular, I present new randomized solvers for large systems of linear equations, randomized singular value (SVD) decomposition for large matrices and their use for solving inverse problems, and stochastic simulation of random fields. Stochastic projection methods, which I call here “random row action” algorithms, are extended to problems which involve systems of equations and constrains in the form of systems of linear inequalities.

Karl Sabelfeld

SM Stability for Time-Dependent Problems

Various classes of stable finite difference schemes can be constructed to obtain a numerical solution. It is important to select among all stable schemes such a scheme that is optimal in terms of certain additional criteria. In this study, we use a simple boundary value problem for a one-dimensional parabolic equation to discuss the selection of an approximation with respect to time. We consider the pure diffusion equation, the pure convective transport equation and combined convection-diffusion phenomena. Requirements for the unconditionally stable finite difference schemes are formulated that are related to retaining the main features of the differential problem. The concept of SM stable finite difference scheme is introduced. The starting point are difference schemes constructed on the basis of the various Pad



Petr N. Vabishchevich

Monte Carlo and Quasi-Monte Carlo Methods

Advanced Monte Carlo Techniques in the Simulation of CMOS Devices and Circuits

The years of happy scaling are over and the fundamental challenges that the semiconductor industry faces at technology and device level will deeply affect the design of the next generations of integrated circuits and systems. The progressive scaling of CMOS transistors to achieve faster devices and higher circuit density has fuelled the phenomenal success of the semiconductor industry captured by Moores famous law [1]. Silicon technology has entered the nano CMOS era with 35nm MOSFETs in mass production in the 45nm technology generation. However, it is widely recognised that the increasing variability in the device characteristics is among the major challenges to scaling and integration for the present and next generation of nano CMOS transistors and circuits. Variability of transistor characteristics has become a major concern associated with CMOS transistors scaling and integration [2], [3]. It already critically affects SRAM scaling [4], and introduces leakage and timing issues in digital logic circuits [5]. The variability is the main factor restricting the scaling of the supply voltage, which for the last four technology generations has remained virtually constant, adding to the looming power crisis.

In this paper we describe advanced Monte Carlo simulation techniques that are used to study statistical variability in contemporary and future CMOS technology generations at the levels of physical transistor simulation, compact model and circuit simulation. First we review the major sources of statistical variability in nano CMOS transistors focusing at the 45nm technology generation and beyond and introduce the advanced 3D statistical physical statistical simulation technology and tools used to forecasts the magnitude of statistical variability. Statistical compact models used to transfer the variability information obtained from the physical simulations into the circuit simulation and design domain are discussed next. Sensitivity analysis allows the selection of optimal statistical compact model sets of parameters. The use of statistical compact models is illustrated in the simulation of SRAM cells.

Asen Asenov

Monte Carlo Method for Numerical Integration Based on Sobol’s Sequences

An efficient Monte Carlo method for multidimensional integration is proposed and studied. The method is based on Sobol’s sequences. Each random point in


-dimensional domain of integration is generated in the following way. A Sobol’s vector of dimension



$\it{\Lambda \Pi_{\tau}}$

point) is considered as a centrum of a sphere with a radius


. Then a random point uniformly distributed on the sphere is taken and a random variable is defined as a value of the integrand at that random point. It is proven that the mathematical expectation of the random variable is equal to the desired multidimensional integral. This fact is used to define a Monte Carlo algorithm with a low variance.

Numerical experiments are performed in order to study the quality of the algorithm depending of the radius


and regularity, i.e. smoothness of the integrand.

Ivan Dimov, Rayna Georgieva

Using Monte-Carlo Simulation for Risk Assessment: Application to Occupational Exposure during Remediation Works

The aim of this study was to apply the Monte-Carlo techniques to develop a probabilistic risk assessment. The risk resulting from the occupational exposure during the remediation activities of a uranium tailings disposal, in an abandoned uranium mining site, was assessed. A hypothetical exposure scenario was developed and two different pathways were compared: internal exposure through radon inhalation and external through gamma irradiation from the contaminated tailings material. The input variables, such as the inhalation rate and the external exposure parameters, were considered as specific probabilistic distributions, each one characterized by its central tendency and dispersion parameters. Using the cumulative distribution function, a probabilistic value for each variable can be generated using a single random number. Thus, this methodology allows performing a probabilistic risk assessment generating a risk distribution.

M. L. Dinis, A. Fiúza

The b-adic Diaphony as a Tool to Study Pseudo-randomness of Nets

We consider the


-adic diaphony as a tool to measure the uniform distribution of sequences, as well as to investigate pseudo-random properties of sequences. The study of pseudo-random properties of uniformly distributed nets is extremely important for quasi-Monte Carlo integration. It is known that the error of the quasi-Monte Carlo integration depends on the distribution of the points of the net. On the other hand, the


-adic diaphony gives information about the points distribution of the net.

Several particular constructions of sequences (



) are considered. The


-adic diaphony of the two dimensional nets {



 = (






 + 1

)} is calculated numerically. The numerical results show that if the two dimensional net {



} is uniformly distributed and the sequence (



) has good pseudo-random properties, then the value of the


-adic diaphony decreases with the increase of the number of the points. The analysis of the results shows a direct relation between pseudo-randomness of the points of the constructed sequences and nets and the


-adic diaphony as well as the discrepancy.

Ivan Lirkov, Stanislava Stoilova

Scatter Estimation for PET Reconstruction

This paper presents a Monte Carlo scatter estimation algorithm for Positron Emission Tomography (PET) where positron-electron annihilations induce photon pairs that fly independently in the medium and eventually get absorbed in the detector grid. The path of the photon pair will be a


defined by the detector hits and scattering points where one of the photons changed its direction. The values measured by detector pairs will then be the total contribution, i.e. the integral of such polyline paths of arbitrary length. This integral is evaluated with Monte Carlo quadrature, using a sampling strategy that is appropriate for the graphics processing unit (GPU) that executes the process. We consider the contribution of photon paths to each pair of detectors as an integral over the Cartesian product set of the volume. This integration domain is sampled globally, i.e. a single polyline will represent all annihilation events occurred in any of its points. Furthermore, line segments containing scattering points will be reused for all detector pairs, which allows us to significantly reduce the number of samples. The scatter estimation is incorporated into a PET reconstruction algorithm where the scattered term is subtracted from the measurements.

Milan Magdics, Laszlo Szirmay-Kalos, Balazs Tóth, Ádam Csendesi, Anton Penzov

Modeling of the SET and RESET Process in Bipolar Resistive Oxide-Based Memory Using Monte Carlo Simulations

A stochastic model of the resistive switching mechanism in bipolar oxide-based resistive random access memory (RRAM) is presented. The distribution of electron occupation probabilities obtained is in agreement with previous work. In particular, a low occupation region is formed near the cathode. Our simulations of the temperature dependence of the electron occupation probability near the anode and the cathode demonstrate a high robustness of the low occupation region. The RESET process in RRAM simulated with our stochastic model is in good agreement with experimental results.

Alexander Makarov, Viktor Sverdlov, Siegfried Selberherr

Stochastic Algorithm for Solving the Wigner-Boltzmann Correction Equation

The quantum-kinetics of current carriers in modern nanoscale semiconductor devices is determined by the interplay between coherent phenomena and processes which destroy the quantum phase correlations. The carrier behavior has been recently described with a two-stage Wigner function model, where the phase-breaking effects are considered as a correction to the coherent counterpart. The correction function satisfies a Boltzmann-like equation.

A stochastic method for solving the equation for the correction function is developed in this work, under the condition for an a-priori knowledge of the coherent Wigner function. The steps of an almost optimal algorithm for a stepwise evaluation of the correction function are presented. The algorithm conforms the well established Monte Carlo device simulation methods, and thus allows an easy implementation.

M. Nedjalkov, S. Selberherr, I. Dimov

Modeling Thermal Effects in Fully-Depleted SOI Devices with Arbitrary Crystallographic Orientation

In this work we continue our investigation on the heating effects in nano-scale FD-SOI devices using an in-house thermal particle-based device simulator. We focus on the current variations for FD-SOI devices with arbitrary crystallographic orientation and examine which crystallographic orientation gives better results from electrical and thermal point of view. Our simulation results demonstrate that one can obtain the lowest current degradation with (110) wafer orientation. The temperature of the hot-spot is the smallest for (110)-orientation as well.

K. Raleva, D. Vasileska, S. M. Goodnick

Particle Monte Carlo Algorithms with Small Number of Particles in Grid Cells

The Direct Simulation Monte Carlo (DSMC) analysis of two- and three-dimensional rarefied gas flows requires computational resources of very large proportions. One of the major causes for this is that, along with the multidimensional computational mesh, the standard DSMC approach also requires a large number of particles in each cell of the mesh in order to obtain sufficiently accurate results. In this paper we present two modified simulation procedures which allow more accurate calculations with a smaller mean number of particles (

$\left\langle{N}\right\rangle \sim 1$

) in the grid cells. In the general DSMC scheme, the standard DSMC collision algorithm is replaced by a new collision procedure based on ”Bernoulli trials” scheme or its simplified version. The modified algorithms use a symmetric Strang splitting scheme that improves the accuracy of the splitting method to





) with respect to the time step


making the modified DSMC method a more effective numerical tool for both steady and unsteady gas flow calculations on fine multidimensional grids. Here the considered modifications are validated on the one-dimensional unsteady-state problem of strong shock wave formation.

Stefan K. Stefanov

Is Self-Heating Important in Nanowire FETs?

In this work we investigate self-heating effects in nanowire FETs. We find that, as in the case of FD SOI devices, the velocity overshoot effect of the carriers in the channel and reduced number of scattering events with phonons lead to smaller ON-current degradation in short compared to long channel nanowire transistors.

D. Vasileska, A. Hossain, K. Raleva, S. M. Goodnick

Environmental Modeling

Mixed-Hybrid Formulation of Multidimensional Fracture Flow

We shall study Darcy flow on the heterogeneous system of 3D, 2D, and 1D domains and we present four models for coupling of the flow. For one of these models, we describe in detail its mixed-hybrid formulation. Finally, we show that Schur complements are suitable for solution of the linear system resulting form the lowest order approximation of the mixed-hybrid formulation.

Jan Březina, Milan Hokr

WRF-Fire Applied in Bulgaria

WRF-Fire consists of the WRF (Weather Research and Forecasting Model) coupled with a fire spread model, based on the level-set method. We describe a preliminary application of WRF-Fire to a forest fire in Bulgaria, oportunities for research of forest fire models for Bulgaria, and plans for the development of an Environmental Decision Support Systems which includes computational modeling of fire behavior.

Nina Dobrinkova, Georgi Jordanov, Jan Mandel

Bulgarian Operative System for Chemical Weather Forecast

In the paper, an operational prototype of the Integrated Bulgarian Chemical Weather Forecasting and Information System is presented. The system is foreseen to provide in real time forecast of the spatial/temporal Air Quality behavior for the country and (with higher resolution) for selected sub-regions and cities. The country-scale part of the system has been designed and tested and is now running operationally. It is based on the US EPA Models-3 System (MM5, SMOKE and CMAQ). The meteorological input to the system is NIMHs operational numerical weather forecast. The emission input exploits a high resolution disaggregation of the EMEP 50x50 km inventory for the year 2003. When elaborated, the actual national emission inventory is foreseen to be used. The boundary conditions are prepared by a similar system running operationally at Aristotle University of Thessaloniki, Greece. The System automatically runs twice a day (00 and 12 UTC) and produces 48-hour forecast. The results of each Systems run are post-processed in a way to archive the most important pollutants forecasts as to compare them with the respective measurements for the sake of verification of the System. Part of these pollutants is visualized as sequences of maps giving the evolution of the air quality over the country. The plots are uploaded to NIMHs web-server. The web-site is designed in a way to show both forecast maps for specified moments of time and animations for the entire 48-hour period for a number of key species.

Iglika Etropolska, Maria Prodanova, Dimiter Syrakov, Kostadin Ganev, Nikolai Miloshev, Kiril Slavov

Atmospheric Composition Studies for the Balkan Region

The present work aims at studying the local to regional atmospheric pollution transport and transformation processes over the Balkan Peninsula and at tracking and characterizing the main pathways and processes that lead to atmospheric composition formation in the region.

The US EPA Models-3 system is chosen as a modelling too, its nesting capabilities applied for downscaling the simulations to a 9 km resolution over Balkans. The TNO emission inventory is used as emission input. Special pre-processing procedures are created for introducing temporal profiles and speciation of the emissions.

The Models-3 “Integrated Process Rate Analysis” option is applied to discriminate the role of different dynamic and chemical processes for the pollution from road and ship transport. Some results from several emission scenarios which make it possible to evaluate the contribution of different SNAP are demonstrated as well.

Georgi Gadzhev, Georgi Jordanov, Kostadin Ganev, Maria Prodanova, Dimiter Syrakov, Nikolai Miloshev

Specialized Sparse Matrices Solver in the Chemical Part of an Environmental Model

A two-dimensional advection-diffusion-chemistry module of a large-scale environmental model (Danish Eulerian Model for studying the transport of air pollutants on large scale - UNI-DEM) is taken. The module is described mathematically by system of partial differential equations. Sequential splitting is used in the numerical treatment. The non-linear chemistry is most the time-consuming part during the computer runs and it is handled by six implicit algorithms for solving ordinary differential equations. This leads to the solution of very long sequences of systems of linear algebraic equations. It is crucial to solve these systems efficiently. This is achieved by applying four different algorithms which are developed, tested and discussed.

Krassimir Georgiev, Zahari Zlatev

A Numerical Investigation for the Optimal Contaminant Inlet Positions in Horizontal Subsurface Flow Wetlands

The paper presents a numerical treatment of flow and contaminant removal in porous media with emphasis to horizontal subsurface flow constructed wetlands. The purpose here is to find their optimal design characteristics as concerns the contaminant inlet positions, in order to maximize the removal efficiency.

Konstantinos Liolios, Vassilios Tsihrintzis, Stefan Radev

Using Satellite Observations for Air Quality Assessment with an Inverse Model System

The EURAD-IM chemistry transport model and its 4d-var inverse model extension is applied to one summer and one winter episode, in order to identify the benefit of tropospheric NO


column retrievals for estimating near-surface nitrogen dioxide concentrations. Initial values and emission rates are jointly optimised by assimilating tropospheric NO


data from the OMI, while European ground based observations are used for impact evaluation. Results show a moderate improvement of surface level nitrogen dioxide estimates during the summer episode, successfully sustained after the assimilation period through emission adjustments. In the winter case, the OMI data is of limited value due to lower boundary layer heights and thus smaller impact on emission rates.

Achim Strunk, Hendrik Elbern, Adolf Ebel

Distributed Software System for Data Evaluation and Numerical Simulations of Atmospheric Processes

A distributed software system for numerical simulations of atmospheric physicochemical processes is presented. It is a multi-layer Java based system for theoretical investigation of complex interactions of atmospheric trace gases and ice particles. The simulations are based on the fundamental theory of Langmuir adsorption and second Fick’s law applied for adsorption, desorption and diffusion processes. The system consists of three basic layers: (1) input/output interface layer, (2) dispatcher layer, (3) grid-based layer for simulations distributed over multiple machines. The core software module used in level (3) is based on previously published by us software prototype for simulations of adsorption, desorption and diffusion in a closed system and Flow Tube Reactor. The main task of the current distributed system is to derive numerical estimations of several significant constants: adsorption/desorption rates, ice entry rate, ice bulk diffusion coefficient and etc. The constants are estimated by comparison of experimental signals from a Flow Tube Reactor and simulations results from the system described in this paper. The difference between both curve profiles is minimized by an exhaustive search in a multi-dimensional parameter space which represents all possible values of the physicochemical constants. The dispatcher layer of the system defines several regions of the multi-dimensional parameter space. For each region, a separate task is configured and dispatched to a node from a computer GRID or cluster. The entire parameter space is searched in a parallel manner and after that all results are united in order to find the global minimum of the difference between experimental and simulated curves. The results are printed via the input/output software layer. Example kinetic simulations performed by the software system are presented and discussed.

Atanas T. Terziyski, Nikolay T. Kochev

Advanced Numerical Tools Applied to Geo-environmental Engineering - Soils Contaminated by Petroleum Hydrocarbons, a Case Study

Contaminated soils can be considered as a heterogeneous, anisotropic and discontinuous geo-system, whose properties vary in time and space. Focusing on the remediation of a real contaminated site (a refinery located in northern Portugal), soil samples contaminated with petroleum hydrocarbons were subject to laboratory studies. The results of contaminant degradation kinetics tests led to the development of a distributed parameter model describing simultaneously the time evolution of biomass and contaminant degradation. Several phenomena were globally taken into account in this model: the volatilization, a fast kinetics component, a slow kinetics component and the refractory hydrocarbons for the time scale used in the experiments. To complement kinetics tests the soil contaminated was submitted to respirometric tests. The

a priori

unpredictability of the respirometric results justified the continuous measurement of oxygen and carbon dioxide concentrations and of temperature in the soil atmosphere, resulting in a huge volume of data. Several mathematical techniques were used in respirometry data treatment, namely: time series, system identification and wavelets theories.

Maria Cristina Vila, J. M. Soeiro de Carvalho, Antynio Fiúza

Richardson Extrapolated Numerical Methods for Treatment of One-Dimensional Advection Equations

Advection equations are an essential part of many mathematical models arising in different fields of science and engineering. It is important to treat such equations with efficient numerical schemes. The well-known Crank-Nicolson scheme will be applied. It will be shown that the accuracy of the calculated results can be improved when the Crank-Nicolson scheme is combined with the Richardson Extrapolation.

Zahari Zlatev, Ivan Dimov, István Faragó, Krassimir Georgiev, Ágnes Havasi, Tzvetan Ostromsky

Grid Computing and Applications

Programming Problems with a Large Number of Objective Functions

The paper treats the Multi-Objective Programming problem with a large composite set of (linear and nonlinear) objective functions, the domain of feasible solutions being defined by a set of linear equalities/inequalities representing a large scale problem. One constructs a preferred solution i.e. a non-dominated solution chosen via extending the decision-making framework. A feasible approach, for this class of problems, is to use a solver for the Linear Programming problems and a solver for Multiple Attribute Decision Making problems in combination with Parallel and Distributed Computing techniques based on a GRID configuration.

Cornel Resteanu, Romica Trandafir

First Results of SEE-GRID-SCI Application CCIAQ

Intensive long-term meteorological modeling took place over an area covering Bulgaria with resolution of 10 km. The climatic version of the operational weather forecast model ALADIN was applied for simulating 3 time slices: 1960-2000, 2020-2050 and 2070-2100, following the IPCC scenario A1B. The differences of climatic fields for the 3 periods are presented and interpreted. The created met-data base is used to estimate the impact of climate changes on air quality, as well. A respective modeling System was created on the base of US EPA Models-3 tool (MM5, CMAQ and SMOKE). Calculations for the last 10 years of each time slice are performed. Grid technology in the frame of SEE-GRID-SCI project is used to perform this enormous volume of calculations as an application abbreviated to CCIAQ (Climate Change Impact on Air Quality). The results are presented and interpreted in the study.

Dimiter Syrakov, Valery Spiridonov, Kostadin Ganev, Maria Prodanova, Andrey Bogachev, Nikolai Miloshev, Kiril Slavov

Metaheuristics for Optimization Problems

Genetic Algorithms Based Parameter Identification of Yeast Fed-Batch Cultivation

Different kinds of genetic algorithms have been investigated for a parameter identification of a fermentation process. Altogether eight realizations of genetic algorithms have been presented - four of simple genetic algorithms and four of multi-population ones. Each of them is characterized with a different sequence of implementation of main genetic operators, namely selection, crossover and mutation. A comparison of considered eight kinds of genetic algorithms is presented for a parameter identification of a fed-batch cultivation of

S. cerevisiae

. All kinds of multi-population algorithms lead to considerable improvement of the optimization criterion value but for more computational time. Among the considered multi-population algorithms, the best one has an operators’ sequence of crossover, mutation and selection. Different kinds of considered simple genetic algorithms lead to similar values of the optimization criterion but the genetic algorithm with an operators’ sequence of mutation, crossover and selection is significantly faster than the others.

Maria Angelova, Stoyan Tzonkov, Tania Pencheva

Intuitionistic Fuzzy Interpretations of Conway’s Game of Life

Conway’s Game of Life is a popular heuristic zero-player game, devised by John Horton Conway in 1970, and it is the best-known example of a cellular automaton. Its “universe” is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, alive or dead. Every cell interacts with its eight neighbours, which are the cells that are directly horizontally, vertically, or diagonally adjacent. In a stepwise manner, the state of each cell in the grid preserves or alternates with respect to a given list of rules. Intuitionistic fuzzy sets (IFS) are an extension of Zadeh’s fuzzy sets, which introduce a degree of membership and a degree of non-membership whose sum is equal to or less than 1 and the complement to 1 is called a degree of uncertainty. The article proposes an intuitionistic fuzzy estimation of the cells’ state in a modified Game of Life. For each cell we can define its IF estimation as a pair consisting of the degrees






, namely degrees of presence and absence of life, where






 ≤ 1. In the classical Conway’s Game of Life, the alive and dead states correspond to the elementary IF estimations 〈1,0 〉 and 〈0,1 〉. The article presents the formulas for calculating the IF state of liveliness of each cell, as functions of the current states of the cell’s neighbours. Criteria of liveliness will be also determined in terms of IFS.

Lilija Atanassova, Krassimir Atanassov

Ant Colony Optimization Approach to Tokens’ Movement within Generalized Nets

Generalized Nets (GNs) is a concept, extending the concept of Petri Nets and the rest of its modifications: an apparatus for modelling of parallel and concurrent processes. GNs have been applied to modelling of processes in the field of artificial intelligence, and in particular to metaheuristic methods for solving of optimizational problems, like the transportational problem, the travelling salesman problem, the knapsack problem, etc. An important venue of application of GNs is the area of Ant Colony Optimization (ACO). So far, GNs have been used as a method for description of the ACO procedures. The present article for the first time adopts the opposite approach: it discusses the possibility for optimization of the GN tokens’ movement, using ACO algorithms.

Vassia Atanassova, Krassimir Atanassov

Start Strategies of ACO Applied on Subset Problems

Ant Colony Optimization is a stochastic search method that mimic the social behavior of real ants colonies, which manage to establish the shortest routs to feeding sources and back. Such algorithms have been developed to arrive at near-optimum solutions to large-scale optimization problems, for which traditional mathematical techniques may fail. In this paper on each iteration estimations of the start nodes of the ants are made. Several start strategies are prepared and combined. Benchmark comparisons among the strategies are presented in terms of quality of the results. Based on this comparison analysis, the performance of the algorithm is discussed along with some guidelines for determining the best strategy. The study presents ideas that should be beneficial to both practitioners and researchers involved in solving optimization problems.

Stefka Fidanova, Krassimir Atanassov, Pencho Marinov

Sensitivity Analysis of ACO Start Strategies for Subset Problems

Ant Colony Optimization (ACO) has been used successfully to solve hard combinatorial optimization problems. This metaheuristic method is inspired by the foraging behavior of ant colonies, which manage to establish the shortest routes to feeding sources and back. On this work we use estimation of start nodes with respect to the quality of the solution. Various start strategies are offered. Sensitivity analysis of the algorithm behavior according strategy parameters is made. Our ideas is applied on Multiple Knapsack Problem (MKP) like a representative of the subset problems.

Stefka Fidanova, Pencho Marinov, Krassimir Atanassov

A Highly-Parallel TSP Solver for a GPU Computing Platform

The traveling salesman problem (TSP) is probably the most widely studied combinatorial optimization problem and has become a standard testbed for new algorithmic ideas. Recently the use of a GPU (Graphics Processing Unit) to accelerate non-graphics computations has attracted much attention due to its high performance and low cost. This paper presents a novel method to solve TSP with a GPU based on the CUDA architecture. The proposed method highly parallelizes a serial metaheuristic algorithm which is a genetic algorithm with the OX (order crossover) operator and the 2-opt local search. The experiments with an NVIDIA GeForce GTX285 GPU and a single core of 3.0 GHz Intel Core2 Duo E6850 CPU show that our GPU implementation is about up to 24.2 times faster than the corresponding CPU implementation.

Noriyuki Fujimoto, Shigeyoshi Tsutsui

Metaheuristics for the Asymmetric Hamiltonian Path Problem

One of the most important applications of the Asymmetric Hamiltonian Path Problem is in scheduling. In this paper we describe a variant of this problem, and develop both a mathematical programming formulation and simple metaheuristics for solving it. The formulation is based on a transformation of the input data, in such a way that a standard mathematical programming model for the Asymmetric Travelling Salesman Problem can be used on this slightly different problem. Two standard metaheuristics for the asymmetric travelling salesman are proposed and analysed on this variant: repeated random construction followed by local search with the 3-Exchange neighbourhood, and iterated local search based on the same neighbourhood and on a 4-Exchange perturbation. The computational results obtained show the interest and the complementary merits of using a mixed-integer programming solver and an approximative method for the solution of this problem.

João Pedro Pedroso

Adaptive Intelligence Applied to Numerical Optimisation

The article presents modification strategies’ theoretical comparison and experimental results achieved by adaptive heuristics applied to numerical optimisation of several non-constraint test functions. The aims of the study are to identify and compare how adaptive search heuristics behave within heterogeneous search space without retuning of the search parameters. The achieved results are summarised and analysed, which could be used for comparison to other methods and further investigation.

Kalin Penev, Anton Ruzhekov

Fed-Batch Cultivation Control Based on Genetic Algorithm PID Controller Tuning

In this paper a universal discrete PID controller for the control of

E. coli

fed-batch cultivation processes is designed. The controller is used to control feed rate and to maintain glucose concentration at the desired set point. Tuning the PID controller, to achieve good closed-loop system performance, using genetic algorithms is proposed. As a result the optimal PID controller settings are obtained. For a short time the controller sets the control variable and maintains it at the desired set point during the process. Application of the designed controller provides maintaining of the accuracy and efficiency of the system performance.

Olympia Roeva, Tsonyo Slavov

Perspectives of Selfish Behaviour in Mobile Ad Hoc Networks

This paper investigates the conditions in which trust-based cooperation on packet forwarding is unlikely to be developed in mobile ad hoc networks. The analysis is performed by combining genetic algorithms and replicator equation dynamics. We demonstrate that in the presence of a large number of unconditionally cooperative nodes a selfish permanent defection forwarding strategy is more successful than a forgiving version of reciprocal tit-for-tat.

Marcin Seredynski, Pascal Bouvry

A Comparison of Metaheurisitics for the Problem of Solving Parametric Interval Linear Systems

The problem of computing a hull solution of parametric interval linear systems with general dependencies is considered. It can be reduced to the problem of solving a family of constrained optimizatiom problems. In this study, different metaheuristics are used to solve those problems. Comparison of evolutionary algorithm, simulated annealing and tabu search algorithm together with analysis of variance tests are provided on the basis of three different practical problems.

Iwona Skalna, Jerzy Duda

Parametric Approximation of Functions Using Genetic Algorithms: An Example with a Logistic Curve

Whenever we have a set of discrete measures of a phenomenon and try to find an analytic function which models such phenomenon, we are solving a problem about finding some parameters that minimizes a computable error function. In this way, parameter estimation may be studied as an optimization problem, in which the fitness function we are trying to minimize is the error one. This work try to do that using a genetic algorithm to obtain three parameters of a function. Particularly, we use data about one village population over time to see the goodness of our algorithm.

Fernando Torrecilla-Pinero, Jesús A. Torrecilla-Pinero, Juan A. Gómez-Pulido, Miguel A. Vega-Rodríguez, Juan M. Sánchez-Pérez

Population-Based Metaheuristics for Tasks Scheduling in Heterogeneous Distributed Systems

This paper proposes a simple population based heuristic for task scheduling in heterogeneous distributed systems. The heuristic is based on a hybrid perturbation operator which combines greedy and random strategies in order to ensure local improvement of the schedules. The behaviour of the scheduling algorithm is tested for batch and online scheduling problems and is compared with other scheduling heuristics.

Flavia Zamfirache, Marc Frîncu, Daniela Zaharie

Modeling and Simulation of Electrochemical Processes

Modeling of Species and Charge Transport in Li–Ion Batteries Based on Non-equilibrium Thermodynamics

In order to improve the design of Li ion batteries the complex interplay of various physical phenomena in the active particles of the electrodes and in the electrolyte has to be balanced. The separate transport phenomena in the electrolyte and in the active particle as well as their coupling due to the electrochemical reactions at the interfaces between the electrode particles and the electrolyte will influence the performance and the lifetime of a battery. Any modeling of the complex phenomena during the usage of a battery has therefore to be based on sound physical and chemical principles in order to allow for reliable predictions for the response of the battery to changing load conditions. We will present a modeling approach for the transport processes in the electrolyte and the electrodes based on non-equilibrium thermodynamics and transport theory. The assumption of local charge neutrality, which is known to be valid in concentrated electrolytes, is explicitly used to identify the independent thermodynamic variables and fluxes. The theory guarantees strictly positive entropy production. Differences to other theories will be discussed.

Arnulf Latz, Jochen Zausch, Oleg Iliev

Finite Volume Discretization of Equations Describing Nonlinear Diffusion in Li-Ion Batteries

Numerical modeling of electrochemical process in Li-Ion battery is an emerging topic of great practical interest. In this work we present a Finite Volume discretization of electrochemical diffusive processes occurring during the operation of Li-Ion batteries. The system of equations is a nonlinear, time-dependent diffusive system, coupling the Li concentration and the electric potential. The system is formulated at length-scale at which two different types of domains are distinguished, one for the electrolyte and one for the active solid particles in the electrode. The domains can be of highly irregular shape, with electrolyte occupying the pore space of a porous electrode. The material parameters in each domain differ by several orders of magnitude and can be nonlinear functions of Li ions concentration and/or the electrical potential. Moreover, special interface conditions are imposed at the boundary separating the electrolyte from the active solid particles. The field variables are discontinuous across such an interface and the coupling is highly nonlinear, rendering direct iteration methods ineffective for such problems. We formulate a Newton iteration for a purely implicit Finite Volume discretization of the coupled system. A series of numerical examples are presented for different type of electrolyte/electrode configurations and material parameters. The convergence of the Newton method is characterized both as function of nonlinear material parameters and the nonlinearity in the interface conditions.

P. Popov, Y. Vutov, S. Margenov, O. Iliev

Contributed Papers

Numerical Study of Magnetic Flux in the LJJ Model with Double Sine-Gordon Equation

The decrease of the barrier transparency in superconductor-insulator-superconductor (SIS) Josephson junctions leads to the deviations of the current-phase relation from the sinusoidal form. The sign of second harmonics is important for many applications, in particular in junctions with a more complex structure like SNINS or SFIFS, where N is a normal metal and F is a weak metallic ferromagnet. In our work we study the static magnetic flux distributions in long Josephson junctions taking into account the higher harmonics in the Fourier-decomposition of the Josephson current. Stability analysis is based on numerical solution of a spectral Sturm-Liouville problem formulated for each distribution. In this approach the nullification of the minimal eigenvalue of this problem indicates a bifurcation point in one of parameters. At each step of numerical continuation in parameters of the model, the corresponding nonlinear boundary problem is solved on the basis of the continuous analog of Newton’s method. The solutions which do not exist in the traditional model have been found. The influence of second harmonic on stability of magnetic flux distributions for main solutions is investigated.

P. Kh. Atanasova, T. L. Boyadjiev, E. V. Zemlyanaya, Yu. M. Shukrinov

A Simple Preconditioner for the SIPG Discretization of Linear Elasticity Equations

We deal with the solution of the systems of linear algebraic equations arising from Symmetric Interior Penalty discontinuous Galerkin (SIPG) discretization of linear elasticity problems in primal (displacement) formulation. The main focus of the paper is on constructing a uniform preconditioner which is based on a natural splitting of the space of piecewise linear discontinuous functions. The presented approach has recently been introduced in [2] in the context of designing subspace correction methods for scalar elliptic partial differential equations and is extended here to linear elasticity equations, i.e., a class of vector field problems. Similar to the scalar case the solution of the linear algebraic system corresponding to the SIPG method is reduced to the solution of a problem arising from discretization by nonconforming Crouzeix-Raviart elements plus the solution of a well-conditioned problem on the complementary space.

B. Ayuso, I. Georgiev, J. Kraus, L. Zikatanov

Merger Bound States in 0 − π Josephson Structures

The possible static distributions of magnetic flux in a 0 − 


Josephson junction are described as a result of a nonlinear interaction between distributions of magnetic flux in “virtual” homogeneous and


junctions. The influence of an external magnetic field on some basic stable fluxons in a 0 − 


Josephson junction as well as in the corresponding “virtual” junctions has been studied.

Todor L. Boyadjiev, Hristo T. Melemov

Some Error Estimates for the Discretization of Parabolic Equations on General Multidimensional Nonconforming Spatial Meshes

This work is devoted to error estimates for the discretization of parabolic equations on general nonconforming spatial meshes in several space dimensions. These meshes have been recently used to approximate stationary anisotropic heterogeneous diffusion equations and nonlinear equations. We present an implicit time discretization scheme based on an orthogonal projection of the exact initial value. We prove that, when the discrete flux is calculated using a stabilized discrete gradient, the convergence order is


, where




) is the mesh size of the spatial (resp. time) discretization. This estimate is valid for discrete norms



${\mathcal W}^{1,\infty}(0,T;L^2(\Omega))$

under the regularity assumption

$u\in {\mathcal{C}}^2([0,T];{\mathcal{C}}^2(\overline{\Omega}))$

for the exact solution


. These error estimates are useful because they allow to obtain approximations to the exact solution and its first derivatives of order



Abadallah Bradji, Jürgen Fuhrmann

Finite-Volume Difference Scheme for the Black-Scholes Equation in Stochastic Volatility Models

We study numerically the two-dimensional Black-Scholes equation in stochastic volatility models [3]. For these models, starting from the conservative form of the equation, we construct a finite-volume difference scheme using the appropriate boundary conditions. The scheme is first order accurate in the space grid size. We also present some results from numerical experiments that confirm this.

Tatiana Chernogorova, Radoslav Valkov

On the Numerical Simulation of Unsteady Solutions for the 2D Boussinesq Paradigm Equation

For the solution of the 2D Boussinesq Paradigm Equation (BPE) an implicit, unconditionally stable difference scheme with second order truncation error in space and time is designed. Two different asymptotic boundary conditions are implemented: the trivial one, and a condition that matches the expected asymptotic behavior of the profile at infinity. The available in the literature solutions of BPE of type of stationary localized waves are used as initial conditions for different phase speeds and their evolution is investigated numerically. We find that, the solitary waves retain their identity for moderate times; for larger times they either transform into diverging propagating waves or blow-up.

Christo I. Christov, Natalia Kolkovska, Daniela Vasileva

Numerical Investigation of Spiral Structure Solutions of a Nonlinear Elliptic Problem

The nonlinear elliptic problem considered arises when investigating a class of self-similar solutions of a reaction-diffusion equation. We focus our study on the solutions of spiral structure. The proposed approach is based on the continuous analog of the Newton’s method and on the Galerkin finite element method. To reveal solutions of spiral structure appropriate initial approximations are used. The last ones are expressed by the confluent hypergeometric function










). Algorithms for accurate, fast and reliable computation of its values for broad ranges of the parameters




and of the variable


are worked out. A detailed numerical analysis of the evolution of the spiral structure solutions with respect to the medium parameters, including critical values, is carried out.

Milena Dimova, Stefka Dimova

Bidirectional Beam Propagation Method Applied for Lasers with Multilayer Active Medium

The vertical external cavity surface emitting laser (VECSEL) as a typical example of laser with multilayer active medium is considered. The round-trip operator technique is presented in the given paper based on the bidirectional beam propagation method (BiBPM). Similarly to traditional Fox-Li technique our method not requires explicit calculation of matrix of the round-trip operator and suits perfectly to Krylov subspace methods of linear algebra. The presented method is extended in natural way to non-linear case taking into account light-medium interaction. The results of modeling of a VECSEL with a resonant array of quantum wells are presented.

N. N. Elkin, A. P. Napartovich, D. V. Vysotsky

Analysis of the CBS Constant for Quadratic Finite Elements

We study the behavior of the CBS constant as a quality measure for hierarchical two-level splittings of quadratic FEM stiffness matrices. The article is written in the spirit of [3] where the focus is on the robustness with respect to mesh and coefficient anisotropy. The considered splittings are: Differences and Aggregates (DA); First Reduce (FR); and hierarchical P-decomposition (P). The presented results show sufficient conditions for the existence of optimal order Algebraic MultiLevel Iteration (AMLI) preconditioners.

Ivan Georgiev, Maria Lymbery, Svetozar Margenov

Sensitivity of Results of the Water Flow Problem in a Discrete Fracture Network with Large Coefficient Differences

This work deals with modelling of groundwater flow in compact rock with network of discrete fractures. The test problem is given by stochastically generated network of lines (fractures) with large variations of the aperture, conductivity, and discretisation element size which leads to the differences of the coefficients in the linear equations system up to ten orders of magnitude. We compare our own simulation code using mixed finite elements with commercial code NAPSAC using standard finite elements. Both codes produce consistent results, with differences in percents but unevenly distributed. Results from mixed finite elements have four orders of magnitude smaller error of mass balance than those from standard finite elements.

Milan Hokr, Jiří Kopal, Jan Březina, Petr Rálek

Fluxon Dynamics in Stacked Josephson Junctions

Sakai-Bodin-Pedersen model – a system of perturbed sine-Gordon equations – is used to study numerically the dynamics of Josephson phases in stacks of inductively coupled long Josephson Junctions (LJJs). The boundary conditions correspond to a stack of linear geometry. In order to obtain appropriate initial values for the dynamic problem the corresponding static problem is solved as well. We are interested in solutions having one or two moving fluxons in each junction and seek for conditions under which a bunching of fluxons is possible. The current-voltage dependencies and the current-velocity dependencies for different values of dissipation and coupling parameters for bunched and unbunched states are found. To solve numerically the above problems Finite element method and Finite difference method are used.

Ivan Hristov, Stefka Dimova

Global Convergence Properties of the SOR-Weierstrass Method

In this paper we give sufficient conditions for


-th approximations of the zeros of polynomial




) under the Successive Over-Relaxation Weierstrass method (SORW) fails on the next step. This is a further improvement of the known results. Interesting numerical examples are presented.

Vladimir Hristov, Nikolay Kyurkchiev, Anton Iliev

Numerical Solution of a Nonlinear Evolution Equation for the Risk Preference

A singular nonlinear partial differential equation (PDE) for the risk preference was derived by the first author in previous publications. The PDE is related to the Arrow-Pratt coefficient of relative risk aversion. In the present paper, we develop a Rothe-Bellman & Kalaba quasilinearization method on quasi-uniform space mesh to numerically investigate such PDE. Numerical experiments are discussed.

Naoyuki Ishimura, Miglena N. Koleva, Lubin G. Vulkov

A Numerical Approach for the American Call Option Pricing Model

We present a numerical approach of the free boundary problem for the Black-Scholes equation for pricing the American call option on stocks paying a continuous dividend. A fixed domain transformation of the free boundary problem into a parabolic equation defined on a fixed spatial domain is performed. As a result a nonlinear time-dependent term is involved in the resulting equation. Two iterative numerical algorithms are proposed. Computational experiments, confirming the accuracy of the algorithms are discussed.

Juri D. Kandilarov, Radoslav L. Valkov

A Numerical Study of a Parabolic Monge-Ampère Equation in Mathematical Finance

We propose iterative algorithms for solving finite difference schemes approximating an initial value problem of a parabolic Monge-Ampère equation, arising from the optimal investment of mathematical finance theory. We investigate positivity and convexity preserving properties of the numerical solution. Convergence results are also given. Numerical experiments demonstrate the efficiency of the algorithms and verify theoretical statements.

Miglena N. Koleva, Lubin G. Vulkov

Convergence of Finite Difference Schemes for a Multidimensional Boussinesq Equation

Conservative finite difference schemes

for the numerical solution of multi-dimensional Boussinesq-type equations are constructed and studied theoretically. Depending on the way the nonlinear term




) is approximated, two families of finite difference schemes are developed. Error estimates for these numerical methods in the uniform metric and the Sobolev space


are obtained. The extensive numerical experiments given in [7] for the one-dimensional problem show good precision and full agreement between the theoretical results and practical evaluation for single soliton and the interaction between two solitons.

Natalia T. Kolkovska

A Numerical Approach for Obtaining Fragility Curves in Seismic Structural Mechanics: A Bridge Case of Egnatia Motorway in Northern Greece

Fragility curves for Civil Engineering structures represent a critically important step in seismic damage estimation process. In the present article, a numerical methodology for the evaluation of such curves for bridges is presented. The methodology is based on the Finite Element Method, combines the nonlinear static pushover procedure with the capacity spectrum method and is applied for establishing fragility curves for an existing reinforced concrete bridge with seismic stoppers in the Krystalopigi - Psilorahi section of Egnatia Motorway, in the county of Epirus, northern Greece.

Asterios Liolios, Panagiotis Panetsos, Angelos Liolios, George Hatzigeorgiou, Stefan Radev

An Efficient Numerical Method for a System of Singularly Perturbed Semilinear Reaction-Diffusion Equations

In this work we consider a system of singularly perturbed semilinear reaction-diffusion equations. To solve this problem numerically, we construct a finite difference scheme of Hermite type, and combine this with standard central difference scheme in a special way on a piecewise-uniform Shishkin mesh. We prove that the method is third order uniformly convergent. Numerical experiments are conducted to demonstrate the efficiency of the present method.

S. Chandra Sekhara Rao, Sunil Kumar

A Comparison of Methods for Solving Parametric Interval Linear Systems with General Dependencies

This study compares two methods for solving interval linear systems whose coefficients are functions of interval parameters: the generalized Rump’s fixed-point iteration and Skalna’s Direct Method. Both methods have the same scope of application and require estimating the range of the same functions over a box. Evaluation of functional ranges using the simplest form of interval analysis produces wide intervals. This is due in a large part to the so-called interval dependency. To cope with the dependence problem, revised affine arithmetic with a new affine approximation of a product is used. Numerical examples are provided to show the advantages of Skalna’s Direct Method over generalized Rump’s fixed point iteration.

Iwona Skalna

Numerical Investigation of the Upper Bounds on the Convective Heat Transport in a Heated from below Rotating Fluid Layer

We apply the Galerkin method in order to obtain numerical solution of the Euler - Lagrange equations for the variational problem for the upper bounds on the convective heat transport in a fluid layer under the action of intermediate and strong rotation. The role of the numerical investigation in such kind of variational problems is to obtain the upper bounds for the case of small and intermediate values of the Rayleigh and Taylor numbers in addition to the analytical asymptotic theory which leads to the upper bounds for the case of large values of the above two characteristic dimensionless numbers. The application of the Galerkin method reduces the Euler - Lagrange equations to a system of nonlinear algebraic equations. This system is solved numerically by the Powel hybrid method. We observe that the Powel hybrid method guarantees satisfactory fast rate of convergence from the guess solution to the solution of the system of equations. We present and discuss several results from the numerical computations.

Nikolay Vitanov


Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.



Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!