Approximations by low-rank matrices and their applications
| Thesis title in Czech: | Aproximace maticemi malé hodnosti a jejich aplikace |
|---|---|
| Thesis title in English: | Approximations by low-rank matrices and their applications |
| Key words: | aproximace maticemi nízké hodnosti, řídké matice, iterační metody pro řešení rozsáhlých soustav algebraických rovnic, předpodmínění |
| English key words: | low-rank matrix approximations, sparse matrices, iterative methods for solving large linear algebraic equations, preconditioning |
| Academic year of topic announcement: | 2017/2018 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Department of Numerical Mathematics (32-KNM) |
| Supervisor: | prof. Ing. Miroslav Tůma, CSc. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 22.08.2017 |
| Date of assignment: | 14.09.2017 |
| Confirmed by Study dept. on: | 21.06.2018 |
| Date and time of defence: | 05.09.2018 00:00 |
| Date of electronic submission: | 20.07.2018 |
| Date of submission of printed version: | 20.07.2018 |
| Date of proceeded defence: | 05.09.2018 |
| Opponents: | doc. Ing. Miroslav Rozložník, Dr. |
| Guidelines |
| 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. |
| References |
| 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. |
| Preliminary scope of work |
| 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. |
| Preliminary scope of work in English |
| The goal is to study modern computational algorithms based on low-rank approximations in the context
of solving systems of equations. |