This thesis is devoted to investigation of some properties of the permanent function over the set Omega_n of n-by-n doubly stochastic matrices. It contains some basic properties as well as some partial progress on Foregger's conjecture. CONJECTURE[Foregger] For every n\in N, there exists k=k(n)>1 such that, for every matrix A\in Omega_n, per(A^k)<=per(A). In this thesis the author proves the following result. THEOREM For every c>0, n\in N, for all sufficiently large k=k(n,c), for all A\in\Omega_n which minimum nonzero entry exceeds c, per(A^k)<=per(A). This theorem implies that for every A\in\Omega_n, there exists k=k(n,A)>1 such that per(A^k)<=per(A).

The present thesis focuses on the design and analysis of randomized algorithms for accelerating several linear algebraic tasks. In particular, we develop simple, efficient, randomized algorithms for a plethora of fundamental linear algebraic tasks and we also demonstrate their usefulness and applicability to matrix computations and graph theoretic problems. The thesis can be divided into three parts. The first part concentrates on the development of randomized linear algebraic primitives, the second part demonstrates the application of such primitives to matrix computations, and the last part discusses the application of such primitives to graph problems. First, we present randomized approximation algorithms for the problems of matrix multiplication, orthogonal projection, vector orthonormalization and principal angles computation (a.k.a. canonical correlation analysis). Second, utilizing the tools developed in the first part, we present randomized and provable accurate approximation algorithms for the problems of linear regression and element-wise matrix sparsification. Moreover, we present an efficient deterministic algorithm for selecting a small subset of vectors that are in isotropic position. Finally, we exploit well-known interactions between linear algebra and spectral graph theory to develop and analyze graph algorithms. In particular, we present a near-optimal time deterministic construction of expanding Cayley graphs, an efficient deterministic algorithm for graph sparsification and a randomized distributed Laplacian solver that operates under the gossip model of computation.

The present thesis focuses on the design and analysis of randomized algorithms for accelerating several linear algebraic tasks. In particular, we develop simple, efficient, randomized algorithms for a plethora of fundamental linear algebraic tasks and we also demonstrate their usefulness and applicability to matrix computations and graph theoretic problems. The thesis can be divided into three parts. The first part concentrates on the development of randomized linear algebraic primitives, the second part demonstrates the application of such primitives to matrix computations, and the last part discusses the application of such primitives to graph problems. First, we present randomized approximation algorithms for the problems of matrix multiplication, orthogonal projection, vector orthonormalization and principal angles computation (a.k.a. canonical correlation analysis). Second, utilizing the tools developed in the first part, we present randomized and provable accurate approximation algorithms for the problems of linear regression and element-wise matrix sparsification. Moreover, we present an efficient deterministic algorithm for selecting a small subset of vectors that are in isotropic position. Finally, we exploit well-known interactions between linear algebra and spectral graph theory to develop and analyze graph algorithms. In particular, we present a near-optimal time deterministic construction of expanding Cayley graphs, an efficient deterministic algorithm for graph sparsification and a randomized distributed Laplacian solver that operates under the gossip model of computation.

In the Game of Light, as formulated in "Harmonic Evolutions" (J. Kocik, 2007), there is a definition of dynamic graphs and a thorough explanation of how to find the structure of the digraph that shows the changing of states during the game. This thesis furthers this research in two directions: first, by exploring what happens when there are more than two vertex states, by expanding the state space to any cyclic group. Secondly, the research attempted to identify families of graphs and describe their graph states using only the number of vertex states. To further both of these goals, two programs were written, one as a calculator to compute the digraph structure, and one as a visualization tool that automates the game of light, allowing users to input graphs with simple point and click commands, and to easily see how graphs evolve. Finally, about one hundred graphs were evaluated using the calculator, and the resulting structures are recorded.

Made available in DSpace on 2014-06-11T19:24:54Z (GMT). No. of bitstreams: 0 Previous issue date: 2002-08-22Bitstream added on 2014-06-13T20:32:26Z : No. of bitstreams: 1 oliveira_vca_me_rcla.pdf: 1646750 bytes, checksum: 6cae5fb8a7a44b1b990f0e6c0d8c18d4 (MD5) / 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. / 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.

