Parallel Numerical Methods

The aim of the lecture is to acquaint students with the selected numerical methods for parallel and distributed computations. Their scope covers some linear algebra methods (finite and iterative), contraction mappings, unconstrained optimization methods (gradient, Newton and quasi_newton methods) and constrained optimization methods (decomposition methods), global optimization methods (clustering and genetic algorithms) and algorithms for finding association mining rules in large data bases. Additional goal attained by means of the project is to make the students familiar with the distributed computation environments PVM (Parallel Virtual Machine) and MPI (Message Passing Interface).




Lecture contents

1. Introduction to parallel and distributed architectures, classification of parallel and distributed computing systems, effectiveness measures, Amdahl`s law.


2. Linear systems with triangular matrices, partitioning of the system matrix into blocks, back substitution.


3. Tridiagonal systems and odd-even reduction.


4. Parallelization of the Gaussian elimination and Given`s rotations.


5. Fast direct matrix inversion algorithm based on the Caley-Hamilton theorem and the characteristic polynomial, classical iterative methods for systems of linear equations (Jacobi, Gauss-Seidel, Jacobi overrelaxation, successive overrelaxation, Richardson methods).


6. Fast iterative matrix inverse.


7. Conjugate gradient and preconditioned conjugate gradient methods.


8. Convergence of pseudo-contracting and contracting iterations, iterative methods for nonlinear problems,


9. Contractions over Cartesian product sets, Gauss-Seidel methods, convergent solution methods, some useful contraction mappings.


10. Unconstrained optimization, Jacobi and Gauss-Seidel method, gradient algorithm, Newton and approximate Newton methods.


11. Constrained optimization, optimality condition and the projections theorem.
    
12. Decomposition methods for constrained optimization, Bender`s decomposition.


13. Global optimization, clustering methods.


14. Global optimization, genetic algorithms.


15. Parallel and distributed association mining, mining complexity, algorithms for finding association mining rules.

EPNM - it is necessary to realize positively evaluated project and pass the exam; final mark is the mean value of the two marks: from the project and exam.