L'objet de cette thèse est l'étude des équations de Schrödinger et des ondes, à la fois linéaires et non linéaires, dans des domaines extérieurs. Nous nous intéressons en particulier aux inégalités dites de Strichartz, qui sont une famille d'estimations dispersives mesurant la décroissance du flot linéaire, particulièrement utiles à l'étude des problèmes non linéaires correspondants. Dans des géométries dites non-captantes, c'est à dire où tous les rayons de l'optique géométrique partent à l'infini, de nombreux résultats montrent que de telles estimations sont aussi bonnes que dans l'espace libre. D'autre part, la présence d'une trajectoire captive induit nécessairement une perte au niveau d'une autre famille d'estimations à priori, les estimations d'effet régularisant et de décroissance locale de l'énergie, respectivement pour Schrödinger et pour les ondes. En contraste de quoi, nous montrons des estimations de Strichartz sans perte dans une géométrie captante instable : l'extérieur de plusieurs obstacles strictement convexes vérifiant la condition d'Ikawa. La seconde partie de cette thèse est dédiée à l'étude du comportement en temps long des équations non-linéaires sous-jacentes. Lorsque le domaine dans lequel elles vivent n'induit pas trop de concentration de l'énergie, on s'attend à ce qu'elles diffusent, c'est à dire se comportent de manière linéaire asymptotiquement en temps. Nous montrons un tel résultat pour les ondes non linéaires critiques à l'extérieur d'une classe d'obstacles généralisant la notion d'étoilé. A l'extérieur de deux obstacles strictement convexes, nous obtenons un résultat de rigidité concernant les solutions à flot compact, premier pas vers un résultat général. Enfin, nous nous intéressons à l'équation de Schrödinger non linéaire, dans l'espace libre, mais avec un potentiel. Nous montrons que les solutions diffusent si l'on prend un potentiel répulsif, ainsi qu'une somme de deux potentiels répulsifs ayant des surfaces de niveau convexes, ce qui fournit un exemple de diffusion dans une géométrie captante analogue à l'extérieur de deux convexes stricts. / We are concerned with Schrödinger and wave equations, both linear and non linear, in exterior domains. In particular, we are interested in the so-called Strichartz estimates, which are a family of dispersive estimates measuring decay for the linear flow. They turn out to be particularly useful in order to study the corresponding non linear equations. In non-captive geometries, where all the rays of geometrical optics go to infinity, many results show that Strichartz estimates hold with no loss with respect to the flat case. Moreover, the local smoothing estimates for the Schrödinger equation, respectively the local energy decay for the wave equation, which are another family of dispersive estimates, are known to fail in any captive geometry. In contrast, we show Strichartz estimates without loss in an unstable captive geometry: the exterior of many strictly convex obstacles verifying Ikawa's condition. The second part of this thesis is dedicated to the study of the long time asymptotics of the corresponding non linear equations. We expect that they behave linearly in large times, or scatter, when the domain they live in does not induce too much concentration effect. We show such a result for the non linear critical wave equation in the exterior of a class of obstacles generalizing star-shaped bodies. In the exterior of two strictly convex obstacles, we obtain a rigidity result concerning compact flow solutions, which is a first step toward a general result. Finally, we consider the non linear Schrödinger equation in the free space but with a potential. We prove that solutions scatter for a repulsive potential, and for a sum of two repulsive potentials with strictly convex level surfaces. This provides a scattering result in a framework similar to the exterior of two strictly convex obstacles.