High-end multicore systems with GPU-based accelerators are now ubiquitous in the hardware landscape. Besides dealing with the nontrivial heterogeneous environ- ment, end users should often take into consideration the underlying memory architec- ture to decrease the overhead of data motion, especially when running on non-uniform memory access (NUMA) platforms. We propose the OmpSs parallel programming model approach using its Nanos++ dynamic runtime system to solve the two challeng- ing problems aforementioned, through 1) an innovative NUMA node-aware scheduling policy to reduce data movement between NUMA nodes and 2) a nested parallelism feature to concurrently exploit the resources available from the GPU devices as well as the CPU host, without compromising the overall performance. Our approach fea- tures separation of concerns by abstracting the complexity of the hardware from the end users so that high productivity can be achieved. The Cholesky factorization is used as a benchmark representative of dense numerical linear algebra algorithms. Superior performance is also demonstrated on the symmetric matrix inversion based on Cholesky factorization, commonly used in co-variance computations in statistics. Performance on a NUMA system with Kepler-based GPUs exceeds that of existing implementations, while the OmpSs-enabled code remains very similar to its original sequential version.

In max-plus algebra we work with the max-plus semi-ring which is the set ℝ_max=[-∞)∪ℝ together with operations 𝑎⊕𝑏 = max(𝑎,𝑏) and 𝑎⊗𝑏= 𝑎+𝑏.  The additive and multiplicative identities are taken to be ε=-∞ and ε=0 respectively. Max-plus algebra is one of many idempotent semi-rings which have been considered in various fields of mathematics. Max-plus algebra is becoming more popular not only because its operations are associative, commutative and distributive as in conventional algebra but because it takes systems that are non-linear in conventional algebra and makes them linear. Max-plus algebra also arises as the algebra of asymptotic growth rates of functions in conventional algebra which will play a significant role in several aspects of this thesis. This thesis is a survey of max-plus algebra that will concentrate on max-plus linear algebra results. We will then consider from a max-plus perspective several results by Wentzell and Freidlin for finite state Markov chains with an asymptotic dependence. / Master of Science

Scientific Computation provides a critical role in the scientific process because it allows us ask complex queries and test predictions that would otherwise be unfeasible to perform experimentally. Because of its power, Scientific Computing has helped drive advances in many fields ranging from Engineering and Physics to Biology and Sociology to Economics and Drug Development and even to Machine Learning and Artificial Intelligence. Common among these domains is the desire for timely computational results, thus a considerable amount of human expert effort is spent towards obtaining performance for these scientific codes. However, this is no easy task because each of these domains present their own unique set of challenges to software developers, such as domain specific operations, structurally complex data and ever-growing datasets. Compounding these problems are the myriads of constantly changing, complex and unique hardware platforms that an expert must target. Unfortunately, an expert is typically forced to reproduce their effort across multiple problem domains and hardware platforms. In this thesis, we demonstrate the automatic generation of expert level high-performance scientific codes for Dense Linear Algebra (DLA), Structured Mesh (Stencil), Sparse Linear Algebra and Graph Analytic. In particular, this thesis seeks to address the issue of obtaining performance on many complex platforms for a certain class of matrix-like operations that span across many scientific, engineering and social fields. We do this by automating a method used for obtaining high performance in DLA and extending it to structured, sparse and scale-free domains. We argue that it is through the use of the underlying structure found in the data from these domains that enables this process. Thus, obtaining performance for most operations does not occur in isolation of the data being operated on, but instead depends significantly on the structure of the data.

