This thesis aims at building a numerical linear algebra library with appropriate software engineering abstractions. Three areas of knowledge, namely, Numerical Linear Algebra (NLA), Software Engineering and Compiler Optimisation Techniques, are involved. Numerical simulation is widely used in a large number of distinct disciplines to help scientists understand and discover the world. The solutions to frequently occurring numerical problems have been implemented in subroutines, which were then grouped together to form libraries for ease of use. The design, implementation and maintenance of a NLA library require a great deal of work so that the other two topics, namely, software engineering and compiler optimisation techniques have emerged. Generally speaking, these both try to divide the system into smaller and controllable concerns, and allow the programmer to deal with fewer concerns at one time. Band matrix operation, as a new level of abstraction, is proposed for simplifying library implementation and enhancing extensibility for future functionality upgrades. Iteration Space Partitioning (ISP) is applied, in order to make the performance of this generalised implementation for band matrices comparable to that of the specialised implementations for dense and triangular matrices. The optimisation of ISP can be either programmed using the pointcut-advice model of Aspect-Oriented Programming, or integrated as part of a compiler. This naturally leads to a comparison of these two different techniques for resolving one fundamental problem. The thesis shows that software engineering properties of a library, such as modularity and extensibility, can be improved by the use of the appropriate level of abstraction, while performance is either not sacrificed at all, or at least the loss of performance is limited. In other words, the perceived trade-off between the use of high-level abstraction and fast execution is made less significant than previously assumed.

A range of numerical linear algebra problems that arise in finite element-based structural analysis are considered. These problems were encountered when implementing the finite element method in the software package Oasys GSA. We present novel solutions to these problems in the form of a new method for error detection, algorithms with superior numerical effeciency and algorithms with scalable performance on parallel computers. The solutions and their corresponding software implementations have been integrated into GSA's program code and we present results that demonstrate the use of these implementations by engineers to solve real-world structural analysis problems.

Orientador: Samuel Rocha de Oliveira / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Educação / Made available in DSpace on 2018-08-26T16:42:27Z (GMT). No. of bitstreams: 1 Cardoso_ValdineiCezar_D.pdf: 4997650 bytes, checksum: 1a1744fbebd33d7857dac964fbba6f66 (MD5) Previous issue date: 2014 / Resumo: Neste trabalho, buscamos investigar em que medida os vídeos digitais e a metodologia de ensino podem contribuir para a conceitualização em Álgebra Linear. Para isso, ministramos dois cursos, com 68 horas de duração cada um, em dois cenários: o primeiro com uma turma presencial e a gravação de pequenas partes das aulas e o segundo utilizando a metodologia das aulas reversas. Nosso referencial teórico foram as Teorias: dos Campos Conceituais, dos Registros de Representação Semiótica e Cognitiva da Aprendizagem Multimídia. Por meio deste estudo, identificamos e analisamos teoremas em ação que emergem durante a resolução de situações-problemas. A abordagem utilizada na investigação foi a pesquisa qualitativa, seguindo a abordagem de Campbell e Stanley (1979). Entre os resultados encontrados, destacamos que a forma como os estudantes utilizam os vídeos digitais para estudar Álgebra Linear está diretamente relacionada com a metodologia de ensino adotada pelo professor. Em particular, percebemos que o uso de vídeos, associado às aulas reversas, contribui para a aproximação entre estudantes e professor durante as aulas, o que facilita a mediação docente durante o processo de conceitualização nessa disciplina / Abstract: In this work, we sought to investigate to what extent digital videos and teaching methodology can contribute to the conceptualization in Linear Algebra. For this, we ministered two courses, which were 68 (sixty-eight) hours long, in two scenarios. The first class was with attendance and recordings of small parts of the lessons, the second class using methodology of the reverse lessons. Our theoretical framework was the theories of conceptual fields and semiotic representation registers and the cognitive theory of multimedia learning. Through this study, we identified and analyzed theorems in action that emerges during the resolution of problem situations. The approach used in the research was qualitative research, following the approach of Campbell and Stanley (1979). Between the results, we highlight that the way the students use the digital videos to study Linear Algebra is directly related with the methodology of teaching adopted by the teacher, in particular, we realized the use of the videos, associated to the reversed lessons contribute to the approach between students and teacher, during the lessons, which makes the teacher mediation easier during the process of conceptualization in this subject / Doutorado / Ensino de Ciencias e Matematica / Doutor em Multiunidades em Ensino de Ciências e Matemática

