Richard Ehrenborg conjectured that in a bipartite graph G with parts X and Y, the number of spanning trees is at most the product of the vertex degrees divided by |X|⋅|Y|. We make two main contributions. First, using techniques from spectral graph theory, we show that the conjecture holds for sufficiently dense graphs containing a cut vertex of degree 2. Second, using electrical network analysis, we show that the conjecture holds under the operation of removing an edge whose endpoints have sufficiently large degrees. Our other results are combinatorial proofs that the conjecture holds for graphs having |X| ≤ 2, for even cycles, and under the operation of connecting two graphs by a new edge. We also make two new conjectures based on empirical data, each of which is stronger than Ehrenborg's conjecture.

This dissertation has two topics. The rst one is about rotating a supporting hyperplane on the convex hull of a nite point set to arrive at one of its facets. We present three procedures for these rotations in multiple dimensions. The rst two procedures rotate a supporting hyperplane for the polytope starting at a lower dimensional face until the support set is a facet. These two procedures keep current points in the support set and accumulate new points after the rotations. The rst procedure uses only algebraic operations. The second procedure uses LP. In the third procedure we rotate a hyperplane on a facet of the polytope to a dierent adjacent facet. Similarly to the rst procedure, this procedure uses only algebraic operations. Some applications to these procedures include data envelopment analysis (DEA) and integer programming. The second topic is in the eld of containment problems for polyhedral sets. We present three procedures to nd a circumscribing simplex that contains a point set in any dimension. The rst two procedures are based on the supporting hyperplane rotation ideas from the rst topic. The third circumscribing simplex procedure uses polar cones and other geometrical properties to nd facets of a circumscribing simplex. One application of the second topic discussed in this dissertation is in hyperspectral unmixing.

In the well known SIR endemic model, the infection-free steady state is globally stable for R0 < 1 and unstable for R0 > 1. Hence, we have a forward bifurcation when R0 = 1. When R0 > 1, an asymptotically stable endemic steady state exists. The basic reproduction number R0 is the main threshold bifurcation parameter used to determine the stability of steady states of SIR endemic models. In this thesis we study extensions of the SIR endemic model for which a backward bifurcation may occur at R0 = 1. We investigate the biologically reasonable conditions for the change of stability. We also analyse the impact of di erent factors that lead to a backward bifurcation both numerically and analytically. A backward bifurcation leads to sub-critical endemic steady states and hysteresis. We also provide a general classi cation of such models, using a small amplitude expansion near the bifurcation. Additionally, we present a procedure for projecting three dimensional models onto two dimensional models by applying some linear algebraic techniques. The four extensions examined are: the SIR model with a susceptible recovered class; nonlinear transmission; exogenous infection; and with a carrier class. Numerous writers have mentioned that a nonlinear transmission function in relation to the infective class, can only lead to a system with an unstable endemic steady state. In spite of this we show that in a nonlinear transmission model, we have a function depending on the infectives and satisfying certain biological conditions, and leading to a sub-critical endemic equilibriums.

Dense linear algebra(DLA) is one of the most seven important kernels in high performance computing. The introduction of new machines from vendors provides us opportunities to optimize DLA libraries for the new machines and thus exploit their power. Unfortunately the optimization phase is not straightforward. The optimum code of a certain Basic Linear Algebra Subprogram (BLAS) kernel, which is the core of DLA algorithms, in two different machines with different semiconductor process can be different even if they share the same features in terms of instruction set architecture, memory hierarchy and clock speed. It has become a tradition to optimize BLAS for new machines. Vendors maintain highly optimized BLAS libraries targeting their CPUs. Unfortunately the existing BLAS for GPUs is not highly optimized for DLA algorithms. In my research, I have provided new algorithms for several important BLAS kernels for different generation of GPUs and introduced a pointer redirecting approach to make BLAS run faster in generic problem size. I have also presented an auto-tuning approach to parameterize the developed BLAS algorithms and select the best set of parameters for a given card. The hardware trends have also brought up the need for updates on existing legacy DLA software packages, such as the sequential LAPACK. To take advantage of the new computational environment, successors of LAPACK must incorporate algorithms of three main characteristics: high parallelism, reduced communication, and heterogeneity-awareness. On multicore architectures, Parallel Linear Algebra Software for Multicore Architectures (PLASMA) has been developed to meet the challenges in multicore. On the other extreme, Matrix Algebra on GPU and Multicore Architectures (MAGMA) library demonstrated a hybridization approach that indeed streamlined the development of high performance DLA for multicores with GPU accelerators. The performance of these two libraries depend upon right choice of parameters for a given problem size and given number of cores and/or GPUs. In this work, the issue of automatically tuning these two libraries is presented. A prune based empirical auto-tuning method has been proposed for tuning PLASMA. Part of the tuning method for PLASMA was considered to tune hybrid MAGMA library.

