Métodos tipo simplex são a base dos principais softwares utilizados na resolução de problemas de otimização linear. A implementação computacional direta destes métodos, assim como são descritos na teoria, leva a resultados indesejáveis na resolução de problemas reais de grande porte. Assim, a utilização de técnicas computacionais adequadas é fundamental para uma implementação eficiente e estável. Neste trabalho, as principais técnicas são discutidas, com enfoque naquelas que buscam proporcionar a estabilidade numérica do método: utilização de tolerâncias, estabilização do teste da razão, mudança de escala e representação da matriz básica. Para este último tópico, são apresentadas duas técnicas, a Forma Produto da Inversa e a Decomposição LU. A análise das abordagens é feita baseando-se na resolução dos problemas da biblioteca Netlib / Simplex-type methods are the basis of the main linear optimization solvers. The straightforward implementation of these methods as they are presented in theory yield unexpected results in solving reallife large-scale problems. Hence, it is essencial to use suitable computational techniques for an efficient and stable implementation. In this thesis, we address the main techniques focusing on those which aim for numerical stability of the method: use of tolerances, stable ratio test, scaling and representation of the basis matrix. For the latter topic, we present two techniques, the Product Form of Inverse and the LU decomposition. The Netlib problems are solved using the approaches addressed and the results are analyzed

Orientadores: Carlile Campos Lavor, Jose Mario Martinez / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-11T21:12:00Z (GMT). No. of bitstreams: 1 Goncalves_MarcosRobertodaSilva_M.pdf: 1220561 bytes, checksum: e3b9dadf0b151f53d8a3e0e572b4c7ab (MD5) Previous issue date: 2008 / Resumo: Neste trabalho, abordamos o problema da determinação de pontos de intersecção de n esferas no Rn. Este problema, além de ser importante matematicamente, é um problema com muitas aplicações, que vão desde a localização de pontos no globo, pelo sistema GPS, até a posicionamento de átomos em estruturas moleculares. O problema de encontrar a intersecção de n esferas no Rn é, em geral, formulado como um conjunto de n equações não-lineares, onde se deseja determinar a sua solução através de um método eficiente e confiável. Mostramos que, com exceção de alguns casos, o problema é geralmente resolvido de forma eficaz, empregando técnicas de álgebra linear. Reformulamos o problema de forma a convertê-lo em um problema linear e apresentamos dois métodos baseados na decomposição de matrizes. Testamos os métodos para casos particulares de baixa dimensão, analisando o custo computacional e possíveis dificuldades que podem surgir devido a erros de medição. / Abstract: We consider the problem of determining the points of intersection of n spheres in R n. This problem has many applications, such as the location of points on the globe by the GPS system and problems related to molecular geometry optimization. The problem of finding the intersection of n spheres in R n is generally expressed as a set of nonlinear equations, where we want to establish an efficient and reliable method to find their solution. We show that, in general, the problem can be solved effectively employing techniques of linear algebra. We reformulate the problem in order to transform it into a linear problem and present two methods based on the decomposition of matrices. We also test the methods in small instances and analyze the computational cost and possible difficulties that may arise due to errors of measurement. / Mestrado / Mestre em Matemática

Métodos tipo simplex são a base dos principais softwares utilizados na resolução de problemas de otimização linear. A implementação computacional direta destes métodos, assim como são descritos na teoria, leva a resultados indesejáveis na resolução de problemas reais de grande porte. Assim, a utilização de técnicas computacionais adequadas é fundamental para uma implementação eficiente e estável. Neste trabalho, as principais técnicas são discutidas, com enfoque naquelas que buscam proporcionar a estabilidade numérica do método: utilização de tolerâncias, estabilização do teste da razão, mudança de escala e representação da matriz básica. Para este último tópico, são apresentadas duas técnicas, a Forma Produto da Inversa e a Decomposição LU. A análise das abordagens é feita baseando-se na resolução dos problemas da biblioteca Netlib / Simplex-type methods are the basis of the main linear optimization solvers. The straightforward implementation of these methods as they are presented in theory yield unexpected results in solving reallife large-scale problems. Hence, it is essencial to use suitable computational techniques for an efficient and stable implementation. In this thesis, we address the main techniques focusing on those which aim for numerical stability of the method: use of tolerances, stable ratio test, scaling and representation of the basis matrix. For the latter topic, we present two techniques, the Product Form of Inverse and the LU decomposition. The Netlib problems are solved using the approaches addressed and the results are analyzed