In this thesis, we propose a novel hyper-rectangle cover theory which provides a new approach to analyzing mathematical problems with nonnegativity constraints on variables. In this theory, two fundamental concepts, cover order and cover length, are introduced and studied in details. In the same manner as determining the rank of a matrix, we construct a specific e ́chelon form of the matrix to obtain the cover order of a given matrix efficiently and effectively. We discuss various structures of the e ́chelon form for some special cases in detail. Based on the structure and properties of the constructed e ́chelon form, the concepts of non-negatively linear independence and non-negatively linear dependence are developed. Using the properties of the cover order, we obtain the necessary and sufficient conditions for the existence and uniqueness of the solutions for linear equations system with nonnegativity constraints on variables for both homogeneous and non-homogeneous cases. In addition, we apply the cover theory to analyze some typical problems in linear algebra and optimization with nonnegativity constraints on variables, including linear programming problems and non-negative least squares (NNLS) problems. For linear programming problem, we study the three possible behaviors of the solutions for it through hyper-rectangle cover theory, and show that a series of feasible solutions for the problem with the zero-cover e ́chelon form structure. On the other hand, we develop a method to obtain the cover length of the covered variable. In the process, we discover the relationship between the cover length determination problem and the NNLS problem. This enables us to obtain an analytical optimal value for the NNLS problem. / Thesis / Doctor of Philosophy (PhD)

No description available.

The goal of the diploma thesis was to describe critical moments for solving systems of linear equations at the primary school. First, various methods of solving systems of two linear equations with two unknowns are summarized, the history of systems of linear equations is briefly outlined and the theme is described from the point of view of curricular documents. Based on the review of literature, the critical moments and types of mistake made by pupils are described. My own research used the mixed research strategy, where the main strategy was qualitative and the secondary strategy was quantitative. The research consisted of semi-structured interviews with four mathematics teachers, the preparation and realization of a questionnaire for primary school pupils and the creation, realization and analysis of a didactic test. The main results of the thesis consists of the description of the most frequent pupils' problems when solving systems of linear equations, the didactic analysis of textbooks and teachers' views of the topic and its teaching. Keywords: linear equations and their systems, pupils' problems, mistakes, semi-structured interviews, didactic test Powered by TCPDF (www.tcpdf.org)

Made available in DSpace on 2016-04-27T16:57:13Z (GMT). No. of bitstreams: 1 Emerson Pereira Rodrigues.pdf: 5383374 bytes, checksum: 97ac5f06e6504db9e26d782c33cfbb75 (MD5) Previous issue date: 2011-11-10 / Secretaria da Educação do Estado de São Paulo / The aim of this documentary qualitative research is to investigate how the content from the "Linear Equations Systems in Mathematics Teacher's Notebooks from São Paulo's public schools (from 2008 and 2009)" is covered. Our interest about this research started when the Pedagogical Mathematics Report (2010) was presented. In this report, they affirmed that high school students present more difficulty to learn Mathematics than elementary school students do. To develop this paper we have researched the official documents, to see what they recommend in teaching linear equations systems to high school and elementary school students. For comparison, we have also explored two didactical Mathematics book collections. We have found out that Mathematics Teacher's Notebooks from São Paulo's public schools (from 2008 and 2009) use an approach that is similar to didactical books; the biggest difference has been found in materials dedicated to high school. While didactic books teach subjects followed by exercises, authors from Mathematics Teacher's Notebooks from São Paulo's public schools worry more about contextualizing the subject to student's realities. The aim of this paper is to propitiate an analysis of Mathematics Teacher's Notebooks from São Paulo's public schools from the 3rd bimester from the 8th year in high school and the 2nd grade from the 2nd year in high school referring to teaching linear equations systems. The product of this analysis can be found separately from this paper, and it is available online at www.pucsp.br/pos/edmat / Esta pesquisa qualitativa do tipo documental tem como objetivo investigar como é abordado o conteúdo de Sistemas de Equações Lineares nos Cadernos do Professor de Matemática da rede pública de São Paulo de 2008 e 2009. Nosso interesse em realizar esta pesquisa partiu da constatação apresentada no Relatório Pedagógico de Matemática (2010) que o aluno do Ensino Médio apresenta uma maior dificuldade com relação à aprendizagem de Matemática que o aluno do Ensino Fundamental. Para o desenvolvimento deste trabalho investigamos o que os documentos oficiais recomendam para o ensino de sistemas de equações lineares para o Ensino Fundamental e Médio. Para efeito de comparação investigamos também duas coleções de livros didáticos de Matemática. Nosso estudo constatou que os Cadernos do Professor de Matemática de 2008 e o de 2009 do Ensino Fundamental abordam de forma semelhante aos livros didáticos. A maior diferença foi constatada nos materiais destinados ao Ensino Médio. Enquanto os livros didáticos abordam os conteúdos seguidos de exercícios, os autores dos Cadernos do Professor de Matemática se preocupam com a contextualização do conteúdo estudado com relação à realidade do aluno, constatamos também a ausência de uma discussão mais abrangente a respeito da classificação dos sistemas lineares em função de um parâmetro. Este trabalho tem como produto propiciar uma análise do Caderno do Professor de Matemática do 3º bimestre do 8º ano do Ensino Fundamental e da 2ª série do 2º ano do Ensino Médio referente ao ensino de sistemas de equações lineares. Esse produto encontra-se em separado da dissertação e está disponível para o uso de professores interessados na página do Programa (www.pucsp.br/pos/edmat)