Let $V$ be a finite-dimensional vector space over a field $\mathbb{K}$, and let \text{End}$(V)$ be the set of all $\mathbb{K}$-linear transformations from $V$ to $V$. A {\em Leonard system} on $V$ is a sequence \[(\A ;\B; \lbrace E_i\rbrace_{i=0}^d; \lbrace E^*_i\rbrace_{i=0}^d),\] where $\A$ and $\B $ are multiplicity-free elements of \text{End}$(V)$; $\lbrace E_i\rbrace_{i=0}^d$ and $\lbrace E^*_i\rbrace_{i=0}^d$ are orderings of the primitive idempotents of $\A $ and $\B$, respectively; and for $0\leq i, j\leq d$, the expressions $E_i\B E_j$ and $E^*_i\A E^*_j$ are zero when $\vert i-j\vert > 1$ and nonzero when $\vert i-j \vert = 1$. % Leonard systems arise in connection with orthogonal polynomials, representations of many nice algebras, and the study of some highly regular combinatorial objects. We shall use the construction of Leonard pairs of classical type from finite-dimensional modules of $\mathit{sl}_2$ and the construction of Leonard pairs of basic type from finite-dimensional modules of $U_q(\mathit{sl}_2)$. Suppose $\Phi:=(\A ;\B; \lbrace E_i\rbrace_{i=0}^d; \lbrace E^*_i\rbrace_{i=0}^d)$ is a Leonard system. For $0 \leq i \leq d$, let \[ U_i = (E^*_0V+E^*_1V+\cdots + E^*_iV)\cap (E_iV+E_{i+1}V+\cdots + E_dV). \] Then $U_0$, $U_1$, \ldots, $U_d$ is the {\em split decomposition of $V$ for $\Phi$}. % The split decomposition of $V$ for $\Phi$ gives rise to canonical matrix representations of $\A$ and $\B$ in terms of useful parameters for the Leonard system. %These canonical matrix representations for $\A$, $\B$ are respectively lower bidiagonal and upper bidiagonal. In this thesis, we consider when certain Leonard systems share a split decomposition. We say that Leonard systems $\Phi:=(\A ;\B; \lbrace E_i\rbrace_{i=0}^d; \lbrace E^*_i\rbrace_{i=0}^d)$ and $\hat{\Phi}:=(\hat{\A} ;\hat{\B}; \lbrace \hat{E}_i\rbrace_{i=0}^d; \lbrace \hat{E^*}_i\rbrace_{i=0}^d)$ are {\em friends} when $\A = \hat{\A}$ and $\Phi$, $\hat{\Phi}$ have the same split decomposition. % We obtain Leonard systems which share a split decomposition by constructing them from closely related module structures for either $\mathit{sl}_2$ or $U_q(\mathit{sl}_2)$ on $V$. We then describe friends by a parametric classification. In this manner we describe all pairs of friends of classical and basic types. In particular, friendship is not entirely a property of isomorphism classes.

Dans cette thèse, nous discutons d’aspects algorithmiques de trois différents problèmes, en lien avec la cryptographie. La première partie est consacrée à l’algèbre linéaire creuse. Nous y présentons un nouvel algorithme de pivot de Gauss pour matrices creuses à coefficients exacts, ainsi qu’une nouvelle heuristique de sélection de pivots, qui rend l’entière procédure particulièrement efficace dans certains cas. La deuxième partie porte sur une variante du problème des anniversaires, avec trois listes. Ce problème, que nous appelons problème 3XOR, consiste intuitivement à trouver trois chaînes de caractères uniformément aléatoires de longueur fixée, telles que leur XOR soit la chaîne nulle. Nous discutons des considérations pratiques qui émanent de ce problème et proposons un nouvel algorithme plus rapide à la fois en théorie et en pratique que les précédents. La troisième partie est en lien avec le problème learning with errors (LWE). Ce problème est connu pour être l’un des principaux problèmes difficiles sur lesquels repose la cryptographie à base de réseaux euclidiens. Nous introduisons d’abord un générateur pseudo-aléatoire, basé sur la variante dé-randomisée learning with rounding de LWE, dont le temps d’évaluation est comparable avec celui d’AES. Dans un second temps, nous présentons une variante de LWE sur l’anneau des entiers. Nous montrerons que dans ce cas le problème est facile à résoudre et nous proposons une application intéressante en re-visitant une attaque par canaux auxiliaires contre le schéma de signature BLISS. / In this thesis, we discuss algorithmic aspects of three different problems, related to cryptography. The first part is devoted to sparse linear algebra. We present a new Gaussian elimination algorithm for sparse matrices whose coefficients are exact, along with a new pivots selection heuristic, which make the whole procedure particularly efficient in some cases. The second part treats with a variant of the Birthday Problem with three lists. This problem, which we call 3XOR problem, intuitively consists in finding three uniformly random bit-strings of fixed length, such that their XOR is the zero string. We discuss practical considerations arising from this problem, and propose a new algorithm which is faster in theory as well as in practice than previous ones. The third part is related to the learning with errors (LWE) problem. This problem is known for being one of the main hard problems on which lattice-based cryptography relies. We first introduce a pseudorandom generator, based on the de-randomised learning with rounding variant of LWE, whose running time is competitive with AES. Second, we present a variant of LWE over the ring of integers. We show that in this case the problem is easier to solve, and we propose an interesting application, revisiting a side-channel attack against the BLISS signature scheme.