An independent set in a graph G is a set of pairwise nonadjacent vertices, and the maximum size, alpha(G), of an independent set in G is called the independence number. Given a graph G and weight matrix A of G with entries from some field F, the maximum dimension of an A-isotropic subspace, known as the Witt index of A, is an upper bound on alpha(G). Since any weight matrix can be used, it is natural to seek the minimum upper bound on the independence number of G that can be achieved by a weight matrix. This minimum, iota_F^*(G), is called the minimum Witt index of G over F, and the resulting bound, alpha(G)<= iota_F^*(G), is called the isotropic bound. When F is finite, the possible values of iota_F^*(G) are determined and the graphs that attain the isotropic bound are characterized. The characterization is given in terms of graph classes CC(n,t,c) and CK(n,t,k) constructed from certain spanning subgraphs called C(n,t,c)-graphs and K(n,t,k)-graphs. Here t is the term rank of the adjacency matrix of G. When F=R, the isotropic bound is known as the Cvetkovi\'c bound. It is shown that it is sufficient to consider a finite number of weight matrices A when determining iota_R^*(G) and that, in many cases, two weight values suffice. For example, if the vertex set of G can be covered by alpha(G) cliques, then G attains the Cvetkovi\'c bound with a weight matrix with two weight values. Inequalities on alpha and iota_F^* resulting from graph operations such as sums, products, vertex deletion, and vertex identification are examined and, in some cases, conditions that imply equality are proved. The equalities imply that the problem of determining whether or not alpha(G)=iota_F^*(G) can be reduced to that of determining iota_F^*(H) for certain crucial graphs H found from G. / Thesis (Ph.D, Mathematics & Statistics) -- Queen's University, 2007-09-04 15:38:47.57

Achieving high computation efficiency, in terms of Cycles per Instruction (CPI), for high-performance computing kernels is an interesting and challenging research area. Dense Linear Algebra (DLA) computation is a representative high-performance computing ap- plication, which is used, for example, in LU and QR factorizations. Unfortunately, mod- ern off-the-shelf microprocessors fall significantly short of achieving theoretical lower bound in CPI for high performance computing applications. In this thesis, we perform an in-depth analysis of the available parallelisms and propose suitable algorithmic and architectural variation to significantly improve the computation efficiency. There are two standard approaches for improving the computation effficiency, first, to perform application-specific architecture customization and second, to do algorithmic tuning. In the same manner, we first perform a graph-based analysis of selected DLA kernels. From the various forms of parallelism, thus identified, we design a custom processing element for improving the CPI. The processing elements are used as building blocks for a commercially available Coarse-Grained Reconfigurable Architecture (CGRA). By per- forming detailed experiments on a synthesized CGRA implementation, we demonstrate that our proposed algorithmic and architectural variations are able to achieve lower CPI compared to off-the-shelf microprocessors. We also benchmark against state-of-the-art custom implementations to report higher energy-performance-area product. DLA computations are encountered in many engineering and scientific computing ap- plications ranging from Computational Fluid Dynamics (CFD) to Eigenvalue problem. Traditionally, these applications are written in highly tuned High Performance Comput- ing (HPC) software packages like Linear Algebra Package (LAPACK), and/or Scalable Linear Algebra Package (ScaLAPACK). The basic building block for these packages is Ba- sic Linear Algebra Subprograms (BLAS). Algorithms pertaining LAPACK/ScaLAPACK are written in-terms of BLAS to achieve high throughput. Despite extensive intellectual efforts in development and tuning of these packages, there still exists a scope for fur- ther tuning in this packages. In this thesis, we revisit most prominent and widely used compute bound algorithms like GMM for further exploitation of Instruction Level Parallelism (ILP). We further look into LU and QR factorizations for generalizations and exhibit higher ILP in these algorithms. We first accelerate sequential performance of the algorithms in BLAS and LAPACK and then focus on the parallel realization of these algorithms. Major contributions in the algorithmic tuning in this thesis are as follows: Algorithms: We present graph based analysis of General Matrix Multiplication (GMM) and discuss different types of parallelisms available in GMM We present analysis of Givens Rotation based QR factorization where we improve GR and derive Column-wise GR (CGR) that can annihilate multiple elements of a column of a matrix simultaneously. We show that the multiplications in CGR are lower than GR We generalize CGR further and derive Generalized GR (GGR) that can annihilate multiple elements of the columns of a matrix simultaneously. We show that the parallelism exhibited by GGR is much higher than GR and Householder Transform (HT) We extend generalizations to Square root Free GR (also knows as Fast Givens Rotation) and Square root and Division Free GR (SDFG) and derive Column-wise Fast Givens, and Column-wise SDFG . We also extend generalization for complex matrices and derive Complex Column-wise Givens Rotation Coarse-grained Recon gurable Architectures (CGRAs) have gained popularity in the last decade due to their power and area efficiency. Furthermore, CGRAs like REDEFINE also exhibit support for domain customizations. REDEFINE is an array of Tiles where each Tile consists of a Compute Element and a Router. The Routers are responsible for on-chip communication, while Compute Elements in the REDEFINE can be domain customized to accelerate the applications pertaining to the domain of interest. In this thesis, we consider REDEFINE base architecture as a starting point and we design Processing Element (PE) that can execute algorithms in BLAS and LAPACK efficiently. We perform several architectural enhancements in the PE to approach lower bound of the CPI. For parallel realization of BLAS and LAPACK, we attach this PE to the Router of REDEFINE. We achieve better area and power performance compared to the yesteryear customized architecture for DLA. Major contributions in architecture in this thesis are as follows: Architecture: We present design of a PE for acceleration of GMM which is a Level-3 BLAS operation We methodically enhance the PE with different features for improvement in the performance of GMM For efficient realization of Linear Algebra Package (LAPACK), we use PE that can efficiently execute GMM and show better performance For further acceleration of LU and QR factorizations in LAPACK, we identify macro operations encountered in LU and QR factorizations, and realize them on a reconfigurable data-path resulting in 25-30% lower run-time

