A graph is a mathematical structure for modelling the pairwise relations between objects. This thesis studies two types of graphs, namely, similarity-based graphs and evolving graphs. We look at ways to traverse an evolving graph. In particular, we examine the influence of temporal information on node centrality. In the process, we develop EvolvingGraphs.jl, a software package for analyzing time-dependent networks. We develop Etymo, a search system for discovering interesting research papers. Etymo utilizes both similarity-based graphs and evolving graphs to build a knowledge graph of research articles in order to help users to track the development of ideas. We construct content similarity-based graphs using the full text of research papers. And we extract key concepts from research papers and exploit the temporal information in research papers to construct a concepts evolving graph.

Cette thèse présente une vision unifiée de plusieurs méthodes de décomposition de domaine : celles avec recouvrement, dites de Schwarz, et celles basées sur des compléments de Schur, dites de sous-structuration. Il est ainsi possible de changer de méthodes de manière abstraite et de construire différents préconditionneurs pour accélérer la résolution de grands systèmes linéaires creux par des méthodes itératives. On rencontre régulièrement ce type de systèmes dans des problèmes industriels ou scientifiques après discrétisation de modèles continus. Bien que de tels préconditionneurs exposent naturellement de bonnes propriétés de parallélisme sur les architectures distribuées, ils peuvent s’avérer être peu performants numériquement pour des décompositions complexes ou des problèmes physiques multi-échelles. On peut pallier ces défauts de robustesse en calculant de façon concurrente des problèmes locaux creux ou denses aux valeurs propres généralisées. D’aucuns peuvent alors identifier des modes qui perturbent la convergence des méthodes itératives sous-jacentes a priori. En utilisant ces modes, il est alors possible de définir des opérateurs de projection qui utilisent un problème dit grossier. L’utilisation de ces outils auxiliaires règle généralement les problèmes sus-cités, mais tend à diminuer les performances algorithmiques des préconditionneurs. Dans ce manuscrit, on montre en trois points quela nouvelle construction développée est performante : 1) grâce à des essais numériques à très grande échelle sur Curie—un supercalculateur européen, puis en le comparant à des solveurs de pointe 2) multi-grilles et 3) directs. / This thesis introduces a unified framework for various domain decomposition methods:those with overlap, so-called Schwarz methods, and those based on Schur complements,so-called substructuring methods. It is then possible to switch with a high-level of abstractionbetween methods and to build different preconditioners to accelerate the iterativesolution of large sparse linear systems. Such systems are frequently encountered in industrialor scientific problems after discretization of continuous models. Even though thesepreconditioners naturally exhibit good parallelism properties on distributed architectures,they can prove inadequate numerical performance for complex decompositions or multiscalephysics. This lack of robustness may be alleviated by concurrently solving sparse ordense local generalized eigenvalue problems, thus identifying modes that hinder the convergenceof the underlying iterative methods a priori. Using these modes, it is then possibleto define projection operators based on what is usually referred to as a coarse solver. Theseauxiliary tools tend to solve the aforementioned issues, but typically decrease the parallelefficiency of the preconditioners. In this dissertation, it is shown in three points thatthe newly developed construction is efficient: 1) by performing large-scale numerical experimentson Curie—a European supercomputer, and by comparing it with state of the art2) multigrid and 3) direct solvers.

