Orientador: Clotilzio Moreira dos Santos / Banca: Ires Dias / Banca: Aparecida Francisco da Silva / Resumo: Seja K um corpo p-ádico, com p 6= 2 e F K uma extensão galoisiana de K de grau n: Então F pode ser visto como espa»co quadrático sobre K, com a forma quadrática dada por T(x) = trFjK(x2), para x 2 F: Determinaremos os invariantes determinante, dimensão e invariante de Hasse desta forma quadrática para n igual a 2,3 e 4. / Let K be a p-adic eld with p 6= 2 and F a Galois extension eld of K of degree n: Then F can be viewed as a quadratic space over K under the quadratic form T(x) = trFjK(x2) for x 2 F. The invariants of this quadratic form dimension, determinant and Hasse invariant are given in the case when n is equal to 2,3 and 4. / Mestre

The main theme of this work is effectiveness and efficiency of Krylov subspace methods and Krylov subspace recycling. While solving long, slowly changing sequences of large linear systems, such as the ones that arise in engineering, there are many issues we need to consider if we want to make the process reliable (converging to a correct solution) and as fast as possible. This thesis is built on three main components. At first, we target bilinear and quadratic form estimation. Bilinear form $c^TA^{-1}b$ is often associated with long sequences of linear systems, especially in optimization problems. Thus, we devise algorithms that adapt cheap bilinear and quadratic form estimates for Krylov subspace recycling. In the second part, we develop a hybrid recycling method that is inspired by a complex CFD application. We aim to make the method robust and cheap at the same time. In the third part of the thesis, we optimize the implementation of Krylov subspace methods on Graphic Processing Units (GPUs). Since preconditioners based on incomplete matrix factorization (ILU, Cholesky) are very slow on the GPUs, we develop a preconditioner that is effective but well suited for GPU implementation. / Ph. D. / In many applications we encounter the repeated solution of a large number of slowly changing large linear systems. The cost of solving these systems typically dominates the computation. This is often the case in medical imaging, or more generally inverse problems, and optimization of designs. Because of the size of the matrices, Gaussian elimination is infeasible. Instead, we find a sufficiently accurate solution using iterative methods, so-called Krylov subspace methods, that improve the solution with every iteration computing a sequence of approximations spanning a Krylov subspace. However, these methods often take many iterations to construct a good solution, and these iterations can be expensive. Hence, we consider methods to reduce the number of iterations while keeping the iterations cheap. One such approach is Krylov subspace recycling, in which we recycle judiciously selected subspaces from previous linear solves to improve the rate of convergence and get a good initial guess. In this thesis, we focus on improving efficiency (runtimes) and effectiveness (number of iterations) of Krylov subspace methods. The thesis has three parts. In the first part, we focus on efficiently estimating sequences of bilinear forms, c^TA⁻¹b. We approximate the bilinear forms using the properties of Krylov subspaces and Krylov subspace solvers. We devise an algorithm that allows us to use Krylov subspace recycling methods to efficiently estimate bilinear forms, and we test our approach on three applications: topology optimization for the optimal design of structures, diffuse optical tomography, and error estimation and grid adaptation in computational fluid dynamics. In the second part, we focus on finding the best strategy for Krylov subspace recycling for two large computational fluid dynamics problems. We also present a new approach, which lets us reduce the computational cost of Krylov subspace recycling. In the third part, we investigate Krylov subspace methods on Graphics Processing Units. We use a lid driven cavity problem from computational fluid dynamics to perform a thorough analysis of how the choice of the Krylov subspace solver and preconditioner influences runtimes. We propose a new preconditioner, which is designed to work well on Graphics Processing Units.

No description available.

One of the most popular ways to exploit the advantages of a multiple-input multiple-output (MIMO) system is using space time block coding. A space time block code (STBC) is a finite set of complex matrices whose entries consist of the information symbols to be transmitted. A linear STBC is one in which the information symbols are linearly combined to form a two-dimensional code matrix. A well known method of maximum-likelihood (ML) decoding of such STBCs is using the sphere decoder (SD). In this thesis, new constructions of STBCs with low sphere decoding complexity are presented and various ways of characterizing and reducing the sphere decoding complexity of an STBC are addressed. The construction of low sphere decoding complexity STBCs is tackled using irreducible matrix representations of Clifford algebras, cyclic division algebras and crossed-product algebras. The complexity reduction algorithms for the STBCs constructed are explored using tree based search algorithms. Considering an STBC as a vector space over the set of weight matrices, the problem of characterizing the sphere decoding complexity is addressed using quadratic form representations. The main results are as follows. A sub-class of fast decodable STBCs known as Block Orthogonal STBCs (BOSTBCs) are explored. A set of sufficient conditions to obtain BOSTBCs are explained. How the block orthogonal structure of these codes can be exploited to reduce the SD complexity of the STBC is then explained using a depth first tree search algorithm. Bounds on the SD complexity reduction and its relationship with the block orthogonal structure are then addressed. A set of constructions to obtain BOSTBCs are presented next using Clifford unitary weight designs (CUWDs), Coordinate-interleaved orthogonal designs (CIODs), cyclic division algebras and crossed product algebras which show that a lot of codes existing in literature exhibit the block orthogonal property. Next, the dependency of the ordering of information symbols on the SD complexity is discussed following which a quadratic form representation known as the Hurwitz-Radon quadratic form (HRQF) of an STBC is presented which is solely dependent on the weight matrices of the STBC and their ordering. It is then shown that the SD complexity is only a function of the weight matrices defining the code and their ordering, and not of the channel realization (even though the equivalent channel when SD is used depends on the channel realization). It is also shown that the SD complexity is completely captured into a single matrix obtained from the HRQF. Also, for a given set of weight matrices, an algorithm to obtain a best ordering of them leading to the least SD complexity is presented using the HRQF matrix.