Submitted by JULIANA MALLIA ZACHI null (juzachi@yahoo.com.br) on 2016-09-28T00:44:55Z No. of bitstreams: 1 dissertacao.pdf: 6894521 bytes, checksum: f75c53a8798712cd2028eda75d209e76 (MD5) / Approved for entry into archive by Ana Paula Grisoto (grisotoana@reitoria.unesp.br) on 2016-09-28T14:35:50Z (GMT) No. of bitstreams: 1 zachi_jm_me_rcla.pdf: 6894521 bytes, checksum: f75c53a8798712cd2028eda75d209e76 (MD5) / Made available in DSpace on 2016-09-28T14:35:50Z (GMT). No. of bitstreams: 1 zachi_jm_me_rcla.pdf: 6894521 bytes, checksum: f75c53a8798712cd2028eda75d209e76 (MD5) Previous issue date: 2016-09-02 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho são apresentados os fundamentos da Programação Linear, em especial, da Programação Linear Geométrica, instrumento importante de otimização para problemas de Economia, gestão de empresas, problemas de transportes, obtenção de misturas ótimas, entre outros. Além disso, é apresentada uma proposta didática para os professores de educação básica da escola pública, utilizando o software GeoGebra como instrumento motivador para o estudo de uma situação de aprendizagem proposta no material de apoio idealizado pela Secretaria da Educação do Estado de São Paulo, abordada no caderno do aluno do 3º ano do Ensino Médio. / In this work presents the fundamentals of linear programming in particular, of geometric linear programming, important instrument of optimization for economic problems, business management, transport problems, obtaining optimal mixtures, among others. In addition, presents a didactic proposal for teachers of the basic education of public school, using the GeoGebra software as a motivating tool for the study of a learning situation proposed in the support material designed by the Education secretary of the State of São Paulo is presented, adressed in the student notebook of 3rd year of high school.

