Parallel Numerical Methods
General data
Course ID: | 103A-CSCSN-MSA-EPNM |
Erasmus code / ISCED: | (unknown) / (unknown) |
Course title: | Parallel Numerical Methods |
Name in Polish: | Parallel Numerical Methods |
Organizational unit: | The Faculty of Electronics and Information Technology |
Course groups: |
( Computer Systems and Networks - Advanced )-Computer Systems and Networks-M.Sc.-EITI ( Courses in English )--eng.-EITI ( Technical Courses )---EITI ( Technical Courses )--eng.-EITI |
ECTS credit allocation (and other scores): |
6.00
|
Language: | English |
(in Polish) Jednostka decyzyjna: | (in Polish) 103000 - Wydział Elektroniki i Technik Informacyjnych |
(in Polish) Kod wydziałowy: | (in Polish) EPNM |
(in Polish) Numer wersji: | (in Polish) 1 |
Short description: |
The aim of the lecture is to acquaint the students with the problem of using parallel and distributed calculations to the realization of selected numerical methods. Their scope covers selected methods of linear algebra (finite and iterative), contraction mappings, conjugate gradient methods, decomposition methods for linear programming problems and the branch and bound method for solving linear integer and mixed integer problems. The additional goal is to familiarize students with the distributed calculations, when the number of available processes is very small and acquaint them with the work with tools from the Matlab Parallel Computing toolbox. |
Full description: |
The aim of the lecture is to acquaint the students with the problem of using parallel and distributed calculations to the realization of selected numerical methods. Scope covers selected methods of linear algebra (finite and iterative), decomposition methods for linear programming problems and branch and bound method. Lectures: Introduction to parallel and distributed architectures, classification of parallel and distributed computing systems, effectiveness measures, Amdahl`s law, two methods for calculating randomly the π number (random generation of numbers in a square on the plain, Bailey–Borwein–Plouffe formula). Linear systems with triangular matrices, partitioning of the system matrix into blocks, forward substitution and backward substitution. Tridiagonal systems and odd-even reduction. Gaussian elimination - distributed realization. Given`s rotations - distributed realization. Fast direct matrix inverse algorithm based on the Caley-Hamilton theorem and the characteristic polynomial, Conjugate gradient and preconditioned conjugate gradient methods. Fast iterative matrix inverse making use of the Newton iterations.. Classical iterative methods for systems of linear equations (Jacobi, Gauss-Seidel, Jacobi overrelaxation, successive overrelaxation, Richardson methods). Preparatory material to the decomposition methods, Part I. simplex method for solving linear programming problems. Preparatory material to the decomposition methods, Part II. Lagrange duality theory for linear programming problems. Decomposition methods for linear programming, Danzig_Wolfe decomposition, applied to the primal problem with the block angular structure of the constraints matrix. Decomposition methods for linear programming, Bender`s decomposition, applied to the problem with the dual block angular structure (ladder structure). Branch and bound method for integer and mixed-integer problems. Project: Project tasks are organized in such way that should convince the students to keep the balance between the number of available processors and the number of used processes. In order to realize that goal four small projects of growing difficulty level are foreseen. Calculations are run with the aid of the tools from the Parallel Calculations Toolbox in Matlab. The first project not evaluated is to calculate finite sum of an infinite arithmetic serie in the distributed fashion. Every student works with the same serie. In the second project every student repeats the task one, but this time has got personally assigned arithmetic serie. In the third project students are asked to realize matrix/matrix multiplication in a distributed way defining the number of processes close to the number of available processors an compare it with a calculations invoking excessive number of processes. In project number four one has to implement one of the methods presented during the lectures (usually from the linear algebra). The data are of two origins: 1. delivered by the teacher, 2. taken from the repository of linear algebra problems, available under the url: https://sparse.tamu.edu/HB |
Bibliography: |
|
Learning outcomes: |
Knowlegde
Skills
|
Assessment methods and assessment criteria: |
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. |
Classes in period "Summer Semester 2023/2024" (in progress)
Time span: | 2024-02-19 - 2024-09-30 |
Navigate to timetable
MO WYK
PRO
TU W TH FR |
Type of class: |
lectures, 30 hours, 48 places
project , 30 hours, 48 places
|
|
Coordinators: | Andrzej Karbowski | |
Group instructors: | Andrzej Karbowski | |
Students list: | (inaccessible to you) | |
Examination: | Exam | |
(in Polish) Jednostka realizująca: | (in Polish) 103100 - Instytut Automatyki i Informatyki Stosowanej |
Classes in period "Summer Semester 2022/2023" (past)
Time span: | 2023-02-20 - 2023-09-30 |
Navigate to timetable
MO WYK
PRO
TU W TH FR |
Type of class: |
lectures, 30 hours, 48 places
project , 30 hours, 48 places
|
|
Coordinators: | Andrzej Stachurski | |
Group instructors: | Andrzej Stachurski | |
Students list: | (inaccessible to you) | |
Examination: | Exam | |
(in Polish) Jednostka realizująca: | (in Polish) 103100 - Instytut Automatyki i Informatyki Stosowanej |
Classes in period "Summer Semester 2021/2022" (past)
Time span: | 2022-02-23 - 2022-09-30 |
Navigate to timetable
MO WYK
PRO
TU W TH FR |
Type of class: |
lectures, 30 hours, 48 places
project , 30 hours, 48 places
|
|
Coordinators: | Andrzej Stachurski | |
Group instructors: | Andrzej Stachurski | |
Students list: | (inaccessible to you) | |
Examination: | Exam | |
(in Polish) Jednostka realizująca: | (in Polish) 103100 - Instytut Automatyki i Informatyki Stosowanej |
Classes in period "Summer Semester 2020/2021" (past)
Time span: | 2021-02-20 - 2021-09-30 |
Navigate to timetable
MO WYK
PRO
TU W TH FR |
Type of class: |
lectures, 30 hours, 35 places
project , 30 hours, 35 places
|
|
Coordinators: | Andrzej Stachurski | |
Group instructors: | Andrzej Stachurski | |
Students list: | (inaccessible to you) | |
Examination: | Exam | |
(in Polish) Jednostka realizująca: | (in Polish) 103100 - Instytut Automatyki i Informatyki Stosowanej |
Classes in period "Summer Semester 2019/2020" (past)
Time span: | 2020-02-22 - 2020-09-30 |
Navigate to timetable
MO WYK
PRO
TU W TH FR |
Type of class: |
lectures, 30 hours, 35 places
project , 30 hours, 35 places
|
|
Coordinators: | Andrzej Stachurski | |
Group instructors: | Andrzej Stachurski | |
Students list: | (inaccessible to you) | |
Examination: | Exam | |
(in Polish) Jednostka realizująca: | (in Polish) 103100 - Instytut Automatyki i Informatyki Stosowanej |
Classes in period "Summer Semester 2018/2019" (past)
Time span: | 2019-02-18 - 2019-09-30 |
Navigate to timetable
MO WYK
PRO
TU W TH FR |
Type of class: |
lectures, 30 hours, 35 places
project , 30 hours, 35 places
|
|
Coordinators: | Andrzej Stachurski | |
Group instructors: | Andrzej Stachurski | |
Students list: | (inaccessible to you) | |
Examination: | Exam | |
(in Polish) Jednostka realizująca: | (in Polish) 103100 - Instytut Automatyki i Informatyki Stosowanej |
Copyright by Warsaw University of Technology.