For sequences of related linear systems, the computation of a preconditioner for every system can be expensive. Often a fixed preconditioner is used, but this may not be effective as the matrix changes. This research examines the benefits of both reusing and recycling preconditioners, with special focus on ILUTP and factorized sparse approximate inverses and proposes an update that we refer to as a sparse approximate map or SAM update. Analysis of the residual and eigenvalues of the map will be provided. Applications include the Quantum Monte Carlo method, model reduction, oscillatory hydraulic tomography, diffuse optical tomography, and Helmholtz-type problems. / Master of Science

Cette thèse développe des méthodes de diagonalisation conjointe de matrices et de tenseurs d’ordre trois, et son application à la séparation MIMO de sources de télécommunications numériques. Après un état, les motivations et objectifs de la thèse sont présentés. Les problèmes de la diagonalisation conjointe et de la séparation de sources sont définis et un lien entre ces deux domaines est établi. Par la suite, plusieurs algorithmes itératifs de type Jacobi reposant sur une paramétrisation LU sont développés. Pour chacun des algorithmes, on propose de déterminer les matrices permettant de diagonaliser l’ensemble considéré par l’optimisation d’un critère inverse. On envisage la minimisation du critère selon deux approches : la première, de manière directe, et la seconde, en supposant que les éléments de l’ensemble considéré sont quasiment diagonaux. En ce qui concerne l’estimation des différents paramètres du problème, deux stratégies sont mises en œuvre : l’une consistant à estimer tous les paramètres indépendamment et l’autre reposant sur l’estimation indépendante de couples de paramètres spécifiquement choisis. Ainsi, nous proposons trois algorithmes pour la diagonalisation conjointe de matrices complexes symétriques ou hermitiennes et deux algorithmes pour la diagonalisation conjointe d’ensembles de tenseurs symétriques ou non-symétriques ou admettant une décomposition INDSCAL. Nous montrons aussi le lien existant entre la diagonalisation conjointe de tenseurs d’ordre trois et la décomposition canonique polyadique d’un tenseur d’ordre quatre, puis nous comparons les algorithmes développés à différentes méthodes de la littérature. Le bon comportement des algorithmes proposés est illustré au moyen de simulations numériques. Puis, ils sont validés dans le cadre de la séparation de sources de télécommunications numériques. / This thesis develops joint diagonalization of matrices and third-order tensors methods for MIMO source separation in the field of digital telecommunications. After a state of the art, the motivations and the objectives are presented. Then the joint diagonalisation and the blind source separation issues are defined and a link between both fields is established. Thereafter, five Jacobi-like iterative algorithms based on an LU parameterization are developed. For each of them, we propose to derive the diagonalization matrix by optimizing an inverse criterion. Two ways are investigated : minimizing the criterion in a direct way or assuming that the elements from the considered set are almost diagonal. Regarding the parameters derivation, two strategies are implemented : one consists in estimating each parameter independently, the other consists in the independent derivation of couple of well-chosen parameters. Hence, we propose three algorithms for the joint diagonalization of symmetric complex matrices or hermitian ones. The first one relies on searching for the roots of the criterion derivative, the second one relies on a minor eigenvector research and the last one relies on a gradient descent method enhanced by computation of the optimal adaptation step. In the framework of joint diagonalization of symmetric, INDSCAL or non symmetric third-order tensors, we have developed two algorithms. For each of them, the parameters derivation is done by computing the roots of the considered criterion derivative. We also show the link between the joint diagonalization of a third-order tensor set and the canonical polyadic decomposition of a fourth-order tensor. We confront both methods through numerical simulations. The good behavior of the proposed algorithms is illustrated by means of computing simulations. Finally, they are applied to the source separation of digital telecommunication signals.