Submitted by Cássia Santos (cassia.bcufg@gmail.com) on 2017-01-26T09:20:52Z No. of bitstreams: 2 Dissertação - Jânio Alves dos Santos Júnior - 2016.pdf: 3798217 bytes, checksum: c2acd93260ead52c126f4b37d994825f (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-01-30T10:25:56Z (GMT) No. of bitstreams: 2 Dissertação - Jânio Alves dos Santos Júnior - 2016.pdf: 3798217 bytes, checksum: c2acd93260ead52c126f4b37d994825f (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-01-30T10:25:56Z (GMT). No. of bitstreams: 2 Dissertação - Jânio Alves dos Santos Júnior - 2016.pdf: 3798217 bytes, checksum: c2acd93260ead52c126f4b37d994825f (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-12-14 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work aims to study some topics of graph theory in order to solve some problems. In order to complement, we approached a light study of matrices, eigenvalues and eigenvectors. The first problem is known as Königsberg Bridge Problem, where this was considered the problem that gave rise to the study on graphs. The House Problem is a joke, which shows us several propositions about planar and bipartite graphs. Some models we can relate graphs, such as we can observe in the problem of cannibals and in the game of chess. Finally, we will work with applications in the adjacency matrix as in the Problem of the Condominium of Farms and in the Number of Possible Paths in a graph, where we will work with geometric figures, apparently resolving a counting problem using eigenvalues and graph. As a methodological support will be approached Linear Algebra. / O objetivo deste trabalho é estudar alguns tópicos da teoria de grafos com o intuito de resolver alguns problemas. Para complementar, abordamos um leve estudo de matrizes, autovalores e autovetores. O primeiro problema é conhecido como o Problema da Ponte de Königsberg, onde tal, foi considerado o problema que deu origem ao estudo sobre grafos. O Problema das Casas que é uma brincadeira, que nos mostra várias proposições sobre grafos planares e bipartidos. Alguns modelos que podemos relacionar grafos, tais como veremos no problema dos canibais e no jogo de xadrez. Por fim, trabalharemos com aplicações na matriz de adjacência como no problema do Condomínio de Chácaras e no Número de Caminhos Possíveis em um Grafo, onde trabalharemos com figuras geométricas, resolvendo aparentemente um problema de contagem, utilizando autovalores e grafos. Como suporte metodológico será abordado Álgebra Linear.

The focus of this dissertation is the advancement of theory and computation related to exact precision mathematical programming. Optimization software based on floating-point arithmetic can return suboptimal or incorrect resulting because of round-off errors or the use of numerical tolerances. Exact or correct results are necessary for some applications. Implementing software entirely in rational arithmetic can be prohibitively slow. A viable alternative is the use of hybrid methods that use fast numerical computation to obtain approximate results that are then verified or corrected with safe or exact computation. We study fast methods for sparse exact rational linear algebra, which arises as a bottleneck when solving linear programming problems exactly. Output sensitive methods for exact linear algebra are studied. Finally, a new method for computing valid linear programming bounds is introduced and proven effective as a subroutine for solving mixed-integer linear programming problems exactly. Extensive computational results are presented for each topic.

This thesis focus on memory-aware algorithms tailored for hierarchical memory architectures, found for instance within multicore processors. We first study the matrix product on multicore architectures. We model such a processor, and derive lower bounds on the communication volume. We introduce three ad hoc algorithms, and experimentally assess their performance.We then target a more complex operation: the QR factorization of tall matrices. We revisit existing algorithms to better exploit the parallelism of multicore processors. We thus study the critical paths of many algorithms, prove some of them to be asymptotically optimal, and assess their performance.In the next study, we focus on scheduling streaming applications onto a heterogeneous multicore platform, the QS 22. We introduce a model of the platform and use steady-state scheduling techniques so as to maximize the throughput. We present a mixed integer programming approach that computes an optimal solution, and propose simpler heuristics. We then focus on minimizing the amount of required memory for tree-shaped workflows, and target a classical two-level memory system. I/O represent transfers from a memory to the other. We propose a new exact algorithm, and show that there exist trees where postorder traversals are arbitrarily bad. We then study the problem of minimizing the I/O volume for a given memory, show that it is NP-hard, and provide a set of heuristics.Finally, we compare archival policies for BLUE WATERS. We introduce two archival policies and adapt the well known RAIT strategy. We provide a model of the tape storage platform, and use it to assess the performance of the three policies through simulation.

Designing efficient code in practice for a given computation is a hard task. In this thesis, we tackle this issue in two different situations. The first part of the thesis introduces some algorithmic improvements in structured linear algebra. We first show how to extend an algorithm by Cardinal for inverting Cauchy-like matrices to the other common structures. This approach, which mainly relies on products of the type "structured matrix × matrix", leads to a theoretical speed-up of a factor up to 7 that we also observe in practice. Then, we extend some works on Toeplitz-like matrices and prove that, for any of the common structures, the product of an n×n structured matrix of displacement rank α by an n×α matrix can be computed in Õ(α^(ω-1)n). This leads to direct inversion algorithms in Õ(α^(ω-1)n) , that do not rely on a reduction to the Toeplitz-like case. The second part of the thesis deals with the implementation of arithmetic expressions. This topic raises several issues like finding the minimum number of operations, and maximizing the speed or the accuracy when using some finite-precision arithmetic. Making use of the inductive nature of arithmetic expressions enables the design of algorithms that help to answer such questions. We thus present a set of algorithms for generating evaluation schemes, counting them, and optimizing them according to one or several criteria. These algorithms are part of a library that we have developed and used, among other things, in order to decrease the running time of a code generator for a mathematical library, and to study optimality issues about the evaluation of a small degree polynomial with scalar coefficients at a matrix point.

In mathematics the parameter is used as a special kind of a variable. The classification of the terms \"variable\" and \"parameter\" is often done by intuition and changes due to different situations and needs. The history of mathematics shows that these two terms represent the same abstract object in mathematics. In today´s mathematics, compared to variables, the parameter is declared as an unknown constant measure. This interpretation of parameters can be used in set theory for describing sets with an infinite number of elements. Due to this perspective the structure of vector spaces can be developed as a special structured set theory. Further, the concept of parameters can be seen as a model for developing mathematics education in linear algebra.

The thesis consists of two equal parts - of a part dealing with didactic aspects of teaching linear algebra, and of an unconventionally approached textbook Fundamentals of Linear Algebra, which is appended as a separate attachment. The didactic part deals with teaching mathematics, especially linear algebra, at the University of Economics in Prague, namely from the historical and methodological point of view. The thesis also includes a detailed evaluation of students' knowledge tests. The conclusions are largely portable to other non- technically oriented universities. The textbook is designed with respect to two levels of difficulty; it is written in the form accessible for students with lighter assumptions for the study of mathematics. The textbook is designed especially for students of universities where mathematics is not the main focus; it may also serve to interested high schools students as an introduction to a more advanced study of linear algebra.

[pt] O objetivo deste trabalho é apresentar conteúdos necessários para a construção de uma base sólida em Matemática do Ensino Fundamental e Médio, mas que são em geral mal assimilados pelos alunos. Inicialmente apresentaremos o plano cartesiano, equações de uma e duas variáveis, funções de uma variável real e gráfico de funções. Passaremos então ao estudo de curvas simples e bem conhecidas dos alunos em geral, como a circunferência, e chegaremos até as cônicas rotacionadas. A partir daí, procuramos relacionar as duas partes do trabalho, mostrando como as cônicas podem ser vistas como gráficos de função de uma variável. Pretende-se que este trabalho possa ser utilizado por professores do Ensino Fundamental e Médio em sala de aula, pois boa parte do conteúdo apresentado faz parte do currículo mínimo da Secretaria de Educação do Estado do Rio de Janeiro. Propomos atividades teóricas e computacionais, utilizando o software Geogebra para construção de curvas no plano cartesiano. / [en] The objective of this paper is to present content needed to build a solid foundation in mathematics from primary and secondary schools, but are generally poorly assimilated by the students. Initially present the Cartesian plane, equations of one and two variables, functions of a real variable and function graph. Then we pass to the study of simple curves and well known to students in general, as the circumference, and arrive until the conical rotated. From there, we try to relate the two parts of the work, showing how the taper can be seen as a variable function graphs. It is intended that this work can be used by teachers of primary and secondary education in the classroom, because much of the content presented is part of the minimum curriculum of the Department of Education of the State of Rio de Janeiro. We propose theoretical and computational activities, using the Geogebra software to build curves in the Cartesian plane.

FONTENELE, Francisca Cláudia Fernandes. A sequência fedathi no ensino da álgebra linear: o caso da noção de base de um espaço vetorial. 2013. 94f. – Dissertação (Mestrado) – Universidade Federal do Ceará, Programa de Pós-graduação em Educação Brasileira, Fortaleza (CE), 2013. / Submitted by Márcia Araújo (marcia_m_bezerra@yahoo.com.br) on 2014-02-27T12:29:38Z No. of bitstreams: 1 2013-DIS-FCFFONTENELE.pdf: 1685200 bytes, checksum: 501a01826fc849e7804e2c26150de5e8 (MD5) / Approved for entry into archive by Márcia Araújo(marcia_m_bezerra@yahoo.com.br) on 2014-02-27T14:08:13Z (GMT) No. of bitstreams: 1 2013-DIS-FCFFONTENELE.pdf: 1685200 bytes, checksum: 501a01826fc849e7804e2c26150de5e8 (MD5) / Made available in DSpace on 2014-02-27T14:08:13Z (GMT). No. of bitstreams: 1 2013-DIS-FCFFONTENELE.pdf: 1685200 bytes, checksum: 501a01826fc849e7804e2c26150de5e8 (MD5) Previous issue date: 2013 / This research examined the teaching of concept of base of a vector space according to the premises mediated by Fedathi Sequence during the discipline “Introduction to Algebra” in the course of Engineering of Teleinformatic at Federal University of Ceará. The objective was to determine whether the use of Fedathi Sequence specifically in classes about the concept of base provides resources capable of becoming Meta Lever, allowing students an education based on the reflection on the worked contents. In this sense, the investigation was conducted in the form of case study, having as subject the teacher of discipline, which allowed the observation during his classes and planning, as well as having granted an interview. The results indicated that the Fedathi Sequence favored the use of resources that could become Meta Lever for students, being decisive in mediating the teacher, once the teacher behavior to use it in the classroom motivates students to reflection. We consider theories ML and FS, in this research, are complementary, and therefore we indicate that the teacher know such tools and their potential for use in teaching of concept of base, awakening the teacher an awareness of the role of mediation suggested by Fedathi Sequence. / Esta pesquisa analisou o ensino da noção de base de um espaço vetorial mediado segundo os pressupostos da Sequência Fedathi durante a disciplina de Introdução à Álgebra do curso de Engenharia de Teleinformática da Universidade Federal do Ceará. Objetivou-se verificar se o uso da Sequência Fedathi, especificamente, nas aulas sobre o conceito de base, proporciona recursos passíveis de se tornarem Alavanca Meta, permitindo aos alunos um ensino baseado na reflexão sobre os conteúdos trabalhados. Nesse sentido, a investigação foi conduzida na forma de estudo de caso, tendo como sujeito o professor da disciplina, que permitiu a observação durante suas aulas e planejamentos, além de ter concedido uma entrevista. Os resultados encontrados apontaram que a Sequência Fedathi favoreceu o uso de recursos passíveis de se tornarem Alavancas Meta para os alunos, sendo determinante na mediação do professor, de modo que a postura docente ao utilizá-la em sala de aula motivava os alunos à reflexão. Consideramos que as teorias AM e SF, nessa pesquisa, se complementaram, e, portanto, indicamos que o professor conheça tais ferramentas e seu potencial de uso no ensino de base, despertando no professor uma consciência do papel da mediação preconizada pela Sequência Fedathi.