O estudo dos métodos intervalares é importante para a resolução de sistemas de equações lineares, pois os métodos intervalares produzem resultados dentro de limites confiáveis (do intervalo solução) e provam a existência ou não existência de soluções, portanto produzem resultados confiáveis, o que os métodos pontuais podem não proporcionar. Outro aspecto a destacar é o campo de utilizando de sistemas de equações lineares em problemas das engenharias e outras ciências, o que mostra a aplicabilidade desses métodos e por conseguinte a necessidade de elaboração de ferramentas que possibilitem a implementação desses métodos intervalares. O objetivo deste trabalho não é a elaboração de novos métodos intervalares, mas sim o de realizar uma descrição e implementação de alguns dos métodos intervalares encontrados na bibliografia pesquisada. A versão intervalar dos métodos pontuais não é simples e o calculo por métodos intervalares pode ser dispendioso, uma vez que se está tratando com vetores e matrizes de intervalos. A implementação dos métodos intervalares são foi possível graças a existência de ferramentas, como o compilador Pascal-XSC, que incorpora as suas características aspectos importantes como a aritmética intervalar, a verificação automática do resultado, o produto escalar Ótimo e a aritmética de alta exatidão. Este trabalho é dividido em duas etapas. A primeira apresenta um estudo dos métodos intervalares para a resolução de sistemas de equações lineares. São caracterizadas as metodologias de desenvolvimento desses métodos. Metodologias estas, que foram divididas em três grupos de métodos: métodos intervalares baseados em operações algébricas intervalares ou métodos diretos, métodos intervalares baseados em refinamento ou métodos híbridos e métodos intervalares baseados em interacões. São definidas as características, os métodos que as compõe e a aplicabilidade desses métodos na resolução de sistemas de equações lineares. A segunda etapa é caracterizada pela elaboração dos algoritmos referentes aos métodos intervalares estudados e sua respectiva implementação, dando origem a uma biblioteca aplicativa intervalar para a resolução de sistemas de equações lineares, implementada no PC-486 e utilizando o compilador Pascal-XSC. Para este desenvolvimento foi realizado, previamente, um estudo sobre este compilador e sobre bibliotecas disponíveis que são utilizadas na implementação da biblioteca aplicativa intervalar. A biblioteca selintp é organizada em quatro módulos: o módulo dirint (referente aos métodos diretos); o modulo refint (referente aos métodos baseados em refinamento); o módulo itrint (referente aos métodos iterativos) e o modulo equalg (para sistemas de equações de ordem 1). Por fim, através daquela biblioteca foram realizadas comparações entre os resultados obtidos (resultados pontuais, intervalares, seqüenciais e vetoriais) a rim de se realizar uma analise de desempenho quantitativa (exatidão) e uma comparação entre os resultados obtidos. Esses resultados sendo comparados com os obtidos com a biblioteca biblioteca esta que esta sendo desenvolvida para o ambiente do supercomputador Cray Y-MP do CESUP/UFRGS, como parte do projeto de Aritmética Vetorial Intervalar do Grupo de Matemática Computacional da UFRGS. / The study of interval methods is important for resolution of linear equation systems, because such methods produce results into reliable bounds and prove the existence or not existence of solutions, therefore they produce reliable results that, the punctual methods can non present,save that there is an exhaustive analysis of errors. Another aspect to emphasize is the field of utilization of linear equation systems in engineering problems and other sciences, in which is showed the applicability of that methods and, consequently, the necessity of tools elaboration that make possible the implementation of that interval methods. The goal of this work is not the elaboration of new interval methods, but to accomplish a description and implementation of some interval methods found in the searched bibliography. The interval version of punctual methods is not simple, and the calculus by interval methods can be expensive, respecting is treats of vectors and matrices of intervals. The implementation of interval methods was only possible due to the existence of tools, as the Pascal-XSC compiler, which incorporates to their features, important aspects such as the interval arithmetic, the automatic verification of the result, the optimal scalar product and arithmetic of high accuracy. This work is divided in two stages. The first presents a study of the interval methods for resolution of linear equation systems, in which are characterized the methodologies of development of that methods. These methodologies were divided in three method groups: interval methods based in interval algebraic operations or direct methods, interval methods based in refinament or hybrid methods, and interval methods based in iterations, in which are determined the features, the methods that compose them, and the applicability of those methods in the resolution of linear equation systems. The second stage is characterized for the elaboration of the algorithms relating to the interval methods studied and their respective implementation, originating a interval applied library for resolution of linear equation systems, selintp, implemented in PC-486 and making use of Pascal-XSC compiler. For this development was previously accomplished a study about compiler and avaiable libraries that are used in the inplementation of the interval applied library. The library selintp is organized in four modules: the dirint module (regarding to the direct methods); the refint module (regarding to the methods based in refinament); the itrint module (regarding to the iterative methods) and equalg module(for equation systems of order 1). At last, throu gh this library, comparisons were developed among the results obtained (punctual, interval, sequential and vectorial results) in order to be accomplished an analysis of quantitative performance (accuracy) and a comparison among the results obtained with libselint a library, that is been developed for the Cray Y-MP supercomputer environment of CESUP/UFRGS, as part of the Interval Vectorial Arithmetic project of Group of Computational Mathematics of UFRGS.

