Efficient Parallel Algorithms

For certain problems the use of sophisticated numerical schemes may still not be sufficient to obtain the desired performance. At this point, one should consider the development of efficient parallel algorithms that are tailored for standard high performance cluster systems with either shared or distributed memory.

Our research in the area of efficient parallel algorithms for scientific computing includes the following topics:

• Operator Splitting Techniques
  For certain problems the use of sophisticated numerical schemes may still not be enough to obtain the desired performance. At this point, one should consider the use of high performance cluster systems. In many cases, the parallelisation of fast sequential algorithms is a very challenging task. In [1] [2] [3] we present some parallelisation strategies for a nonlinear diffusion filter that is based on a highly efficient additive operator splitting (AOS) scheme. Using the inter-process communication standard MPI the implemented algorithm showed an excellent scaling behaviour with speed up factors of up to 209 for 256 processors. The research on this topic is in cooperation with the Computer Architecture Group at the University of Heidelberg in Germany.
  
  
  
  
  
• Domain Decomposition Methods
  Domain decomposition is a frequently used strategy for parallelizing linear and nonlinear system of equations. Thereby the original problem is divided in sub-domains, for which the problem is solved locally. From time to time boundaries are updated by solving additional equation systems that take the global context into consideration. In [4] [5] [6] [7] we have developed such domain decomposition strategies for parallel computation of optic flow fields. The research on this topic is in cooperation with the Image and Pattern Analysis Group at the University of Heidelberg in Germany.

1. A. Bruhn, T. Jakob, M. Fischer, T. Kohlberger, J. Weickert, U. Brüning, C. Schnörr:
   Designing 3-D nonlinear diffusion filters for high performance cluster computing.
   In L. Van Gool (Ed.): Pattern Recognition. Lecture Notes in Computer Science, Vol. 2449, Springer, Berlin, 290-297, 2002.

2. D. Slogsnat, M. Fischer, A. Bruhn, J. Weickert, U. Brüning:
   Low level parallelization of nonlinear diffusion filtering algorithms for cluster computing environments.
   In H. Kosch, L. Böszörményi, H. Hellwagner (Eds.): Euro-Par 2003. Parallel Processing. Lecture Notes in Computer Science, Vol. 2790, Springer, Berlin, 481-490, 2003.
   

3. A. Bruhn, T. Jakob, M. Fischer, T. Kohlbeger, J. Weickert, U. Brüning, C. Schnörr:
   High performance cluster computing with 3-D nonlinear diffusion filters.
   Real-Time Imaging, Vol. 10, No. 1, 41-51, 2004.
   Revised version of Technical Report No. 87, Department of Mathematics, Saarland University, Saarbrücken, Germany, 2003.
   

4. T. Kohlberger, C. Schnörr, A. Bruhn, J. Weickert:
   Domain decomposition for parallel variational optic flow computation.
   In B. Michaelis, G. Krell (Eds.): Pattern Recognition. Lecture Notes in Computer Science, Vol. 2781, Springer, Berlin, 196-202, 2003.
   

5. T. Kohlberger, C. Schnörr, A. Bruhn, J. Weickert:
   Parallel variational motion estimation by domain decomposition and cluster computing..
   In T. Pajdla, J. Matas (Eds.): Computer Vision - ECCV 2004. Lecture Notes in Computer Science, Vol. 3024, Springer, Berlin, 205-216, 2004.

6. T. Kohlberger, C. Schnörr, A. Bruhn, J. Weickert:
   Domain Decomposition for Variational Optical Flow Computation.
   IEEE Transactions on Image Processing, Vol. 14/8, 1125-1137, 2005
   

7. T. Kohlberger, C. Schnörr, A. Bruhn, J. Weickert:
   Domain decomposition for nonlinear problems: a control-theoretic approach.
   Technical Report 2005/3, Computer Science Series, University of Mannheim, April 2005.
   

MIA Group
©2001-2023
The author is not
responsible for
the content of
external pages.

Imprint - Data protection