[pt] O produto tensorial é o formalismo adequado para desenvolver a técnica de separação de variáveis em sua generalidade. São estudadas representações tensoriais decompostas de transformações lineares e algumas aplicações recentes em análise numérica (o algoritmo de Beylkin). Os exemplos tratam da discretização do laplaciano em malhas retangulares, suas propriedades espectrais e seu cálculo funcional, com ênfase na função sinal. / [en] Separation of variables is adequately understood and extended by making use of tensor products. We consider linear transformations admitting tensor decompositions and some recent applications in numerical analysis (Beylkin s algorithm). The examples concern the discretization of the Laplacian on rectangular meshes, its spectral properties and functional calculus, with emphasis on its sign function.

abstract: Dimensionality reduction methods are examined for large-scale discrete problems, specifically for the solution of three-dimensional geophysics problems: the inversion of gravity and magnetic data. The matrices for the associated forward problems have beneficial structure for each depth layer of the volume domain, under mild assumptions, which facilitates the use of the two dimensional fast Fourier transform for evaluating forward and transpose matrix operations, providing considerable savings in both computational costs and storage requirements. Application of this approach for the magnetic problem is new in the geophysics literature. Further, the approach is extended for padded volume domains. Stabilized inversion is obtained efficiently by applying novel randomization techniques within each update of the iteratively reweighted scheme. For a general rectangular linear system, a randomization technique combined with preconditioning is introduced and investigated. This is shown to provide well-conditioned inversion, stabilized through truncation. Applying this approach, while implementing matrix operations using the two dimensional fast Fourier transform, yields computationally effective inversion, in memory and cost. Validation is provided via synthetic data sets, and the approach is contrasted with the well-known LSRN algorithm when applied to these data sets. The results demonstrate a significant reduction in computational cost with the new algorithm. Further, this new algorithm produces results for inversion of real magnetic data consistent with those provided in literature. Typically, the iteratively reweighted least squares algorithm depends on a standard Tikhonov formulation. Here, this is solved using both a randomized singular value de- composition and the iterative LSQR Krylov algorithm. The results demonstrate that the new algorithm is competitive with these approaches and offers the advantage that no regularization parameter needs to be found at each outer iteration. Given its efficiency, investigating the new algorithm for the joint inversion of these data sets may be fruitful. Initial research on joint inversion using the two dimensional fast Fourier transform has recently been submitted and provides the basis for future work. Several alternative directions for dimensionality reduction are also discussed, including iteratively applying an approximate pseudo-inverse and obtaining an approximate Kronecker product decomposition via randomization for a general matrix. These are also topics for future consideration. / Dissertation/Thesis / Doctoral Dissertation Applied Mathematics 2020

Large dense matrices are ubiquitous in scientific computing, arising from the discretization of integral operators associated with elliptic pdes, Schur complement methods, covariances in spatial statistics, kernel-based machine learning, and numerical optimization problems. Hierarchical matrices are an efficient way for storing the dense matrices of very large dimension that appear in these and related settings. They exploit the fact that the underlying matrices, while formally dense, are data sparse. They have a structure consisting of blocks many of which can be well-approximated by low rank factorizations. A hierarchical organization of the blocks avoids superlinear growth in memory requirements to store n × n dense matrices in a scalable manner, requiring O(n) units of storage with a constant depending on a representative rank k for the low rank blocks. The asymptotically optimal storage requirement of the resulting hierarchical matrices is a critical advantage, particularly in extreme computing environments, characterized by low memory per processing core. The challenge then becomes to develop the parallel linear algebra operations that can be performed directly on this compressed representation. In this dissertation, I implement a set of hierarchical basic linear algebra subroutines (HBLAS) optimized for GPUs, including hierarchical matrix vector multiplication, orthogonalization, compression, low rank updates, and matrix multiplication. I develop a library of open source batched kernel operations previously missing on GPUs for the high performance implementation of the H2 operations, while relying wherever possible on existing open source and vendor kernels to ride future improvements in the technology. Fast marshaling routines extract the batch operation data from an efficient representation of the trees that compose the hierarchical matrices. The methods developed for GPUs extend to CPUs using the same code base with simple abstractions around the batched routine execution. To demonstrate the scalability of the hierarchical operations I implement a distributed memory multi-GPU hierarchical matrix vector product that focuses on reducing communication volume and hiding communication overhead and areas of low GPU utilization using low priority streams. Two demonstrations involving Hessians of inverse problems governed by pdes and space-fractional diffusion equations show the effectiveness of the hierarchical operations in realistic applications.