Dense linear algebra(DLA) is one of the most seven important kernels inhigh performance computing. The introduction of new machines from vendorsprovides us opportunities to optimize DLA libraries for the new machinesand thus exploit their power. Unfortunately the optimization phase is notstraightforward. The optimum code of a certain Basic Linear AlgebraSubprogram (BLAS) kernel, which is the core of DLA algorithms, in twodifferent machines with different semiconductor process can be differenteven if they share the same features in terms of instruction setarchitecture, memory hierarchy and clock speed. It has become a traditionto optimize BLAS for new machines. Vendors maintain highly optimized BLASlibraries targeting their CPUs. Unfortunately the existing BLAS for GPUsis not highly optimized for DLA algorithms. In my research, I haveprovided new algorithms for several important BLAS kernels for differentgeneration of GPUs and introduced a pointer redirecting approach to makeBLAS run faster in generic problem size. I have also presented anauto-tuning approach to parameterize the developed BLAS algorithms andselect the best set of parameters for a given card.The hardware trends have also brought up the need for updates on existinglegacy DLA software packages, such as the sequential LAPACK. To takeadvantage of the new computational environment, successors of LAPACK mustincorporate algorithms of three main characteristics: high parallelism,reduced communication, and heterogeneity-awareness. On multicorearchitectures, Parallel Linear Algebra Software for MulticoreArchitectures (PLASMA) has been developed to meet the challenges inmulticore. On the other extreme, Matrix Algebra on GPU and MulticoreArchitectures (MAGMA) library demonstrated a hybridization approach thatindeed streamlined the development of high performance DLA for multicoreswith GPU accelerators. The performance of these two libraries depend uponright choice of parameters for a given problem size and given number ofcores and/or GPUs. In this work, the issue of automatically tuning thesetwo libraries is presented. A prune based empirical auto-tuning method hasbeen proposed for tuning PLASMA. Part of the tuning method for PLASMA wasconsidered to tune hybrid MAGMA library.

Loop invariants have traditionally been used in proofs of correctness (e.g. program verification) and program derivation. Given that a loop invariant is all that is required to derive a provably correct program, the loop invariant can be thought of as being the essence of a loop. Being the essence of a loop, we ask the question “What other information is embedded within a loop invariant?” This dissertation provides evidence that in the domain of dense linear algebra, loop invariants can be used to determine the behavior of the loops. This dissertation demonstrates that by understanding how the loop invariant describes the behavior of the loop, a goal-oriented approach can be used to derive loops that are not only provably correct, but also have the desired performance behavior. / text

In the well known SIR endemic model, the infection-free steady state is globally stable for R0 < 1 and unstable for R0 > 1. Hence, we have a forward bifurcation when R0 = 1. When R0 > 1, an asymptotically stable endemic steady state exists. The basic reproduction number R0 is the main threshold bifurcation parameter used to determine the stability of steady states of SIR endemic models. In this thesis we study extensions of the SIR endemic model for which a backward bifurcation may occur at R0 = 1. We investigate the biologically reasonable conditions for the change of stability. We also analyse the impact of di erent factors that lead to a backward bifurcation both numerically and analytically. A backward bifurcation leads to sub-critical endemic steady states and hysteresis. We also provide a general classi cation of such models, using a small amplitude expansion near the bifurcation. Additionally, we present a procedure for projecting three dimensional models onto two dimensional models by applying some linear algebraic techniques. The four extensions examined are: the SIR model with a susceptible recovered class; nonlinear transmission; exogenous infection; and with a carrier class. Numerous writers have mentioned that a nonlinear transmission function in relation to the infective class, can only lead to a system with an unstable endemic steady state. In spite of this we show that in a nonlinear transmission model, we have a function depending on the infectives and satisfying certain biological conditions, and leading to a sub-critical endemic equilibriums.