Made available in DSpace on 2016-04-27T16:58:44Z (GMT). No. of bitstreams: 1 Carla dos Santos Moreno Battaglioli.pdf: 3817939 bytes, checksum: d6c4369162a067d8a378a321a77afa5d (MD5) Previous issue date: 2008-10-02 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This task has as a goal to make a qualitative analysis about the linear system aprouch presented in three didatic books of the high school program that were aproved by the Programa Nacional do Livro Didático para o Ensino Médio (PNLEM). The research is based in the theorical reference of the Registers of the Semiotics Representation by Raymond Duval (2003), because we believe in the importancy of the register s conversion in order to build the student s knowledge. Our proposal is to check in these didatic books in which registers of the semiotics representation the linear systems are presented and which register s conversion are proposed in their exercises. We chose to analyse didatic books because we believe they are the instruments used the most by the teachers to prepare and to give classes. This way, the didatic books can determine the content and strategies to be worked in class. This research lead us also to investigate which are the orientations in some oficial documents: Complementary Educacional Orientations to the Nacionals Curriculares Parameters (PCN+) (BRASIL, 2002); Curriculares Orientations to High school teachers (BRASIL, 2006) and the PNLEM recomendations (BRASIL, 2007). From these documents we will do a comparision between the method of the stagger in the graphical and algebraical registers. The results obtained show that the graphical register and the register of semiotic representation of the natural language are pesented in two of the three books anlysed, however the graphic register is presented only in explanation texts, beeing few explored in the solved exercises or in the proposed exercises. We also observedthat the algebraical register is still prevailling in the linear system aprouch and that the algorithm to the resolution of systems has still beeing treated in first view, while the analyse of the results obteined in the resolution or classification of a linear system is still explored timidly / Este trabalho tem como objetivo fazer uma análise qualitativa sobre a abordagem de Sistemas Lineares apresentada por três livros didáticos do Ensino Médio, aprovados pelo Programa Nacional do Livro Didático para o Ensino Médio (PNLEM). A nossa pesquisa fundamenta-se no referencial teórico dos Registros de Representação Semiótica de Raymond Duval (2003), pois acreditamos na importância da conversão de registros para a construção do conhecimento pelo aluno. A nossa proposta é verificar, nestes livros didáticos, em quais registros de representações semióticas os sistemas lineares são apresentados e quais as conversões de registros propostas em seus exercícios. Escolhemos analisar livros didáticos, pois acreditamos que são os instrumentos mais utilizados pelo professor para preparar e ministrar suas aulas. Assim sendo, os livros didáticos podem determinar conteúdos e estratégias a serem trabalhadas em sala de aula. Esta pesquisa nos levou também a investigar quais são as orientações de alguns documentos oficiais - Orientações Educacionais Complementares aos Parâmetros Curriculares Nacionais (PCN+), (BRASIL, 2002), Orientações Curriculares para professores do Ensino Médio (BRASIL, 2006), e as Recomendações do PNLEM (BRASIL, 2007) - para a abordagem desse tema e a fazermos uma comparação do método do escalonamento nos registros gráfico e algébrico. Os resultados obtidos mostram que o registro gráfico e o registro de representação semiótica da língua natural estão presentes em dois dos três livros analisados, porém o registro gráfico está presente apenas em textos explicativos, sendo muito pouco explorado nos exercícios resolvidos ou propostos. Observamos ainda que o registro algébrico continua prevalecendo na abordagem de sistemas lineares nestes livros didáticos e que os algoritmos para a resolução de sistemas continuam sendo tratados em primeiro plano, enquanto a análise dos resultados obtidos na resolução ou na classificação de um sistema linear ainda é explorada timidamente

