Řídké matice v numerické matematice - NMNV533

• Anglický název: Sparse Matrices in Numerical Mathematics
• Zajišťuje: Katedra numerické matematiky (32-KNM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2020
• Semestr: zimní
• E-Kredity: 5
• Rozsah, examinace: zimní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• Garant: prof. Ing. Miroslav Tůma, CSc.
• Vyučující: prof. Ing. Miroslav Tůma, CSc.
• Třída: M Mgr. MMIB > Povinně volitelné; M Mgr. NVM; M Mgr. NVM > Povinně volitelné
• Kategorizace předmětu: Matematika > Numerická analýza

Anotace

čeština

Cílem tohoto předmětu je poskytnout studentům představu o soudobých technikách práce s řídkými maticemi při řešení rozsáhlých a řídkých soustav rovnic. Takové systémy vznikají v mnoha praktických úlohách matematického modelování, například jako výsledek diskretizace parciálních diferenciálních rovnic, ale i v aplikacích ekonomických či v moderních chemických a biologických vědách. Předmět je vhodný pro magisterské i doktorandské studenty se zájmem o moderní výpočetní metody a jejich implementace na počítačích.

Poslední úprava: Kučera Václav, doc. RNDr., Ph.D. (15.01.2019)

angličtina

The goal of this course is to present contemporary algorithms and techniques dealing with sparse matrices for solving large and sparse systems of linear equations. Such systems arise in many practical problems of mathematical modeling, for example as a result of discretizations of partial differential equations as well as in applications in such diverse fields as management science, economy or chemical and biological sciences.

Poslední úprava: Kučera Václav, doc. RNDr., Ph.D. (15.01.2019)

Cíl předmětu

čeština

Dát základní představu o výpočetních algoritmech, kde se můžeme setkat s řídkými maticemi. Zaměření

předmětu pokrývá především přímé metody, ale zmíněny jsou i přibližné postupy, které se uplatňují

v iteračních metodách.

Poslední úprava: Tůma Miroslav, prof. Ing., CSc. (08.10.2017)

angličtina

To understand basic ideas related to sparse matrices in direct methods as well as approximate factorizations

used as preconditioners in iterative methods.

Poslední úprava: Tůma Miroslav, prof. Ing., CSc. (08.10.2017)

Podmínky zakončení předmětu

čeština

Požadavky k zápočtu:

• na cvičeních studenti dostanou jedno až dvě témata zápočtové prezentace

• prezentaci předvedou v termínu po dohodě s cvičícím

Bude-li nutno, vše bude distanční.

„povaha kontroly studia předmětu“ vylučuje opakování této kontroly, POS, čl. 8, odst. 2

Poslední úprava: Tůma Miroslav, prof. Ing., CSc. (25.09.2020)

angličtina

Needed to get credits:

• students will independently prepare one or two presentations for the other students

based on the agreement with the lecturer

It necessary, everything will be distant.

Poslední úprava: Tůma Miroslav, prof. Ing., CSc. (25.09.2020)

Literatura

čeština

T. Davis. Direct Methods for Sparse Linear Systems. Fundamentals of Algorithms, 2. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2006.

G. Meurant. Computer Solution of Large Linear Systems. Studies in Mathematics and its Applications, 28. North-Holland Publishing Co., Amsterdam, 1999.

I.S. Duff, A. Erisman, J. Reid. Direct methods for Sparse Matrices, Clarenton Press, Oxford University Press, 1986.

J. Dongarra, I.S. Duff, D. Sorensen, H. A. van der Vorst. Solving Linear Systems on Vector and Shared Memory Computers, SIAM, 1991.

A.George, J. Liu: Computer Solution of Sparse Positive Definite Systems, Prentice-Hall, 1981.

J. Liu: The role of elimination trees in sparse factorization, SIAM. J. Matrix Anal. Appl. 11 (1990), 134-172.

Poslední úprava: Kučera Václav, doc. RNDr., Ph.D. (15.01.2019)

Metody výuky

čeština

Přednášky a cvičení distančním způsobem.

Poslední úprava: Tůma Miroslav, prof. Ing., CSc. (25.09.2020)

angličtina

Lectures and tutorials in a distant way.

Poslední úprava: Tůma Miroslav, prof. Ing., CSc. (25.09.2020)

Požadavky ke zkoušce

čeština

Požadavky ke zkoušce:

• zkouška je distanční, její obsah odpovídá sylabu.

• studenti dostanou jednu šířeji zaměřenou otázku

• studenti budou vyzkoušeni ze základního porozumění

• mají dost času, aby si na ni připravili odpověď

• při ověřování znalostí se zkoušející může ptát na související věci

Poslední úprava: Tůma Miroslav, prof. Ing., CSc. (25.09.2020)

angličtina

Examination according to the syllabus. Posssibly distant.

• students will be asked one thematically general question

• students will have enough time to prepare their answer

• they should show basic understanding to parallel matrix computations

• examining persons can pose subquestions related to the main question

Poslední úprava: Tůma Miroslav, prof. Ing., CSc. (25.09.2020)

Sylabus

čeština

1. Základní termíny týkající se počítání, složitosti, rozkladů matic.

2. Řídké matice, jejich modelování pomocí grafů a vznik řídkých matic v aplikacích.

3. Grafová interpretace Choleského faktorizace a LU rozkladu. Teoretické základy a algoritmická

syntéza přímých řešičů.

4. Souvislost přímých metod s nepřesnými maticovými rozklady a jejich použití pro

předpodmiňování soustav rovnic. Řídká QR faktorizace a řídké rozklady indefinitních matic.

5. Implementace přesných i nepřesných řídkých řešičů.

Poslední úprava: Tůma Miroslav, prof. Ing., CSc. (08.10.2017)

angličtina

1. Basic terminology from computers, factorizzations and computational complexity.

2. Direct methods, their representation by graphs and sparse matrices in applications.

3. Graph interpretation of Cholesky factorization and LU decomposition. Theoretical basis and

algorithmic synthesis of sparse direct solvers.

4. Direct and approximate methods. The use of approximate decompositions in preconditioning.

Sparse QR decomposition. Sparse decompositions of symmetric indefinite systems.

5. Implementations of direct and approximate solvers.

The exam will test basic understanding to the subject described in this sylabus.

The exam can preceed getting credits. The credits will be given based on the student activity.

In order to ge the credits, at least one talk based on an independent work offered by the lecturer should

be given.

Poslední úprava: Tůma Miroslav, prof. Ing., CSc. (03.10.2017)

Vstupní požadavky

čeština

Vstupním požadavkem je předmět bakalářského studia NMAG101 Lineární algebra a geometrie 1.

Poslední úprava: Tůma Miroslav, prof. Ing., CSc. (16.05.2018)

angličtina

Premiliminary for this course is only a basic knowledge of linear algebra that corresponds, for example, to NMAG101.

Some knowledge of basic graph theory is an advantage but not a necessity.

Poslední úprava: Tůma Miroslav, prof. Ing., CSc. (16.05.2018)