Institute of Information and Communication Technologies Department of Parallel Algorithms
Department of Parallel Algorithms
Bulgarian version



Field of Research

The main research activities of the Department are in the following areas:

  • Monte Carlo algorithms (differential and integral equations, linear algebra, spectral problems, data processing)
  • Statistical numerical methods with supper convergent probability error.
  • Parallel algorithms and GRID
  • Mathematical modeling and scientific computation in Environmental Mathematics, Gas discharge plasma, Semi-conductors physics.
  • Image processing
  • Computational geometry and topological graph theory
  • Metaheuristics for combinatorial optimization problems
  • Development of Monte Carlo approaches for solving Wigner-Boltzmann equation and Barker-Ferry equation (describing solid-state physics, classical and quantum models of electron transport in micro- and nano-structures) for different physical conditions
  • Simulation of nanostructures and analysis of the quantum phenomena governing their electrical behavior; Femtosecond carrier evolution: collisional broadening and retardation, intra-collisional field effect, ultrafast carrier transfer in quantum wires.
  • LLT model for ionospheric events
  • Protein folding problems
  • High-Performance Computing and Parallel Algorithms
  • Numerical Methods for Partial Differential Equations
  • Numerical treatment of large-scale air pollution problems
  • Programming for vector and parallel (with shared and distributed memory) computers

The Department of Parallel Algorithms participates in several international joint research programs financed by the European Commission, NATO Science and Bulgarian NSF (see Activities - National Grants and International Projects).

The research is oriented to the design of novel algorithms for Linear Algebra Problems with dense, sparse and structured matrices applying new approaches. The prime examples are Monte Carlo parallel methods for solving spectral problems for large sparse and dense matrices. The developed methods are applied for stability study of large physical systems using so called epsilon-spectra or portraits of matrices.

Efficient and superconvergent Monte Carlo algorithms for numerical integration of multidimensional integrals are also studied and the computational complexity of such algorithms is estimated.

A special class of Monte Carlo methods for solving transport problems describing by linear and non-linearintegral equations of Fredholm type are introduced and studied. New results for the statistical error estimates of the quality of the algorithms are obtained and published in leading international journals.

Mixed finite element method for second order elliptic boundary value problems describing transport phenomena is studied. Optimal error estimates in the cases of lumped mass approximation and regular local refinement are derived.

Monte Carlo methods are considered as the most reliable methods for charge-transport modelling in semiconductors. The development of device modelling physics in the last years involved so small space and timescales that the applicability of semi-classical transport.

New parallel algorithms for general sparse matrices are prepared and used for coarse-grained parallel computations. Since the established of the Department we have been dealing very actively with supercomputing. New, high-performance (vector and parallel) algorithms and software for different kind of supercomputers (vector and/or parallel with shared and distributed memory) are studying and performing. The main applications are in the fields of the ecology (transport of air pollutants, source-receptor relations, etc.), solid and quantum mechanics, semiconductors, etc. The investigations are connected with finding optimal algorithms according to the arithmetic complexity and communications as well as an optimal use of the cache and hierarchical memories of the new generation computers.

Metaheuristic and stochastic methods are high-level general procedures that coordinates simple heuristics and rules to find good approximate solution to computationally (NP) difficult problems for a reasonable time and computational effort. Among them are simulated annealing, tabu search, genetic algorithm, ant colony optimization. There are some of most effective solution strategies for solving optimization problems in practice and have been applied to a large variety of problems. Algorithms for real-life and industrial problems are investigated, including: economy (resource management); telecommunications (scheduling, sensor an radar management, GPS networks), biology (protein folding) and so on. The main results are theoretical as well as practical. A memetic simulated annealing algorithm is developed which is applied on GPS surveying problem. Representation of the initial temperature, like a function of the initial data is considered. Other metaheuristic is ant colony optimization. Metodology for semi random start of the construction of solutions is developed. Ant algorithm for antenna (sensor) positioning problem is developed and it outperforms existing ones.

A mathematical model (LLT model) of ionospheric events is developed. The model can detaches and retraced ionospheric events with given size and continuance.

A protein model is developed which can be used for predicting the protein folding, for construction proteins with given folding and for predicting the changes of the folding if some of the amino acids are changed with others. This method is very useful for drug design. Its advantages are that it is fast, easy to be implemented and do not needs big computational ressourses.

Research efforts are directed to applying new approaches in computer graphics and developing of efficient Monte Carlo and Quasi Monte Carlo methods for photorealistic image creation. From mathematical point of view, photorealistic image synthesis is equivalent to the solution of a Fredholm type integral equation called Rendering Equation. The task for finding an acceptable Monte Carlo or Quasi Monte Carlo solution of the multidimensional Rendering equations, so the synthesised images looks photorealistic is very hard and computational expensive. We respond to these challenges by applying new approaches to the design of novel efficient Monte Carlo and Quasi Monte Carlo algorithms, as well as study them. New results for the computational complexity of super convergent Monte Carlo and Quasi Monte Carlo algorithms with uniform separation of integration domain are obtained and published.

The Department organizes a number of scientific meetings - conferences, workshops and seminars. These meetings traditionally bring together participants from practically all European countries, USA, Japan and Russia providing opportunities for active exchange of ideas and experience.


© Department of Parallel Algorithms, IICT-BAS.                                                                                                                    Webmasters