O estudo dos métodos intervalares é importante para a resolução de sistemas de equações lineares, pois os métodos intervalares produzem resultados dentro de limites confiáveis (do intervalo solução) e provam a existência ou não existência de soluções, portanto produzem resultados confiáveis, o que os métodos pontuais podem não proporcionar. Outro aspecto a destacar é o campo de utilizando de sistemas de equações lineares em problemas das engenharias e outras ciências, o que mostra a aplicabilidade desses métodos e por conseguinte a necessidade de elaboração de ferramentas que possibilitem a implementação desses métodos intervalares. O objetivo deste trabalho não é a elaboração de novos métodos intervalares, mas sim o de realizar uma descrição e implementação de alguns dos métodos intervalares encontrados na bibliografia pesquisada. A versão intervalar dos métodos pontuais não é simples e o calculo por métodos intervalares pode ser dispendioso, uma vez que se está tratando com vetores e matrizes de intervalos. A implementação dos métodos intervalares são foi possível graças a existência de ferramentas, como o compilador Pascal-XSC, que incorpora as suas características aspectos importantes como a aritmética intervalar, a verificação automática do resultado, o produto escalar Ótimo e a aritmética de alta exatidão. Este trabalho é dividido em duas etapas. A primeira apresenta um estudo dos métodos intervalares para a resolução de sistemas de equações lineares. São caracterizadas as metodologias de desenvolvimento desses métodos. Metodologias estas, que foram divididas em três grupos de métodos: métodos intervalares baseados em operações algébricas intervalares ou métodos diretos, métodos intervalares baseados em refinamento ou métodos híbridos e métodos intervalares baseados em interacões. São definidas as características, os métodos que as compõe e a aplicabilidade desses métodos na resolução de sistemas de equações lineares. A segunda etapa é caracterizada pela elaboração dos algoritmos referentes aos métodos intervalares estudados e sua respectiva implementação, dando origem a uma biblioteca aplicativa intervalar para a resolução de sistemas de equações lineares, implementada no PC-486 e utilizando o compilador Pascal-XSC. Para este desenvolvimento foi realizado, previamente, um estudo sobre este compilador e sobre bibliotecas disponíveis que são utilizadas na implementação da biblioteca aplicativa intervalar. A biblioteca selintp é organizada em quatro módulos: o módulo dirint (referente aos métodos diretos); o modulo refint (referente aos métodos baseados em refinamento); o módulo itrint (referente aos métodos iterativos) e o modulo equalg (para sistemas de equações de ordem 1). Por fim, através daquela biblioteca foram realizadas comparações entre os resultados obtidos (resultados pontuais, intervalares, seqüenciais e vetoriais) a rim de se realizar uma analise de desempenho quantitativa (exatidão) e uma comparação entre os resultados obtidos. Esses resultados sendo comparados com os obtidos com a biblioteca biblioteca esta que esta sendo desenvolvida para o ambiente do supercomputador Cray Y-MP do CESUP/UFRGS, como parte do projeto de Aritmética Vetorial Intervalar do Grupo de Matemática Computacional da UFRGS. / The study of interval methods is important for resolution of linear equation systems, because such methods produce results into reliable bounds and prove the existence or not existence of solutions, therefore they produce reliable results that, the punctual methods can non present,save that there is an exhaustive analysis of errors. Another aspect to emphasize is the field of utilization of linear equation systems in engineering problems and other sciences, in which is showed the applicability of that methods and, consequently, the necessity of tools elaboration that make possible the implementation of that interval methods. The goal of this work is not the elaboration of new interval methods, but to accomplish a description and implementation of some interval methods found in the searched bibliography. The interval version of punctual methods is not simple, and the calculus by interval methods can be expensive, respecting is treats of vectors and matrices of intervals. The implementation of interval methods was only possible due to the existence of tools, as the Pascal-XSC compiler, which incorporates to their features, important aspects such as the interval arithmetic, the automatic verification of the result, the optimal scalar product and arithmetic of high accuracy. This work is divided in two stages. The first presents a study of the interval methods for resolution of linear equation systems, in which are characterized the methodologies of development of that methods. These methodologies were divided in three method groups: interval methods based in interval algebraic operations or direct methods, interval methods based in refinament or hybrid methods, and interval methods based in iterations, in which are determined the features, the methods that compose them, and the applicability of those methods in the resolution of linear equation systems. The second stage is characterized for the elaboration of the algorithms relating to the interval methods studied and their respective implementation, originating a interval applied library for resolution of linear equation systems, selintp, implemented in PC-486 and making use of Pascal-XSC compiler. For this development was previously accomplished a study about compiler and avaiable libraries that are used in the inplementation of the interval applied library. The library selintp is organized in four modules: the dirint module (regarding to the direct methods); the refint module (regarding to the methods based in refinament); the itrint module (regarding to the iterative methods) and equalg module(for equation systems of order 1). At last, throu gh this library, comparisons were developed among the results obtained (punctual, interval, sequential and vectorial results) in order to be accomplished an analysis of quantitative performance (accuracy) and a comparison among the results obtained with libselint a library, that is been developed for the Cray Y-MP supercomputer environment of CESUP/UFRGS, as part of the Interval Vectorial Arithmetic project of Group of Computational Mathematics of UFRGS.

