Politechnika Warszawska - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Parallel Numerical Methods

Informacje ogólne

Kod przedmiotu: 103A-CSCSN-MSA-EPNM Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Parallel Numerical Methods
Jednostka: Wydział Elektroniki i Technik Informacyjnych
Grupy: ( Computer Systems and Networks - Advanced )-Computer Systems and Networks-M.Sc.-EITI
( Courses in English )--eng.-EITI
( Przedmioty techniczne )---EITI
( Technical Courses )--eng.-EITI
Punkty ECTS i inne: 6.00
Język prowadzenia: angielski
Jednostka decyzyjna:

103000 - Wydział Elektroniki i Technik Informacyjnych

Kod wydziałowy:

EPNM

Numer wersji:

1

Skrócony opis:

Celem wykładu jest zapoznanie studentów z wybranymi metodami numerycznymi do obliczeń równoległych i rozproszonych. Ich zakres obejmuje pewne metody algebry liniowej (skończone i iteracyjne), odwzorowania zwężające, metody optymalizacji bez ograniczeń (metody gradientowe, Newtona i quasinewtonowskie) i z ograniczeniami (metoda dekompozycji), metody optymalizacji globalnej (klasteryzacji oraz algorytmy genetyczne) oraz algorytmy wyszukiwania reguł w dużych bazach danych. Celem dodatkowym realizowanym poprzez projekt jest zapoznanie studentów ze środowiskami do obliczeń rozproszonych PVM i MPI.

Pełny opis: (tylko po angielsku)

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.


Projects contents
The aim of the project is to acquaint students with the PVM (Parallel Virtual Machine) and MPI (Message Passing Interface) developed for realization of distributed calculations over a network of SUN workstations. The students are asked to prepare two projects during the semester. The first one is very simple as for instance "write a small program calculating value of a scalar product of two vectors in parallel way in the PVM environment. The second one is more complicated, for instance "Write a short C-language program implementing the back-substitution method for solving the set of linear equations $Ax = b$ with lower triangular matrix $A$. Use this method to obtain the inverse of the matrix $A$. Program should make use of calculations distributed on the net of computers. Realization in the MPI environment on the SUN Workstations network".

Literatura: (tylko po angielsku)

    Basic literature:

    1. Bertsekas D.P., J.N. Tsitsiklis: Parallel and Distributed Calculation. Numerical Methods. Prentice Hall, 1989.

    2. Zaki M.J.: "Parallel and Distributed Association Mining: A Survey", IEEE Concurrency v.7, No. 4, 1999, pp. 14-25.

    3. Törn A., A. Žilinskas: Global Optimization. Springer Verlag, 1989.


    Additional reading:


    1. Gill P., W. Murray, M. Wright: Practical Optimization. Academic Press 1981.

    2. Bertsekas D.P.: Nonlinear Programming. Athena Scientific, Belmont, Massachusets 1995.

Metody i kryteria oceniania: (tylko po angielsku)

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.

Zajęcia w cyklu "rok akademicki 2019/2020 - sem. letni" (w trakcie)

Okres: 2020-02-22 - 2020-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 35 miejsc więcej informacji
Wykład, 30 godzin, 35 miejsc więcej informacji
Koordynatorzy: Andrzej Stachurski
Prowadzący grup: Andrzej Stachurski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2018/2019 - sem. letni" (zakończony)

Okres: 2019-02-18 - 2019-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 35 miejsc więcej informacji
Wykład, 30 godzin, 35 miejsc więcej informacji
Koordynatorzy: Andrzej Stachurski
Prowadzący grup: Andrzej Stachurski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2017/2018 - sem. letni" (zakończony)

Okres: 2018-02-19 - 2018-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 35 miejsc więcej informacji
Wykład, 30 godzin, 35 miejsc więcej informacji
Koordynatorzy: Andrzej Stachurski
Prowadzący grup: Andrzej Stachurski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2016/2017 - sem. letni" (zakończony)

Okres: 2017-02-20 - 2017-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 35 miejsc więcej informacji
Wykład, 30 godzin, 35 miejsc więcej informacji
Koordynatorzy: Andrzej Stachurski
Prowadzący grup: Andrzej Stachurski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2015/2016 - sem. letni" (zakończony)

Okres: 2016-02-23 - 2016-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 35 miejsc więcej informacji
Wykład, 30 godzin, 35 miejsc więcej informacji
Koordynatorzy: Andrzej Stachurski
Prowadzący grup: Andrzej Stachurski
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Zajęcia w cyklu "rok akademicki 2014/2015 - sem. letni" (zakończony)

Okres: 2015-02-23 - 2015-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Projekt, 30 godzin, 30 miejsc więcej informacji
Wykład, 30 godzin, 30 miejsc więcej informacji
Koordynatorzy: (brak danych)
Prowadzący grup: (brak danych)
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Jednostka realizująca:

103100 - Instytut Automatyki i Informatyki Stosowanej

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Warszawska.