L'objet est de comparer des algorithmes de multiplication de matrices à coefficients intervalles et leurs implémentations.Le premier axe est la mesure de la précision numérique. Les précédentes analyses d'erreur se limitent à établir une borne sur la surestimation du rayon du résultat en négligeant les erreurs dues au calcul en virgule flottante. Après examen des différentes possibilités pour quantifier l'erreur d'approximation entre deux intervalles, l'erreur d'arrondi est intégrée dans l'erreur globale. À partir de jeux de données aléatoires, la dispersion expérimentale de l'erreur globale permet d'éclairer l'importance des différentes erreurs (de méthode et d'arrondi) en fonction de plusieurs facteurs : valeur et homogénéité des précisions relatives des entrées, dimensions des matrices, précision de travail. Cette démarche conduit à un nouvel algorithme moins coûteux et tout aussi précis dans certains cas déterminés.Le deuxième axe est d'exploiter le parallélisme des opérations. Les implémentations précédentes se ramènent à des produits de matrices de nombres flottants. Pour contourner les limitations d'une telle approche sur la validité du résultat et sur la capacité à monter en charge, je propose une implémentation par blocs réalisée avec des threads OpenMP qui exécutent des noyaux de calcul utilisant les instructions vectorielles. L'analyse des temps d'exécution sur une machine de 4 octo-coeurs montre que les coûts de calcul sont du même ordre de grandeur sur des matrices intervalles et numériques de même dimension et que l'implémentation par bloc passe mieux à l'échelle que l'implémentation avec plusieurs appels aux routines BLAS. / This work aims at determining suitable scopes for several algorithms of interval matrices multiplication.First, we quantify the numerical quality. Former error analyses of interval matrix products establish bounds on the radius overestimation by neglecting the roundoff error. We discuss here several possible measures for interval approximations. We then bound the roundoff error and compare experimentally this bound with the global error distribution on several random data sets. This approach enlightens the relative importance of the roundoff and arithmetic errors depending on the value and homogeneity of relative accuracies of inputs, on the matrix dimension, and on the working precision. This also leads to a new algorithm that is cheaper yet as accurate as previous ones under well-identified conditions.Second, we exploit the parallelism of linear algebra. Previous implementations use calls to BLAS routines on numerical matrices. We show that this may lead to wrong interval results and also restrict the scalability of the performance when the core count increases. To overcome these problems, we implement a blocking version with OpenMP threads executing block kernels with vector instructions. The timings on a 4-octo-core machine show that this implementation is more scalable than the BLAS one and that the cost of numerical and interval matrix products are comparable.

Dans cette thèse, on présente la théorie algébrique IH par le biais de générateurs et d’équations.Le modèle libre de IH est la catégorie des sous-espaces linéaires sur un corps k. Les termes de IH sont des diagrammes de cordes, qui, selon le choix de k, peuvent exprimer différents types de réseaux et de formalismes graphiques, que l’on retrouve dans des domaines scientifiques divers, tels que les circuits quantiques, les circuits électriques et les réseaux de Petri. Les équations de IH sont obtenues via des lois distributives entre algèbres de Hopf – d’où le nom “Interacting Hopf algebras” (algèbres de Hopf interagissantes). La caractérisation via les sous-espaces permet de voir IH comme une syntaxe fondée sur les diagrammes de cordes pour l’algèbre linéaire: les applications linéaires, les espaces et leurs transformations ont chacun leur représentation fidèle dans le langage graphique. Cela aboutit à un point de vue alternatif, souvent fructueux, sur le domaine.On illustre cela en particulier en utilisant IH pour axiomatiser la sémantique formelle de circuits de calculs de signaux, pour lesquels on s’intéresse aux questions de la complète adéquation et de la réalisabilité. Notre analyse suggère un certain nombre d’enseignements au sujet du rôle de la causalité dans la sémantique des systèmes de calcul. / We present by generators and equations the algebraic theory IH whose free model is the category oflinear subspaces over a field k. Terms of IH are string diagrams which, for different choices of k, expressdifferent kinds of networks and graphical formalisms used by scientists in various fields, such as quantumcircuits, electrical circuits and Petri nets. The equations of IH arise by distributive laws between Hopfalgebras - from which the name interacting Hopf algebras. The characterisation in terms of subspacesallows to think of IH as a string diagrammatic syntax for linear algebra: linear maps, spaces and theirtransformations are all faithfully represented in the graphical language, resulting in an alternative, ofteninsightful perspective on the subject matter. As main application, we use IH to axiomatise a formalsemantics of signal processing circuits, for which we study full abstraction and realisability. Our analysissuggests a reflection about the role of causality in the semantics of computing devices.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-02-02T10:19:45Z No. of bitstreams: 1 wallacenascimentopintojunior.pdf: 2076856 bytes, checksum: a61767f103c90bc218e055ece7d4b54c (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-02-02T11:43:14Z (GMT) No. of bitstreams: 1 wallacenascimentopintojunior.pdf: 2076856 bytes, checksum: a61767f103c90bc218e055ece7d4b54c (MD5) / Made available in DSpace on 2016-02-02T11:43:14Z (GMT). No. of bitstreams: 1 wallacenascimentopintojunior.pdf: 2076856 bytes, checksum: a61767f103c90bc218e055ece7d4b54c (MD5) Previous issue date: 2013-08-15 / Esta pesquisa qualitativa tem como foco o desenvolvimento da disciplina Álgebra Linear no curso de Licenciatura em Química na modalidade a distância da Universidade Federal de Juiz de Fora, vinculada ao sistema UAB (Universidade Aberta do Brasil). Em consonância com uma epistemologia construtivista, uma perspectiva teórica interpretivista e uma metodologia orientada pela Grounded Theory, foi constituída a pergunta norteadora que orientou a investigação: ”Como tem se desenvolvido a disciplina Álgebra Linear no curso de Licenciatura a distância em Química na UFJF?” A produção dos dados na investigação em pauta se desenvolveu, principalmente, a partir do Projeto Pedagógico do Curso, dos registros do AVA (Ambiente Virtual de Aprendizagem), de questionários e de entrevistas com alunos – evadidos ou não – da disciplina e/ou do curso, com uma tutora presencial e com a professora da disciplina. Por meio da análise dos dados, foi construído um panorama conciso sobre a licenciatura em pauta, observando-se os contrastes entre as propostas do Projeto Pedagógico e a realidade encontrada. Especificamente sobre a Álgebra Linear, destacaram-se os índices de aprovação/reprovação, algumas das dificuldades dos alunos para lidar com os aspectos mais abstratos da disciplina e a importância dada ao tutor presencial, às aulas de exercícios, à formação de grupos de estudo e ao uso de videoaulas. Os resultados sugerem que houve um “esvaziamento”, tanto quantitativo, no que se refere à evasão do curso, quanto qualitativo no que tange à compreensão de conceitos centrais da disciplina. / This qualitative research focuses on the development of the discipline Linear Algebra in an undergraduate distance education course context in chemistry teaching offered by UFJF. The course was related to the UAB (Open University of Brazil) system. The research question was created in line with a constructivist epistemology, a theoretical perspective and an interpretative methodology guided by the Grounded Theory, and it was: "How the discipline Linear Algebra has been developed in the undergraduate distance education course in chemistry teaching offered by UFJF?". Data was produced mainly from the Pedagogical Project of the course, from the records of the VLE (Virtual Learning Environment), from questionnaires and from interviews with students, with a presential tutor and teacher’s discipline. Through data analysis, a concise overview of the course was built, observing the contrasts between the proposed Pedagogical Project and the reality found. Specifically on Linear Algebra the most important points were the indexes of pass/fail, some of the difficulties the students had to deal with the more abstract aspects of the discipline and the importance that is given to the presential tutor, the exercise classes, and the formation of study groups and the use of video classes. The results suggest that there was an "empty", both quantitative, regarding the course drop out, as qualitative with regard to the understanding of the discipline central concepts.

Linear algebra operations appear in nearly every application in advanced analytics, machine learning, and of various science domains. Until today, many data analysts and scientists tend to use statistics software packages or hand-crafted solutions for their analysis. In the era of data deluge, however, the external statistics packages and custom analysis programs that often run on single-workstations are incapable to keep up with the vast increase in data volume and size. In particular, there is an increasing demand of scientists for large scale data manipulation, orchestration, and advanced data management capabilities. These are among the key features of a mature relational database management system (DBMS). With the rise of main memory database systems, it now has become feasible to also consider applications that built up on linear algebra. This thesis presents a deep integration of linear algebra functionality into an in-memory column-oriented database system. In particular, this work shows that it has become feasible to execute linear algebra queries on large data sets directly in a DBMS-integrated engine (LAPEG), without the need of transferring data and being restricted by hard disc latencies. From various application examples that are cited in this work, we deduce a number of requirements that are relevant for a database system that includes linear algebra functionality. Beside the deep integration of matrices and numerical algorithms, these include optimization of expressions, transparent matrix handling, scalability and data-parallelism, and data manipulation capabilities. These requirements are addressed by our linear algebra engine. In particular, the core contributions of this thesis are: firstly, we show that the columnar storage layer of an in-memory DBMS yields an easy adoption of efficient sparse matrix data types and algorithms. Furthermore, we show that the execution of linear algebra expressions significantly benefits from different techniques that are inspired from database technology. In a novel way, we implemented several of these optimization strategies in LAPEG’s optimizer (SpMachO), which uses an advanced density estimation method (SpProdest) to predict the matrix density of intermediate results. Moreover, we present an adaptive matrix data type AT Matrix to obviate the need of scientists for selecting appropriate matrix representations. The tiled substructure of AT Matrix is exploited by our matrix multiplication to saturate the different sockets of a multicore main-memory platform, reaching up to a speed-up of 6x compared to alternative approaches. Finally, a major part of this thesis is devoted to the topic of data manipulation; where we propose a matrix manipulation API and present different mutable matrix types to enable fast insertions and deletes. We finally conclude that our linear algebra engine is well-suited to process dynamic, large matrix workloads in an optimized way. In particular, the DBMS-integrated LAPEG is filling the linear algebra gap, and makes columnar in-memory DBMS attractive as efficient, scalable ad-hoc analysis platform for scientists.

One of the important parameters observed during extruded fibre fabrication is its diameter. The diameter can be measured with a single scanning camera assuming that the fibre section has a circular shape. As proved in practice, another important parameter is ovality, that is the rate of fibre flattening. This paper assumes that the fibre section shape is elliptical. In such a case, at least three different views on examined fibre are needed. Mathematical part of this paper is concerned with analytical description of fibre ovality measurement using two different approaches based on the knowledge of linear algebra, projective geometry and conic sections theory. Main goal of this paper is thus to use both mathematical theory and image analysis methods for ovality and diameter determination. Precise calcluation of such quantities is, however, conditioned on precise camera system calibration, which is described in the paper as well. Additionally, the work contains a brief mention of technical realization of ovality measurement and its possible difficulties.

First, basic aspects of interval analysis, roles of intervals and their applications are addressed. Then, various classes of interval matrices are described and their relations are depicted. This material forms a prelude to the unifying theme of the rest of the work - solving interval linear systems. Several methods for enclosing the solution set of square and overdetermined interval linear systems are covered and compared. For square systems the new shaving method is introduced, for overdetermined systems the new subsquares approach is introduced. Detecting unsolvability and solvability of such systems is discussed and several polynomial conditions are compared. Two strongest condi- tions are proved to be equivalent under certain assumption. Solving of interval linear systems is used to approach other problems in the rest of the work. Computing enclosures of determinants of interval matrices is addressed. NP- hardness of both relative and absolute approximation is proved. New method based on solving square interval linear systems and Cramer's rule is designed. Various classes of matrices with polynomially computable bounds on determinant are characterized. Solving of interval linear systems is also used to compute the least squares linear and nonlinear interval regression. It is then applied to real...

<p>Ova doktorska disertacija izučava matrice zapisane u blok formi. Ona<br />sistematizuje postojeća i predstavlja nova tvrđenja o osobinama takvih matrica,<br />koja se baziraju na ideji generalizovane dijagonalne dominacije. Poznati<br />rezultati u tačkastom slučaju dobra su osnova za blok generalizacije, koje su<br />izvedene na dva različita načina, prvi zbog svoje jednostavnije primenljivosti,<br />a drugi zbog obuhvatanja šire klase matrica na koju se rezultati odnose.</p> / <p>This thesis is related to matrices written in their block form. It systematizes known and<br />represents new knowledge about properties of such matrices, which is based on the idea<br />of generalized diagonal dominance. Known results in the point case serve as a good basis<br />for block generalization, which is done in two different ways, the first one because of its<br />simple usability, and the other for capturing wider class of matrices which are treated.</p>

<p>With the completion of the Human Genome Project and many additional efforts since, there is an abundance of genetic data that can be leveraged to revolutionize healthcare. Now, there are significant efforts to develop state-of-the-art techniques that reveal insights about connections between genetics and complex diseases such as diabetes, heart disease, or common psychiatric conditions that depend on multiple genes interacting with environmental factors. These methods help pave the way towards diagnosis, cure, and ultimately prediction and prevention of complex disorders. As a part of this effort, we address high dimensional genomics-related questions through mathematical modeling, statistical methodologies, combinatorics and scalable algorithms. More specifically, we develop innovative techniques at the intersection of technology and life sciences using biobank scale data from genome-wide association studies (GWAS) and machine learning as an effort to better understand human health and disease. <br> <br> The underlying principle behind Genome Wide Association Studies (GWAS) is a test for association between genotyped variants for each individual and the trait of interest. GWAS have been extensively used to estimate the signed effects of trait-associated alleles, mapping genes to disorders and over the past decade about 10,000 strong associations between genetic variants and one (or more) complex traits have been reported. One of the key challenges in GWAS is population stratification which can lead to spurious genotype-trait associations. Our work proposes a simple clustering-based approach to correct for stratification better than existing methods. This method takes into account the linkage disequilibrium (LD) while computing the distance between the individuals in a sample. Our approach, called CluStrat, performs Agglomerative Hierarchical Clustering (AHC) using a regularized Mahalanobis distance-based GRM, which captures the population-level covariance (LD) matrix for the available genotype data.<br> <br> Linear mixed models (LMMs) have been a popular and powerful method when conducting genome-wide association studies (GWAS) in the presence of population structure. LMMs are computationally expensive relative to simpler techniques. We implement matrix sketching in LMMs (MaSk-LMM) to mitigate the more expensive computations. Matrix sketching is an approximation technique where random projections are applied to compress the original dataset into one that is significantly smaller and still preserves some of the properties of the original dataset up to some guaranteed approximation ratio. This technique naturally applies to problems in genetics where we can treat large biobanks as a matrix with the rows representing samples and columns representing SNPs. These matrices will be very large due to the large number of individuals and markers in biobanks and can benefit from matrix sketching. Our approach tackles the bottleneck of LMMs directly by using sketching on the samples of the genotype matrix as well as sketching on the markers during the computation of the relatedness or kinship matrix (GRM). <br> <br> Predictive analytics have been used to improve healthcare by reinforcing decision-making, enhancing patient outcomes, and providing relief for the healthcare system. These methods help pave the way towards diagnosis, cure, and ultimately prediction and prevention of complex disorders. The prevalence of these complex diseases varies greatly around the world. Understanding the basis of this prevalence difference can help disentangle the interaction among different factors causing complex disorders and identify groups of people who may be at a greater risk of developing certain disorders. This could become the basis of the implementation of early intervention strategies for populations at higher risk with significant benefits for public health.<br> <br> This dissertation broadens our understanding of empirical population genetics. It proposes a data-driven perspective to a variety of problems in genetics such as confounding factors in genetic structure. This dissertation highlights current computational barriers in open problems in genetics and provides robust, scalable and efficient methods to ease the analysis of genotype data.</p>

[pt] Este trabalho faz uma introdução básica aos temas Cadeias de Markov e Matriz de Leontief visando mostrar aplicações práticas de sistemas lineares e matrizes com foco na aplicação no Ensino Médio brasileiro. Para tal, revisou-se as bases teóricas necessárias para o aluno ser capaz de entender e resolver problemas com estes temas. Em complemento, apresenta-se uma proposta de introdução à álgebra linear com geometria analítica, assim como a forma de cobrança da álgebra linear em concursos militares no Brasil. Com o uso de vídeos e ferramentas online, criando caminhos mais amistosos em assunto tão teórico, demonstra-se como o Youtube pode ser uma ferramenta poderosa na visualização de problemas abstratos envolvendo a álgebra linear. / [en] This work makes a basic introduction to the themes Markov Chains and Leontief Matrix aiming to show practical applications of linear systems and matrices with a focus on its application in Brazilian High School. To achieve this goal, the theoretical bases necessary for the student to be able to understand and solve problems with these themes has been revised. In addition, we present a proposal to introduce linear algebra with analytical geometry, as well as the way of taking linear algebra in military tests in Brazil. With the use of videos and online tools and creating friendlier paths on such a theoretical theme, it is demonstrated how Youtube can be a powerful tool in visualizing abstract problems involving linear algebra.

To leverage the extreme parallelism of emerging architectures, so that scientific applications can fulfill their high fidelity and multi-physics potential while sustaining high efficiency relative to the limiting resource, numerical algorithms must be redesigned. Algorithmic redesign is capable of shifting the limiting resource, for example from memory or communication to arithmetic capacity. The benefit of algorithmic redesign expands greatly when introducing a tunable tradeoff between accuracy and resources. Scientific applications from diverse sources rely on dense matrix operations. These operations arise in: Schur complements, integral equations, covariances in spatial statistics, ridge regression, radial basis functions from unstructured meshes, and kernel matrices from machine learning, among others. This thesis demonstrates how to extend the problem sizes that may be treated and to reduce their execution time. Two “universes” of algorithmic innovations have emerged to improve computations by orders of magnitude in capacity and runtime. Each introduces a hierarchy, of rank or precision. Tile Low-Rank approximation replaces blocks of dense operator with those of low rank. Mixed precision approximation, increasingly well supported by contemporary hardware, replaces blocks of high with low precision. Herein, we design new high-performance direct solvers based on the synergism of TLR and mixed precision. Since adapting to data sparsity leads to heterogeneous workloads, we rely on task-based runtime systems to orchestrate the scheduling of fine-grained kernels onto computational resources. We first demonstrate how TLR permits to accelerate acoustic scattering and mesh deformation simulations. Our solvers outperform the state-of-art libraries by up to an order of magnitude. Then, we demonstrate the impact of enabling mixed precision in bioinformatics context. Mixed precision enhances the performance up to three-fold speedup. To facilitate the adoption of task-based runtime systems, we introduce the AL4SAN library to provide a common API for the expression and queueing of tasks across multiple dynamic runtime systems. This library handles a variety of workloads at a low overhead, while increasing user productivity. AL4SAN enables interoperability by switching runtimes at runtime, which permits to achieve a twofold speedup on a task-based generalized symmetric eigenvalue solver.