In the well known SIR endemic model, the infection-free steady state is globally stable for R0 < 1 and unstable for R0 > 1. Hence, we have a forward bifurcation when R0 = 1. When R0 > 1, an asymptotically stable endemic steady state exists. The basic reproduction number R0 is the main threshold bifurcation parameter used to determine the stability of steady states of SIR endemic models. In this thesis we study extensions of the SIR endemic model for which a backward bifurcation may occur at R0 = 1. We investigate the biologically reasonable conditions for the change of stability. We also analyse the impact of di erent factors that lead to a backward bifurcation both numerically and analytically. A backward bifurcation leads to sub-critical endemic steady states and hysteresis. We also provide a general classi cation of such models, using a small amplitude expansion near the bifurcation. Additionally, we present a procedure for projecting three dimensional models onto two dimensional models by applying some linear algebraic techniques. The four extensions examined are: the SIR model with a susceptible recovered class; nonlinear transmission; exogenous infection; and with a carrier class. Numerous writers have mentioned that a nonlinear transmission function in relation to the infective class, can only lead to a system with an unstable endemic steady state. In spite of this we show that in a nonlinear transmission model, we have a function depending on the infectives and satisfying certain biological conditions, and leading to a sub-critical endemic equilibriums.

Orientador: Romulo Campos Lins / Banca: Iole de Freitas Druck / Banca: Marcos Vieira Teixeira / Resumo: Esta pesquisa, baseada no Modelo Teórico dos Campos Semânticos (MTCS), trata da produção de significados para a noção de transformação linear em Álgebra Linear. Foi desenvolvida a partir das análises de: textos matemáticos - alguns considerados históricos e outros contemporâneos - e entrevistas com duas alunas de um curso de Matemática. Neste trabalho, identificamos possíveis significados que podem ser produzidos para a noção de transformação linear, o que pode auxiliar na prática de professores de Álgebra Linear. Além disso, poderá subsidiar discussões mais amplas sobre a formação inicial do professor de Matemática. / Abstract: This research, based on the Theoretical Model of Semantic Fields (TMSF), deals with the production of meanings for the notion of linear transformation in Linear Algebra. It has been developed from the analysis of: mathematics texts - some taken as historical and others as contemporary - and interviews with two undergraduate mathematics students. In this work, we have identified possible meanings that can be produced for the notion of linear transformation. That can help the practice of teachers of Linear Algebra and might also promote more general discussion about the pre-service education of mathematics teachers. / Mestre

This thesis aims to acquire, deepen and promote understanding of computing techniques for high dimensional scattered data approximation with radial basis functions. The main contributions of this thesis include sufficient conditions for the sovability of compactly supported radial basis functions with different shapes, near points preconditioning techniques for high dimensional interpolation systems with compactly supported radial basis functions, a heterogeneous hierarchical radial basis function interpolation scheme, which allows compactly supported radial basis functions of different shapes at the same level, an O(N) algorithm for constructing hierarchical scattered data set andan O(N) algorithm for sparse kernel summation on Cartesian grids. Besides the main contributions, we also investigate the eigenvalue distribution of interpolation matrices related to radial basis functions, and propose a concept of smoothness matching. We look at the problem from different perspectives, giving a systematic and concise description of other relevant theoretical results and numerical techniques. These results are interesting in themselves and become more interesting when placed in the context of the bigger picture. Finally, we solve several real-world problems. Presented applications include 3D implicit surface reconstruction, terrain modelling, high dimensional meteorological data approximation on the earth and scattered spatial environmental data approximation.