Submitted by Gabriela Baptistella Peres null (gaby_peres_1@hotmail.com) on 2017-09-13T19:06:00Z No. of bitstreams: 1 dissertacaofinalgabriela3.pdf: 961677 bytes, checksum: 45abc96f84fbb05b46f93f40b62e0b0d (MD5) / Approved for entry into archive by Luiz Galeffi (luizgaleffi@gmail.com) on 2017-09-15T13:36:46Z (GMT) No. of bitstreams: 1 levorato_gbp_me_rcla.pdf: 961677 bytes, checksum: 45abc96f84fbb05b46f93f40b62e0b0d (MD5) / Made available in DSpace on 2017-09-15T13:36:46Z (GMT). No. of bitstreams: 1 levorato_gbp_me_rcla.pdf: 961677 bytes, checksum: 45abc96f84fbb05b46f93f40b62e0b0d (MD5) Previous issue date: 2017-08-18 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / O presente trabalho mostra a importância da Álgebra Linear e em particular da Teoria de Matrizes, Determinantes e Sistemas Lineares para resolver problemas práticos e contextualizados. Mostramos aplicações em circuitos elétricos, no balanceamento de equações químicas, nos modelos aberto e fechado de Leontief, e no funcionamento do GPS. Ainda, foi aplicado um plano de aula para os alunos do segundo ano do Ensino Médio e apresentamos sugestões de exercícios de vestibulares sobre os tópicos estudados, para serem abordados em sala de aula. / The present work shows the importance of Linear Algebra and in particular of Matrix Theory, Determinants and Linear Systems to solve practical and contextualized problems. We show applications in electrical circuits, in the balancing of chemical equations, in the open and closed models of Leontief, and in the operation of GPS. Also, a lesson plan was applied to the students of the second year of high school and we presented suggestions of exercises of vestibular about the topics studied, to be approached in the classroom.

Orientador: Carlile Campos Lavor / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-08T22:21:40Z (GMT). No. of bitstreams: 1 Lima_LeandroBezerrade_M.pdf: 2935219 bytes, checksum: 44ab53f3f917eeeb707d820048631f0d (MD5) Previous issue date: 2007 / Resumo: Neste trabalho, usando conceitos de álgebra linear e de operações quânticas, obtemos algumas propriedades de ruído quântico (para o caso particular de um q-bit), a fim de apresentar uma interpretação geométrica dos diferentes ruídos em canais quânticos, cujo processo é fundamental para a compreensão do processamento da informação quântica / Abstract: In this work, using concepts of linear algebra and quantum operations, we obtain some properties of quantum noise (for the one qubit case), in order to present a geometrical interpretation of different noises in quantum channels, which process is fundamental to the comprehension of the quantum information processing / Mestrado / Computação Quantica / Mestre em Matemática