Atualmente, o computador pessoal (PC) moderno poder ser considerado como um cluster heterogênedo de um nodo, o qual processa simultâneamente inúmeras tarefas provenientes das aplicações. O PC pode ser composto por Unidades de Processamento (PUs) assimétricas, como a Unidade Central de Processamento (CPU), composta de múltiplos núcleos, a Unidade de Processamento Gráfico (GPU), composta por inúmeros núcleos e que tem sido um dos principais co-processadores que contribuiram para a computação de alto desempenho em PCs, entre outras. Neste sentido, uma plataforma de execução heterogênea é formada em um PC para efetuar cálculos intensivos em um grande número de dados. Na perspectiva desta tese, a distribuição da carga de trabalho de uma aplicação nas PUs é um fator importante para melhorar o desempenho das aplicações e explorar tal heterogeneidade. Esta questão apresenta desafios uma vez que o custo de execução de uma tarefa de alto nível em uma PU é não-determinístico e pode ser afetado por uma série de parâmetros não conhecidos a priori, como o tamanho do domínio do problema e a precisão da solução, entre outros. Nesse escopo, esta pesquisa de doutorado apresenta um sistema sensível ao contexto e de adaptação em tempo de execução com base em um compromisso entre a redução do tempo de execução das aplicações - devido a um escalonamento dinâmico adequado de tarefas de alto nível - e o custo de computação do próprio escalonamento aplicados em uma plataforma composta de CPU e GPU. Esta abordagem combina um modelo para um primeiro escalonamento baseado em perfis de desempenho adquiridos em préprocessamento com um modelo online, o qual mantém o controle do tempo de execução real de novas tarefas e escalona dinâmicamente e de modo eficaz novas instâncias das tarefas de alto nível em uma plataforma de execução composta de CPU e de GPU. Para isso, é proposto um conjunto de heurísticas para escalonar tarefas em uma CPU e uma GPU e uma estratégia genérica e eficiente de escalonamento que considera várias unidades de processamento. A abordagem proposta é aplicada em um estudo de caso utilizando uma plataforma de execução composta por CPU e GPU para computação de métodos iterativos focados na solução de Sistemas de Equações Lineares que se utilizam de um cálculo de stencil especialmente concebido para explorar as características das GPUs modernas. A solução utiliza o número de incógnitas como o principal parâmetro para a decisão de escalonamento. Ao escalonar tarefas para a CPU e para a GPU, um ganho de 21,77% em desempenho é obtido em comparação com o escalonamento estático de todas as tarefas para a GPU (o qual é utilizado por modelos de programação atuais, como OpenCL e CUDA para Nvidia) com um erro de escalonamento de apenas 0,25% em relação à combinação exaustiva. / A modern personal computer can be now considered as a one-node heterogeneous cluster that simultaneously processes several applications’ tasks. It can be composed by asymmetric Processing Units (PUs), like the multi-core Central Processing Unit (CPU), the many-core Graphics Processing Units (GPUs) - which have become one of the main co-processors that contributed towards high performance computing - and other PUs. This way, a powerful heterogeneous execution platform is built on a desktop for data intensive calculations. In the perspective of this thesis, to improve the performance of applications and explore such heterogeneity, a workload distribution over the PUs plays a key role in such systems. This issue presents challenges since the execution cost of a task at a PU is non-deterministic and can be affected by a number of parameters not known a priori, like the problem size domain and the precision of the solution, among others. Within this scope, this doctoral research introduces a context-aware runtime and performance tuning system based on a compromise between reducing the execution time of the applications - due to appropriate dynamic scheduling of high-level tasks - and the cost of computing such scheduling applied on a platform composed of CPU and GPUs. This approach combines a model for a first scheduling based on an off-line task performance profile benchmark with a runtime model that keeps track of the tasks’ real execution time and efficiently schedules new instances of the high-level tasks dynamically over the CPU/GPU execution platform. For that, it is proposed a set of heuristics to schedule tasks over one CPU and one GPU and a generic and efficient scheduling strategy that considers several processing units. The proposed approach is applied in a case study using a CPU-GPU execution platform for computing iterative solvers for Systems of Linear Equations using a stencil code specially designed to explore the characteristics of modern GPUs. The solution uses the number of unknowns as the main parameter for assignment decision. By scheduling tasks to the CPU and to the GPU, it is achieved a performance gain of 21.77% in comparison to the static assignment of all tasks to the GPU (which is done by current programming models, such as OpenCL and CUDA for Nvidia) with a scheduling error of only 0.25% compared to exhaustive search.