No description available.

abstract: The extent of students’ struggles in linear algebra courses is at times surprising to mathematicians and instructors. To gain insight into the challenges, the central question I investigated for this project was: What is the nature of undergraduate students’ conceptions of multiple analytic representations of systems (of equations)? My methodological choices for this study included the use of one-on-one, task-based clinical interviews which were video and audio recorded. Participants were chosen on the basis of selection criteria applied to a pool of volunteers from junior-level applied linear algebra classes. I conducted both generative and convergent analyses in terms of Clement’s (2000) continuum of research purposes. The generative analysis involved an exploration of the data (in transcript form). The convergent analysis involved the analysis of two student interviews through the lenses of Duval’s (1997, 2006, 2017) Theory of Semiotic Representation Registers and a theory I propose, the Theory of Quantitative Systems. All participants concluded that for the four representations in this study, the notation was varying while the solution was invariant. Their descriptions of what was represented by the various representations fell into distinct categories. Further, the students employed visual techniques, heuristics, metaphors, and mathematical computation to account for translations between the various representations. Theoretically, I lay out some constructs that may help with awareness of the complexity in linear algebra. While there are many rich concepts in linear algebra, challenges may stem from less-than-robust communication. Further, mathematics at the level of linear algebra requires a much broader perspective than that of the ordinary algebra of real numbers. Empirically, my results and findings provide important insights into students’ conceptions. The study revealed that students consider and/or can have their interest piqued by such things as changes in register. The lens I propose along with the empirical findings should stimulate conversations that result in linear algebra courses most beneficial to students. This is especially important since students who encounter undue difficulties may alter their intended plans of study, plans which would lead them into careers in STEM (Science, Technology, Engineering, & Mathematics) fields. / Dissertation/Thesis / Doctoral Dissertation Mathematics 2019

<p>Many kernel matrices from differential equations or data science applications possess low or approximately low off-diagonal rank for certain key matrix subblocks; such matrices are referred to as rank-structured. Operations on rank-structured matrices like factorization and linear system solution can be greatly accelerated by converting them into hierarchical matrix forms, such as the hiearchically semiseparable (HSS) matrix form. The dominant cost of this conversion process, called HSS construction, is the low-rank approximation of certain matrix blocks. Low-rank approximation is also a required step in many other contexts throughout numerical linear algebra. In this work, a proxy point low-rank approximation method is detailed for general analytic kernel matrices, in both one and several dimensions. A new accuracy analysis for this approximation is also provided, as well as numerical evidence of its accuracy. The extension of this method to kernels in several dimensions is novel, and its new accuracy analysis makes it a convenient choice to use over existing proxy point methods. Finally, a new HSS construction algorithm using this method for certain Cauchy and Toeplitz matrices is given, which is asymptotically faster than existing methods. Numerical evidence for the accuracy and efficacy of the new construction algorithm is also provided.</p>

<p>This theses is dedicated to the study of generalized diagonal dominance and its<br />various beneflts. The starting point is the well known nonsingularity result of strictly diagonally dominant matrices, from which generalizations were formed in difierent directions. In theses, after a short overview of very well known results, special attention was turned to contemporary contributions, where overview of already published original material is given, together with new obtained results. Particulary, Ger&bull;sgorin-type localization theory for matrix pencils is developed, and application of the results in wireless sensor networks optimization problems is shown.</p> / <p><span class="fontstyle0">Ova teza je posvećena izučavanju generalizovane dijagonalne dominacije i njenih brojnih prednosti. Osnovu čini poznati rezultat o regularnosti strogo dijagonalnih matrica,<br />čija su uop&scaron;tenja formirana u brojnim pravcima. U tezi, nakon kratkog pregleda dobro poznatih rezultata, posebna pažnja je posvećena savremenim doprinosima, gde je dat i pregled već objavljenih autorovih rezultata, kao i detaljan tretman novih dobijenih rezultata. Posebno je razvijena teorija lokalizacije Ger&scaron;gorinovog tipa generalizovanih karakterističnih korena i pokazana je primena rezultata u problemima optimizacije bežičnih senzor mreža.</span></p>