Warsaw University of Technology - Central Authentication System
Strona główna

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 Basic information on ECTS credits allocation principles:
  • the annual hourly workload of the student’s work required to achieve the expected learning outcomes for a given stage is 1500-1800h, corresponding to 60 ECTS;
  • the student’s weekly hourly workload is 45 h;
  • 1 ECTS point corresponds to 25-30 hours of student work needed to achieve the assumed learning outcomes;
  • weekly student workload necessary to achieve the assumed learning outcomes allows to obtain 1.5 ECTS;
  • work required to pass the course, which has been assigned 3 ECTS, constitutes 10% of the semester student load.
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:

  1. Bertsekas D.P., J.N. Tsitsiklis: Parallel and Distributed Calculation. Numerical Methods. Prentice Hall, 1989.
  2. Matlab documentation.
  3. Parallel Computing Toolbox in Matlab.
  4. Bailey–Borwein–Plouffe formula, Wikipedia, https://en.wikipedia.org/wiki/Bailey–Borwein–Plouffe_formula#References, access 24.11.2021
Learning outcomes:

Knowlegde

  • knows methods of parallelizing calculations in basic numerical algorithms of linear algebra (finite and iterative), decomposition methods of linear programming problems and branch and bound methods for integer and mixed integer problems.

Skills

  • is able to plan and implement basic algorithms for solving sets of linear equations in the way permitting to speed up calculations on computer machines with small number of processors. Can do that also in the case of decomposition methods of linear programming problems and branch and bound methods in the case of integer and mixed-integer problems.
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
Selected timetable range:
Navigate to timetable
Type of class:
lectures, 30 hours, 48 places more information
project , 30 hours, 48 places more information
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
Selected timetable range:
Navigate to timetable
Type of class:
lectures, 30 hours, 48 places more information
project , 30 hours, 48 places more information
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
Selected timetable range:
Navigate to timetable
Type of class:
lectures, 30 hours, 48 places more information
project , 30 hours, 48 places more information
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
Selected timetable range:
Navigate to timetable
Type of class:
lectures, 30 hours, 35 places more information
project , 30 hours, 35 places more information
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
Selected timetable range:
Navigate to timetable
Type of class:
lectures, 30 hours, 35 places more information
project , 30 hours, 35 places more information
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
Selected timetable range:
Navigate to timetable
Type of class:
lectures, 30 hours, 35 places more information
project , 30 hours, 35 places more information
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

Course descriptions are protected by copyright.
Copyright by Warsaw University of Technology.
pl. Politechniki 1, 00-661 Warszawa tel: (22) 234 7211 https://pw.edu.pl contact accessibility statement USOSweb 7.0.0.0-7 (2024-03-18)