

Field of Research The main research activities of the Department are in the following areas:
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 epsilonspectra 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 nonlinearintegral 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 chargetransport modelling in semiconductors. The development of device modelling physics in the last years involved so small space and timescales that the applicability of semiclassical transport. New parallel algorithms for general sparse matrices are prepared and used for coarsegrained parallel computations. Since the established of the Department we have been dealing very actively with supercomputing. New, highperformance (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, sourcereceptor 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 highlevel 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 reallife 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, IICTBAS.
Webmasters
