Approximations by low-rank matrices and their applications

• Název práce v češtině: Aproximace maticemi malé hodnosti a jejich aplikace
• Název v anglickém jazyce: Approximations by low-rank matrices and their applications
• Klíčová slova: aproximace maticemi nízké hodnosti, řídké matice, iterační metody pro řešení rozsáhlých soustav algebraických rovnic, předpodmínění
• Klíčová slova anglicky: low-rank matrix approximations, sparse matrices, iterative methods for solving large linear algebraic equations, preconditioning
• Akademický rok vypsání: 2017/2018
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Katedra numerické matematiky (32-KNM)
• Vedoucí / školitel: prof. Ing. Miroslav Tůma, CSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 22.08.2017
• Datum zadání: 14.09.2017
• Datum potvrzení stud. oddělením: 21.06.2018
• Datum a čas obhajoby: 05.09.2018 00:00
• Datum odevzdání elektronické podoby: 20.07.2018
• Datum odevzdání tištěné podoby: 20.07.2018
• Datum proběhlé obhajoby: 05.09.2018
• Oponenti: doc. Ing. Miroslav Rozložník, Dr.

Zásady pro vypracování

Potřeba řešit stále rozsáhlejší soustavy rovnic které souvisejí s pokrokem
matematických metod a inženýrských aplikací vedla v posledních letech k velkému rozvoji strategií
aproximace systémových matic pomocí matic nízké hodnosti. V současné době jsou algoritmy
takových aproximací v mnoha případech zdatnými konkurenty algoritmů explicitně založených
na grafové struktuře nulových a nenulových prvků, které jsou souhrnně nazývány
algoritmy pro řídké matice. Za počáteční impuls tohoto rozvoje aproximace maticemi nízkých hodností
je možné považovat návrh rychlé multipólové metody v problému mnoha těles, ale podobné přístupy
byly motivovány i dalšími aplikačními poli jako jsou, například, řešení
integrálních rovnic či eliptických parciálních diferenciálních rovnic.
V dnešní době toto téma zahrnuje i silnou algebraickou část s impulsy pro přímé
i iterační řešení soustav lineárních algebraických rovnic včetně jejich předpodmiňování.

Téma představuje rychle se rozvíjející obor, který získává impulsy z mnoha teoretických
i praktických matematických disciplín a kde hlavním cílem je vývoj nových efektivních metod
pro aplikace, které obsahují mnoho prvků numerické lineární algebry.

Práce by měla podat nejen určitý přehled a systemizaci technik aproximace pomocí těchto matic,
ale pokusit se i navrhnout nové postupy se zvláštním zaměřením na algebraicky nestrukturované
soustavy soustavy rovnic.

Seznam odborné literatury

Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd edition, SIAM, Philadelpha, PA,
2003.

M. Benzi. Preconditioning techniques for large linear systems: a survey. J. of Computational Physics,
182(2):418-477, 2002.

R. Li and Y. Saad, Divide and conquer low-rank preconditioners for symmetric matrices,
SIAM J. Sci. Comput., 35 (2013), pp. A2069–A2095.

R. Li and Y. Saad, Low-rank correction methods for algebraic domain decomposition preconditioners, Tech.
Report ys-2014-4, Dept. of Computer Science and Engineering,
University of Minnesota, 2014.

R. Li, Y. Xi, and Y. Saad, Schur complement based low-rank correction method for algebraic
domain decomposition preconditioners, Tech. Report Preprint ys-2014-3, Dept. Computer
Science and Engineering, University of Minnesota, 2014.

Y. Saad and B. Suchomel, ARMS: an algebraic recursive multilevel solver for general sparse
linear systems, Numer. Linear Algebra Appl., 9 (2002), pp. 359–378.


Hackbusch, W., A sparse matrix arithmetic based on H-matrices. I.Introduction to H-matrices,
Computing, 62(1999), 89--108.

Ambikasaran, S. and Darve, E., An O(N\log N) fast direct solver for partial hierarchically semi-separable matrices:
with application to ial basis function interpolation, J. Sci. Comput., 57(2013), 477-501.

Martinsson, P. G. and Rokhlin, V., A fast direct solver for boundary integral equations in two dimensions,
J. Comput. Phys., 205(2005), 1-23.

Předběžná náplň práce

Cílem práce je studium moderních výpočetních postupů založených na aproximaci maticemi nízké hodnosti
se zaměřením na řešení soustav rovnic.

Předběžná náplň práce v anglickém jazyce

The goal is to study modern computational algorithms based on low-rank approximations in the context
of solving systems of equations.