O estudo dos métodos intervalares é importante para a resolução de sistemas de equações lineares, pois os métodos intervalares produzem resultados dentro de limites confiáveis (do intervalo solução) e provam a existência ou não existência de soluções, portanto produzem resultados confiáveis, o que os métodos pontuais podem não proporcionar. Outro aspecto a destacar é o campo de utilizando de sistemas de equações lineares em problemas das engenharias e outras ciências, o que mostra a aplicabilidade desses métodos e por conseguinte a necessidade de elaboração de ferramentas que possibilitem a implementação desses métodos intervalares. O objetivo deste trabalho não é a elaboração de novos métodos intervalares, mas sim o de realizar uma descrição e implementação de alguns dos métodos intervalares encontrados na bibliografia pesquisada. A versão intervalar dos métodos pontuais não é simples e o calculo por métodos intervalares pode ser dispendioso, uma vez que se está tratando com vetores e matrizes de intervalos. A implementação dos métodos intervalares são foi possível graças a existência de ferramentas, como o compilador Pascal-XSC, que incorpora as suas características aspectos importantes como a aritmética intervalar, a verificação automática do resultado, o produto escalar Ótimo e a aritmética de alta exatidão. Este trabalho é dividido em duas etapas. A primeira apresenta um estudo dos métodos intervalares para a resolução de sistemas de equações lineares. São caracterizadas as metodologias de desenvolvimento desses métodos. Metodologias estas, que foram divididas em três grupos de métodos: métodos intervalares baseados em operações algébricas intervalares ou métodos diretos, métodos intervalares baseados em refinamento ou métodos híbridos e métodos intervalares baseados em interacões. São definidas as características, os métodos que as compõe e a aplicabilidade desses métodos na resolução de sistemas de equações lineares. A segunda etapa é caracterizada pela elaboração dos algoritmos referentes aos métodos intervalares estudados e sua respectiva implementação, dando origem a uma biblioteca aplicativa intervalar para a resolução de sistemas de equações lineares, implementada no PC-486 e utilizando o compilador Pascal-XSC. Para este desenvolvimento foi realizado, previamente, um estudo sobre este compilador e sobre bibliotecas disponíveis que são utilizadas na implementação da biblioteca aplicativa intervalar. A biblioteca selintp é organizada em quatro módulos: o módulo dirint (referente aos métodos diretos); o modulo refint (referente aos métodos baseados em refinamento); o módulo itrint (referente aos métodos iterativos) e o modulo equalg (para sistemas de equações de ordem 1). Por fim, através daquela biblioteca foram realizadas comparações entre os resultados obtidos (resultados pontuais, intervalares, seqüenciais e vetoriais) a rim de se realizar uma analise de desempenho quantitativa (exatidão) e uma comparação entre os resultados obtidos. Esses resultados sendo comparados com os obtidos com a biblioteca biblioteca esta que esta sendo desenvolvida para o ambiente do supercomputador Cray Y-MP do CESUP/UFRGS, como parte do projeto de Aritmética Vetorial Intervalar do Grupo de Matemática Computacional da UFRGS. / The study of interval methods is important for resolution of linear equation systems, because such methods produce results into reliable bounds and prove the existence or not existence of solutions, therefore they produce reliable results that, the punctual methods can non present,save that there is an exhaustive analysis of errors. Another aspect to emphasize is the field of utilization of linear equation systems in engineering problems and other sciences, in which is showed the applicability of that methods and, consequently, the necessity of tools elaboration that make possible the implementation of that interval methods. The goal of this work is not the elaboration of new interval methods, but to accomplish a description and implementation of some interval methods found in the searched bibliography. The interval version of punctual methods is not simple, and the calculus by interval methods can be expensive, respecting is treats of vectors and matrices of intervals. The implementation of interval methods was only possible due to the existence of tools, as the Pascal-XSC compiler, which incorporates to their features, important aspects such as the interval arithmetic, the automatic verification of the result, the optimal scalar product and arithmetic of high accuracy. This work is divided in two stages. The first presents a study of the interval methods for resolution of linear equation systems, in which are characterized the methodologies of development of that methods. These methodologies were divided in three method groups: interval methods based in interval algebraic operations or direct methods, interval methods based in refinament or hybrid methods, and interval methods based in iterations, in which are determined the features, the methods that compose them, and the applicability of those methods in the resolution of linear equation systems. The second stage is characterized for the elaboration of the algorithms relating to the interval methods studied and their respective implementation, originating a interval applied library for resolution of linear equation systems, selintp, implemented in PC-486 and making use of Pascal-XSC compiler. For this development was previously accomplished a study about compiler and avaiable libraries that are used in the inplementation of the interval applied library. The library selintp is organized in four modules: the dirint module (regarding to the direct methods); the refint module (regarding to the methods based in refinament); the itrint module (regarding to the iterative methods) and equalg module(for equation systems of order 1). At last, throu gh this library, comparisons were developed among the results obtained (punctual, interval, sequential and vectorial results) in order to be accomplished an analysis of quantitative performance (accuracy) and a comparison among the results obtained with libselint a library, that is been developed for the Cray Y-MP supercomputer environment of CESUP/UFRGS, as part of the Interval Vectorial Arithmetic project of Group of Computational Mathematics of UFRGS.