
Leastsquares problems with sparsedense matrices
Riegerová, Ilona ; Tůma, Miroslav (advisor) ; Tichý, Petr (referee)
Problém nejmenších čtverc· (dále jen LS problém) je aproximační úloha řešení soustav lineárních algebraických rovnic, které jsou z nějakého d·vodu za tíženy chybami. Existence a jednoznačnost řešení a metody řešení jsou známé pro r·zné typy matic, kterými tyto soustavy reprezentujeme. Typicky jsou ma tice řídké a obrovských dimenzí, ale velmi často dostáváme z praxe i úlohy s maticemi o proměnlivé hustotě nenulových prvk·. Těmi se myslí řídké matice s jedním nebo více hustými řádky. Zde rozebíráme metody řešení tohoto LS pro blému. Obvykle jsou založeny na rozdělení úlohy na hustou a řídkou část, které řeší odděleně. Tak pro řídkou část m·že přestat platit předpoklad plné sloupcové hodnosti, který je potřebný pro většinu metod. Proto se zde speciálně zabýváme postupy, které tento problém řeší. 1


Reduced communication algoritms: theory and practice
Slevínský, Rostislav ; Tůma, Miroslav (advisor) ; Rozložník, Miroslav (referee)
Development in the parallel computing environment in the last decade comes with the need of being able to use these in solving large algebraic systems. In this thesis, we focus on the Krylov subspace methods (namely the conjugate gradient method) as one of the most powerful tools and the possibilities of their parallelization. We discuss the communication avoiding Krylov subspace methods and various problems introduced by the parallelization e.g. loss of orthogonality or delay of convergence. Application of the Krylov subspace methods comes usually with some preconditioner, therefore part of this thesis is dedicated to the preconditioning in parallel computing environments.


Approximations by lowrank matrices and their applications
Outrata, Michal ; Tůma, Miroslav (advisor) ; Rozložník, Miroslav (referee)
Consider the problem of solving a large system of linear algebraic equations, using the Krylov subspace methods. In order to find the solution efficiently, the system often needs to be preconditioned, i.e., transformed prior to the iterative scheme. A feature of the system that often enables fast solution with efficient preconditioners is the structural sparsity of the corresponding matrix. A recent development brought another and a slightly different phe nomenon called the data sparsity. In contrast to the classical (structural) sparsity, the data sparsity refers to an uneven distribution of extractable information inside the matrix. In practice, the data sparsity of a matrix ty pically means that its blocks can be successfully approximated by matrices of low rank. Naturally, this may significantly change the character of the numerical computations involving the matrix. The thesis focuses on finding ways to construct Choleskybased preconditioners for the conjugate gradi ent method to solve systems with symmetric and positive definite matrices, exploiting a combination of the data and structural sparsity. Methods to exploit the data sparsity are evolving very fast, influencing not only iterative solvers but direct solvers as well. Hierarchical schemes based on the data sparsity concepts can be derived...


Lowrank matrix approximations
Jarolímová, Alena ; Tůma, Miroslav (advisor) ; Vlasák, Miloslav (referee)
This thesis is focused on using low rank matrices in numerical mathematics. We introduce conjugate gradient method and its preconditioning which we use in other chapters. Then we describe four different approaches to approximation using low rank matrices. First we discuss classical approximation using singu lar value decomposition. Next, using a model problem, we describe hierarchical matrices, which are connected with applications in physics and technique. Then pseudoskeleton decomposition is introduced. We formulate and prove a theorem about error estimate of this decomposition. We also mention algorithm Maxvol which can compute pseudoskeletal decomposition of tall matrices. Next chapter is dedicated to probabilistic algorithms and to leastsquares solver Blendenpik. In conclusions we show results of experiments focused on preconditioning using algorithm Maxvol. 1

 

Incomplete Cholesky factorization
Hoang, Phuong Thao ; Tůma, Miroslav (advisor) ; Tichý, Petr (referee)
The thesis is about the incomplete Cholesky factorization and its va riants, which are important for preconditioning a system with symmetric and positive definite matrix. Our main focus is on solving these systems, which arise in many technical applications and natural sciences, using preconditioned Con jugate Gradients. Besides many other ways we can apply Cholesky factorization approximately, incompletely. In this thesis we study existence of the incomplete Cholesky factorization and we evaluate behaviour and potential of different vari ants of the generic algorithm. 1


Multilevel incomplete factorizations
Mudroňová, Veronika ; Tůma, Miroslav (advisor) ; Strakoš, Zdeněk (referee)
In this work we present incomplete matrix decomposition algorithms including their multilevel extensions. First, we have mentioned classical standard strategies that are used for the solution of linear systems. Second, we present incomplete methods based on the hierarchical approach known as multilevel matrix decom positions. Just this latter type of approaches is considered for numerical expe riments. Namely, two major hierarchical algorithms, the greedy search with the strongest coupling and the greedy search with the smallest degree, are compared, using the Fortran programming language. The results presented in the Matlab figures are commented and discussed. 1


Professor Ivo Marek (19332017)
Blaheta, Radim ; Tůma, Miroslav
Ivo Marek, Professor at Charles University and the Czech Tec\nhnical University in Prague, was for many decades one of the bestknown Czech ma\nthematicians, who contributed significantly to the development of computa\ntional methods and numerical analysis. At the same time, he was a teacher and a le\nading personality that integrated and influenced the Czech mathematical commu\nnity.

 

The block triangular form and its use for sparse LUfactorization
Gálfy, Ivan ; Duintjer Tebbens, Erik Jurjen (advisor) ; Tůma, Miroslav (referee)
In this thesis we will present an effective method for solving systems of linear equations with large sparse matrices using LU factorization. The goal is to avoid filling the matrix by nonzero entries during the computations. Firstly we dis cuss the use of permutations for the matrix algorithms. Afterwards we present the maximum matching algorithm and Tarjan's algorithm, both based on graph theory. Tarjan's algorithm is used to achieve block triangular form and the max imum matching gives us the permutation into a matrix with zero free diagonal, which is recommended as a precursor to Tarjan's algorithm. 1