Submitted by Erika Demachki (erikademachki@gmail.com) on 2014-10-30T18:45:23Z No. of bitstreams: 2 Dissertação - Carlos Eduardo Vitória da Silva - 2013.pdf: 1162244 bytes, checksum: d2966939f025f381680dcb9ce82d76ac (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2014-10-31T09:36:29Z (GMT) No. of bitstreams: 2 Dissertação - Carlos Eduardo Vitória da Silva - 2013.pdf: 1162244 bytes, checksum: d2966939f025f381680dcb9ce82d76ac (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-10-31T09:36:29Z (GMT). No. of bitstreams: 2 Dissertação - Carlos Eduardo Vitória da Silva - 2013.pdf: 1162244 bytes, checksum: d2966939f025f381680dcb9ce82d76ac (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2013-04-11 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The theory of linear algebra and matrices and systems particularly are linear math topics that can be applied not only within mathematics itself, but also in various other areas of human knowledge, such as physics, chemistry, biology, all engineering, psychology, economy, transportation, administration, statistics and probability, etc... The Markov chains are used to solve certain problems in the theory of probability. Applications of Markov chains in these problems, depend directly on the theory of matrices and linear systems. In this work we use the techniques of Markov Chains to solve three problems of probability, in three distinct areas. One in genetics, other in psychology and the other in the area of mass transit in a transit system. All work is developed with the intention that a high school student can read and understand the solutions of three problems presented. / A teoria da álgebra linear e particularmente matrizes e sistemas lineares são tópicos de matemática que podem ser aplicados não só dentro da própria matemática, mas também em várias outras áreas do conhecimento humano, como física, química, biologia, todas as engenharias, psicologia, economia, transporte, administração, estat ística e probabilidade, etc. As Cadeias de Markov são usadas para resolver certos problemas dentro da teoria das probabilidades. As aplicações das Cadeias de Markov nesses problemas, dependem diretamente da teoria das matrizes e sistemas lineares. Neste trabalho usamos as técnicas das Cadeias de Markov para resolver três problemas de probabilidades, em três áreas distintas. Um na área da genética, outro na área da psicologia e o outro na área de transporte de massa em um sistema de trânsito. Todo o trabalho é desenvolvido com a intenção de que um estudante do ensino médio possa ler e entender as soluções dos três problemas apresentados.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-02-18T13:23:35Z No. of bitstreams: 1 martaaparecidaferreiradeoliveirabritto.pdf: 973294 bytes, checksum: 3bb46c887b254be0f099b06ad0b53d7c (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-02-26T13:30:03Z (GMT) No. of bitstreams: 1 martaaparecidaferreiradeoliveirabritto.pdf: 973294 bytes, checksum: 3bb46c887b254be0f099b06ad0b53d7c (MD5) / Made available in DSpace on 2016-02-26T13:30:03Z (GMT). No. of bitstreams: 1 martaaparecidaferreiradeoliveirabritto.pdf: 973294 bytes, checksum: 3bb46c887b254be0f099b06ad0b53d7c (MD5) Previous issue date: 2014-03-18 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Neste trabalho, abordamos algumas aplicações de matrizes que julgamos ser possível inserir na educação básica, com o intuito de fornecer ao aluno uma visão da utilidade da matemática no mundo real, contribuindo para tornar o seu ensino mais dinâmico e atraente. As aplicações que apontamos são criptografia, cadeias de Markov, grafos, transformações no plano e sistemas lineares. Percebemos que o tratamento dado a este tópico aparece, em geral, de maneira muito tímida nos livros didáticos de ensino médio e que raramente aparecem atividades que as envolvam. No entanto, o tema é muito abrangente e rico, podendo ser relacionado a inúmeras áreas do conhecimento humano, como administração, economia, biologia, computação e física, podendo ser uma ferramenta útil para as atividades interdisciplinares. Notamos ser possível explorar o conceito de matriz, sua representação, suas operações, propriedades e definições através de problemas contextualizados. No decorrer deste trabalho, coletamos sugestões de atividades presentes em artigos, dissertações e livros de Álgebra Linear. / In this paper, we intent to make an approach of some matrix application that we judge possible to introduce in basic level education, in order to give students a broader vision of the real world mathematical utility, contributing to make a more dynamic and attractive mathematics teaching. The applications are cryptography, Markov chains, graphs, plane transforms and linear systems. We realized that the treatment given in basic textbooks to this topic is, frequently, sketchy and superficial, scarcely happening to make activities encompassing these topics. However, this is a very rich and broadening topic, that can be related to many areas of human knowledge such as Administration, Economy, Biology, Computer Science and Physics, working as an useful tool to educational interdisciplinarity . Then, it is possible to explore the matrix concept, its representations, its operations, properties and definitions to contextualized problems. Along this paper, we collect several activity suggestions found in articles, essays and Linear Algebra textbooks.

Álgebra Linear e particularmente a teoria das matrizes e dos sistemas lineares são tópicos da Matemática que têm aplicações, não só dentro da própria Matemática, mas também em várias outras áreas do conhecimento humano. Neste trabalho, além de estudar estas teorias, estudamos algumas de suas aplicações na área da Economia, como em modelos lineares de produção, modelos de Markov para emprego e modelos de benefícios obtidos no pagamento de impostos após realizarmos contribuições filantrópicas. / Linear Algebra and particularly matrices and linear systems theory are topics in Mathematics with many applications in several branches of science. In this work we study this theory and some of its applications in Economy as in linear models of production, Markov models of employment and tax benefits of charitable contributions.

Le travail de cette thèse porte sur les raisons structurales derrière la formation de cristaux maclés. Ce travail ouvre une voie pour un futur développement de protocoles de synthèse afin de réduire l'occurrence de macles. La motivation de cette étude est que la présence de macles affecte négativement les propriétés physico-chimiques des matériaux d'intérêts technologiques et réduit aussi la qualité des données expérimentales sur lesquelles se fonde l'analyse structurelle. Ce dernier problème est particulièrement sensible dans le cas de cristaux ayant des paramètres de maille importantes, comme les macromolécules biologiques. Les principes de symétrie responsables du phénomène de maclage dans le cas d’une macle de transformation ou d'origine mécanique sont bien connues. En revanche dans le cas d’une macle de croissance, le maclage est toujours considéré comme un accident lié aux conditions aléatoires de croissance cristalline où à la cinétique, plutôt qu'à la thermodynamique. Une approche générale connue comme la « théorie réticulaire des macles » a été développée depuis le XIXe siècle, fondée sur l'existence d'un sous-réseau commun aux cristaux maclés, qui donne les conditions  nécessaires pour l'apparition d'une macle. Cette approche est cependant insuffisante pour déterminer la différence entre les macles avec le même degré de chevauchement des réseaux mais montrant une fréquence d'occurrence assez différente. Une approche structurale, fondée sur l'analyse de la symétrie propre des orbites cristallographiques a été proposée il y a plus d'un demi-siècle (Donnay et Curien, 1960), mais est restée à l'état embryonnaire, malgré une certaine reprise récente (Nespolo et Ferraris, 2009). En outre, l'idée qu'une interface commune aux cristaux maclés puisse contenir une opération reliant ces individus a été proposée (Holser, 1958) mais n'a jamais été portée à un plein développement. Dans cette thèse, nous présentons un développement algébrique de ces idées. Nous montrons que les conditions structurales nécessaires pour la formation d'une macle de croissance peuvent être formulées en se basant, notamment, sur la symétrie propre des orbites cristallographiques et sur le groupe sous-périodique de la couche transversale donnant la symétrie d'une couche commune. L'analyse détaillée dans cette thèse de trois macles fréquentes démontre une corrélation claire entre le degré de restauration de la structure par l'opération de maclage et la fréquence d'occurrence des macles. Un exemple négatif, à savoir une macle hypothétique dont on pourrait prévoir la formation  sur la base de la théorie réticulaire a aussi été analysé. Le fait que cette macle n'ait jamais été observée, en raison d’une faible restauration de la structure qui serait produite par l'opération de macle, confirme le bien fondé de l'approche. Nous nous attendons à ce que la généralisation de l'approche présentée dans cette thèse fournisse une procédure semi-automatique pour prévoir la probabilité de formation d'une macle. Cela permettrait aux personnes travaillant dans la synthèse cristalline démoduler la fréquence de maclage. Le procédé fait appel à la modification de la morphologie du cristal pour une plus grande exposition et le développement des faces cristallines qui présentent une interface défavorable pour le maclage. / This thesis addresses the structural rationale behind the formation of growth twins, with the purpose of opening a route to the future development of synthesis protocols to reduce the occurrence frequency of twinning. The reason for this effort is that twinning affects negatively the physico-chemical properties of materials and biomaterials of technological interests and reduces the quality of the experimental data on which the structural investigation is based. While on the one hand the reasons for twinning in transformation and mechanical twins are well understood, in the case of growth twins twinning is still seen as an accident linked to aleatory conditions where kinetics, rather than thermodynamics, plays a principal role. A general approach known as the reticular theory of twinning has been developed since the XIX century, based on the existence of a sublattice common to the twinned crystals, which gives the minimal necessary conditions for the occurrence of a twin. This approach is, however, insufficient to discriminate between twins with the same degree of lattice overlap but showing a fairly different occurrence frequency. A structural approach, based on the analysis of the eigensymmetry of the crystallographic orbits building a crystal structure was proposed more than half a century ago (Donnay and Curien, 1960) but remained at an embryonic state, despite some recent revival (Nespolo and Ferraris, 2009). Also, the idea that a slice common to the twinned individuals may contain an operation mapping these individuals was proposed (Holser, 1958) but never brought to a full development. In this thesis, we present a full development of these ideas and show that the structurally necessary conditions for the formation of a growth twin can be described on the basis of the eigensymmetry of the crystallographic orbits and on the sectional layer group giving the symmetry of the common slice. The detailed analysis of three well-know twins demonstrates a clear correlation between the degree of structural restoration by the twin operation and the occurrence frequency of the twins. The analysis of a negative example, i.e. of a hypothetical twin which one would expect on the basis of the reticular theory but has never been observed, strengthens the evidence of this correlation, because of the low structural restoration one would observe in that twin. We expect that the generalisation of the approach presented in this thesis through a semi-automatic procedure will provide crystal growers with a powerful tool to modulate the occurrence frequency of twinning through a modification of the crystal morphologies towards a larger exposure and development of crystal faces which represent an unfavorable interface for twinning.

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.