
Behavior of total least squares method for models with multiple observations
Slavenko, Matvei ; Hnětynková, Iveta (advisor) ; Tůma, Miroslav (referee)
Linear approximation problems arise in various applications and can be solved by a large variety of methods. One of such methods is total least squares (TLS), an approach that allows to correct errors both in the linear model and available set of observations. In this work we collect and compare the main theoretical results related to TLS with multiple righthand side. Particularly we describe the classification of TLS problems and summarise the solvability analysis that has currently been spread over various sources. The second part of the work is dedicated to an approach called core data reduction (CDR) and proofofconcept programme demonstrating the CDR numerical behaviour. 1


Iterative calculation of vibrational dynamics in electron scattering from molecule
Šarmanová, Martina ; Čížek, Martin (advisor) ; Tůma, Miroslav (referee)
The main focus of present thesis is the numerical solution of systems of linear algebraic equations arising from the physical model of a collision of an electron with a molecule. The first third of the thesis introduces the basic concepts used in the treatment of molecular vibrations. The description of the JahnTeller model of the vibronic dynamics of the in termediate molecular anion in the form of the system of stationary Schrödinger equations is also included. Then, we show how this system of integrodifferential equations can be transformed into a system of linear algebraic equations represented by a symmetric matix. In the second chapter, nine numerical methods (both direct and iterative), which have been chosen considering the character of the present problem, are discussed in detail. The explanation of the main idea of preconditioning of the problem concludes the theoretical part of the thesis. The last third of the thesis is dedicated to the numerical experiments. The main aim of the epxeriments was to compare the abovementioned methods with the emphasis on the usability within the scope of electronmolecule collision simulations. 1


Multicriteria graph partitioning
Houška, Ondřej ; Tůma, Miroslav (advisor) ; Hnětynková, Iveta (referee)
The thesis is about graph partitioning and applications of graph partitioning in paral lel algorithms for solving big sparse linear equations. The problem of graph partitioning is thorougly described and standard graph partitioning algorithms are explained. The appli cation part is focusing on the Conjugate Gradient method preconditioned by a variant of incomplete Cholesky factorization based on drop tolerance. The role of graph partitioning in the problem decomposition is described and a load balancing problem is studied. 1


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
