Orientador: Aurelio Ribeiro Leite de Oliveira / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-24T06:40:02Z (GMT). No. of bitstreams: 1 SunaguaSalgado_Porfirio_D.pdf: 2121161 bytes, checksum: 6d961fd2da8ded7cbc0733d9f190497a (MD5) Previous issue date: 2014 / Resumo: Uma abordagem do método preditor-corretor de Mehrotra para resolver problemas de programação linear de grande porte, que utiliza uma classe do precondicionador separador, para resolver sistemas lineares envolvidos por métodos iterativos precondicionados, necessita de uma base que é encontrada por um sofisticado processo de fatoração LU retangular da matriz de restrições. O precondicionador separador tem bom desempenho perto de uma solução ótima, onde as matrizes envolvidas ficam muito mal condicionadas. Neste trabalho, primeiro desenvolvemos o método preditor-corretor com o parâmetro de penalização a fim de reduzir o mau condicionamento da matriz de equações normais. O sucesso desta abordagem é garantido pela demonstração do teorema de convergência de penalização mista com o parâmetro de barreira. Em seguida, implementamos uma nova abordagem para encontrar uma base para o precondicionador separador mediante um processo de fatoração LU retangular padrão aplicada à matriz transposta de restrições escalada. Na maioria das vezes, esta base encontrada é melhor condicionada que a base do método de fatoração retangular anterior. Testes computacionais comprovam uma redução da média do número de iterações do método de gradientes conjugados precondicionado. Também, a eficácia e a robustez da nova abordagem é comprovada por conseguir uma melhor curva de desempenho / Abstract: The class of splitting preconditioners for the iterative solution of linear systems arising from Mehrotra's predictor-corrector method for large-scale linear programming problems needs to find a base by a sophisticated process based upon applying a rectangular LU factorization. The class of splitting preconditioners works better near a solution of the linear programming problems when the matrices are highly ill-conditioned. In this work, we develop the penalty parameter in Mehrotra's predictor-corrector method in order to reduce the ill-conditioning of the normal equations matrix. The success of this approach is guaranteed by the proof of the theorem of convergence of mixed penalty with the barrier parameter. In addition, we develop and implement a new approach to find a basis for the splitting preconditioner, based upon standard rectangular LU factorization with partial permutation of the transpose of the scaled linear programming constraint matrix. In most cases, the basis is better conditioned than the existing one. Computational tests show a reduction in the average number of iterations of the preconditioned conjugate gradient method. Also, the efficiency and robustness of the new approach is demonstrated by achieving better performance profile / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

The preprint delivers an efficient solution technique for the numerical simulation of crack propagation of 2D linear elastic formulations based on finite elements together with the conjugate gradient method in order to solve the corresponding linear equation systems. The developed iterative numerical approach using hierarchical preconditioners comprehends the interesting feature that the hierarchical data structure will not be destroyed during crack propagation. Thus, one gets the possibility to simulate crack advance in a very effective numerical manner including adaptive mesh refinement and mesh coarsening. Test examples are presented to illustrate the efficiency of the given approach. Numerical simulations of crack propagation are compared with experimental data.

No description available.

No description available.

Sequences of matrices arise in many applications in science and engineering. In this thesis we consider matrices that are closely related (or closely related in groups), and we take advantage of the small differences between them to efficiently solve sequences of linear systems and eigenproblems. Recycling techniques, such as recycling preconditioners or subspaces, are popular approaches for reducing computational cost. In this thesis, we introduce two novel approaches for recycling previously computed information for a subsequent system or eigenproblem, and demonstrate good results for sequences arising in several applications. Preconditioners are often essential for fast convergence of iterative methods. However, computing a good preconditioner can be very expensive, and when solving a sequence of linear systems, we want to avoid computing a new preconditioner too often. Instead, we can recycle a previously computed preconditioner, for which we have good convergence behavior of the preconditioned system. We propose an update technique we call the sparse approximate map, or SAM update, that approximately maps one matrix to another matrix in our sequence. SAM updates are very cheap to compute and apply, preserve good convergence properties of a previously computed preconditioner, and help to amortize the cost of that preconditioner over many linear solves. When solving a sequence of eigenproblems, we can reduce the computational cost of constructing the Krylov space starting with a single vector by warm-starting the eigensolver with a subspace instead. We propose an algorithm to warm-start the Krylov-Schur method using a previously computed approximate invariant subspace. We first compute the approximate Krylov decomposition for a matrix with minimal residual, and use this space to warm-start the eigensolver. We account for the residual matrix when expanding, truncating, and deflating the decomposition and show that the norm of the residual monotonically decreases. This method is effective in reducing the total number of matrix-vector products, and computes an approximate invariant subspace that is as accurate as the one computed with standard Krylov-Schur. In applications where the matrix-vector products require an implicit linear solve, we incorporate Krylov subspace recycling. Finally, in many applications, sequences of matrices take the special form of the sum of the identity matrix, a very low-rank matrix, and a small-in-norm matrix. We consider convergence rates for GMRES applied to these matrices by identifying the sources of sensitivity. / Doctor of Philosophy / Problems in science and engineering often require the solution to many linear systems, or a sequence of systems, that model the behavior of physical phenomena. In order to construct highly accurate mathematical models to describe this behavior, the resulting matrices can be very large, and therefore the linear system can be very expensive to solve. To efficiently solve a sequence of large linear systems, we often use iterative methods, which can require preconditioning techniques to achieve fast convergence. The preconditioners themselves can be very expensive to compute. So, we propose a cheap update technique that approximately maps one matrix to another in the sequence for which we already have a good preconditioner. We then combine the preconditioner and the map and use the updated preconditioner for the current system. Sequences of eigenvalue problems also arise in many scientific applications, such as those modeling disk brake squeal in a motor vehicle. To accurately represent this physical system, large eigenvalue problems must be solved. The behavior of certain eigenvalues can reveal instability in the physical system but to identify these eigenvalues, we must solve a sequence of very large eigenproblems. The eigensolvers used to solve eigenproblems generally begin with a single vector, and instead, we propose starting the method with several vectors, or a subspace. This allows us to reduce the total number of iterations required by the eigensolver while still producing an accurate solution. We demonstrate good results for both of these approaches using sequences of linear systems and eigenvalue problems arising in several real-world applications. Finally, in many applications, sequences of matrices take the special form of the sum of the identity matrix, a very low-rank matrix, and a small-in-norm matrix. We examine the convergence behavior of the iterative method GMRES when solving such a sequence of matrices.

In science and engineering, many applications require the solution of a sequence of linear systems. There are many ways to solve linear systems and we always look for methods that are faster and/or require less storage. In this dissertation, we focus on solving these systems with Krylov subspace methods and how to obtain effective preconditioners inexpensively. We first present an application for electronic structure calculation. A sequence of slowly changing linear systems is produced in the simulation. The linear systems change by rank-one updates. Properties of the system matrix are analyzed. We use Krylov subspace methods to solve these linear systems. Krylov subspace methods need a preconditioner to be efficient and robust. This causes the problem of computing a sequence of preconditioners corresponding to the sequence of linear systems. We use recycling preconditioners, which is to update and reuse existing preconditioner. We investigate and analyze several preconditioners, such as ILU(0), ILUTP, domain decomposition preconditioners, and inexact matrix-vector products with inner-outer iterations. Recycling preconditioners produces cumulative updates to the preconditioner. To reduce the cost of applying the preconditioners, we propose approaches to truncate the cumulative preconditioner updates, which is a low-rank matrix. Two approaches are developed. The first one is to truncate the low-rank matrix using the best approximation given by the singular value decomposition (SVD). This is effective if many singular values are close to zero. If not, based on the ideas underlying GCROT and recycling, we use information from an Arnoldi recurrence to determine which directions to keep. We investigate and analyze their properties. We also prove that both truncation approaches work well under suitable conditions. We apply our truncation approaches on two applications. One is the Quantum Monte Carlo (QMC) method and the other is a nonlinear second order partial differential equation (PDE). For the QMC method, we test both truncation approaches and analyze their results. For the PDE problem, we discretize the equations with finite difference method, solve the nonlinear problem by Newton's method with a line-search, and utilize Krylov subspace methods to solve the linear system in every nonlinear iteration. The preconditioner is updated by Broyden-type rank-one updates, and we truncate the preconditioner updates by using the SVD finally. We demonstrate that the truncation is effective. In the last chapter, we develop a matrix reordering algorithm that improves the diagonal dominance of Slater matrices in the QMC method. If we reorder the entire Slater matrix, we call it global reordering and the cost is O(N^3), which is expensive. As the change is geometrically localized and impacts only one row and a modest number of columns, we propose a local reordering of a submatrix of the Slater matrix. The submatrix has small dimension, which is independent of the size of Slater matrix, and hence the local reordering has constant cost (with respect to the size of Slater matrix). / Ph. D.

Cette thèse vise à concevoir des solveurs efficaces pour résoudre des systèmes linéaires, résultant des problèmes d'optimisation sous contraintes dans certaines applications de dynamique des structures et vibration (la corrélation calcul-essai, la localisation d'erreur, le modèle hybride, l'évaluation des dommages, etc.). Ces applications reposent sur la résolution de problèmes inverses, exprimés sous la forme de la minimisation d'une fonctionnelle en énergie. Cette fonctionnelle implique à la fois, des données issues d'un modèle numérique éléments finis, et des essais expérimentaux. Ceci conduit à des modèles de haute qualité, mais les systèmes linéaires point-selle associés, sont coûteux à résoudre. Nous proposons deux classes différentes de méthodes pour traiter le système. La première classe repose sur une méthode de factorisation directe profitant de la topologie et des propriétés spéciales de la matrice point-selle. Après une première renumérotation pour regrouper les pivots en blocs d'ordre 2. L'élimination de Gauss est conduite à partir de ces pivots et en utilisant un ordre spécial d'élimination réduisant le remplissage. Les résultats numériques confirment des gains significatifs en terme de remplissage, jusqu'à deux fois meilleurs que la littérature pour la topologie étudiée. La seconde classe de solveurs propose une approche à double projection du système étudié sur le noyau des contraintes, en faisant une distinction entre les contraintes cinématiques et celles reliées aux capteurs sur la structure. La première projection est explicite en utilisant une base creuse du noyau. La deuxième est implicite. Elle est basée sur l'emploi d'un préconditionneur contraint avec des méthodes itératives de type Krylov. Différentes approximations des blocs du préconditionneur sont proposées. L'approche est implémentée dans un environnement distribué parallèle utilisant la bibliothèque PETSc. Des gains significatifs en terme de coût de calcul et de mémoire sont illustrés sur plusieurs applications industrielles. / This thesis aims at designing efficient numerical solution methods to solve linear systems, arising in constrained optimization problems in some structural dynamics and vibration applications (test-analysis correlation, model error localization,hybrid model, damage assessment, etc.). These applications rely on solving inverse problems, by means of minimization of an energy-based functional. This latter involves both data from a numerical finite element model and from experimental tests, which leads to high quality models, but the associated linear systems, that have a saddle-point coefficient matrices, are long and costly to solve. We propose two different classes of methods to deal with these problems. First, a direct factorization method that takes advantage of the special structures and properties of these saddle point matrices. The Gaussian elimination factorization is implemented in order to factorize the saddle point matrices block-wise with small blocks of orders 2 and using a fill-in reducing topological ordering. We obtain significant gains in memory cost (up to 50%) due to enhanced factors sparsity in comparison to literature. The second class is based on a double projection of the generated saddle point system onto the nullspace of the constraints. The first projection onto the kinematic constraints is proposed as an explicit process through the computation of a sparse null basis. Then, we detail the application of a constraint preconditioner within a Krylov subspace solver, as an implicit second projection of the system onto the nullspace of the sensors constraints. We further present and compare different approximations of the constraint preconditioner. The approach is implemented in a parallel distributed environment using the PETSc library. Significant gains in computational cost and memory are illustrated on several industrial applications.

Orientadores: Carla Taviane Lucke da Silva Ghidini, Aurelio Ribeiro Leite de Oliveira / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-26T07:23:54Z (GMT). No. of bitstreams: 1 Silva_Marileneda_M.pdf: 942860 bytes, checksum: 97260f526fda7ee0cb3346887580c3fa (MD5) Previous issue date: 2014 / Resumo: Neste trabalho, consideramos o método preditor-corretor, que é uma das variantes mais importantes dos métodos de pontos interiores devido à sua eficiência e convergência rápida. No método preditor-corretor, é preciso resolver dois sistemas lineares a cada iteração para determinar a direção preditora-corretora. A resolução desses sistemas é o passo que requer mais tempo de processamento, devendo, assim, ser realizada de maneira eficiente. Para obter a solução dos sistemas lineares do método preditor-corretor, consideramos dois métodos do subespaço de Krylov: MINRES e GC (método dos gradientes conjugados). Para que esses métodos convirjam mais rapidamente, um precondicionador especialmente desenvolvido para os sistemas lineares oriundos dos métodos de pontos interiores é usado. Experimentos computacionais, em um conjunto variado de problemas de programação linear, foram realizados com o intuito de analisar a eficiência e robustez dos métodos de solução dos sistemas lineares / Abstract: In this work, we consider the predictor-corrector method, which is one of the most important variants of interior point methods due to its efficiency and fast convergence. In the predictor-corrector method, we must solve two linear systems at each iteration to determine the predictor-corrector direction. The solution of these systems is the step that requires more processing time and should therefore be performed efficiently. For the solution of linear systems are two Krylov subspace methods considered: MINRES and CG(the conjugate-gradient method). For these methods a preconditioner specially developed for linear systems arising from interior point methods is used. Computational experiments on a set of linear programming problems were performed in order to analyze the efficiency and robustness of the methods when solving such linear systems / Mestrado / Matematica Aplicada / Mestra em Matemática Aplicada

This paper concerns the solution of plate bending problems in domains composed of rectangles. Domain decomposition (DD) is the basic tool used for both the parallelization of the conjugate gradient method and the construction of efficient parallel preconditioners. A so-called Dirich- let DD preconditioner for systems of linear equations arising from the fi- nite element approximation by non-conforming Adini elements is derived. It is based on the non-overlapping DD, a multilevel preconditioner for the Schur-complement and a fast, almost direct solution method for the Dirichlet problem in rectangular domains based on fast Fourier transform. Making use of Xu's theory of the auxiliary space method we construct an optimal preconditioner for plate problems discretized by conforming Bogner-Fox-Schmidt rectangles. Results of numerical experiments carried out on a multiprocessor sys- tem are given. For the test problems considered the number of iterations is bounded independent of the mesh sizes and independent of the number of subdomains. The resulting parallel preconditioned conjugate gradient method requiresO(h^-2 ln h^-1 ln epsilon^-11) arithmetical operations per processor in order to solve the finite element equations with the relative accuracy epsilon.

Science and engineering problems frequently require solving a sequence of single linear systems or a sequence of dual linear systems. We develop algorithms that recycle Krylov subspaces and preconditioners from one system (or pair of systems) in the sequence to the next, leading to efficient solutions. Besides the benefit of only having to store few Lanczos vectors, using BiConjugate Gradients (BiCG) to solve dual linear systems may have application-specific advantages. For example, using BiCG to solve the dual linear systems arising in interpolatory model reduction provides a backward error formulation in the model reduction framework. Using BiCG to evaluate bilinear forms -- for example, in the variational Monte Carlo (VMC) algorithm for electronic structure calculations -- leads to a quadratic error bound. Since one of our focus areas is sequences of dual linear systems, we introduce recycling BiCG, a BiCG method that recycles two Krylov subspaces from one pair of dual linear systems to the next pair. The derivation of recycling BiCG also builds the foundation for developing recycling variants of other bi-Lanczos based methods like CGS, BiCGSTAB, BiCGSTAB2, BiCGSTAB(l), QMR, and TFQMR. We develop a generalized bi-Lanczos algorithm, where the two matrices of the bi-Lanczos procedure are not each other's conjugate transpose but satisfy this relation over the generated Krylov subspaces. This is sufficient for a short term recurrence. Next, we derive an augmented bi-Lanczos algorithm with recycling and show that this algorithm is a special case of generalized bi-Lanczos. The Petrov-Galerkin approximation that includes recycling in the iteration leads to modified two-term recurrences for the solution and residual updates. We generalize and extend the framework of our recycling BiCG to CGS, BiCGSTAB and BiCGSTAB2. We perform extensive numerical experiments and analyze the generated recycle space. We test all of our recycling algorithms on a discretized partial differential equation (PDE) of convection-diffusion type. This PDE problem provides well-known test cases that are easy to analyze further. We use recycling BiCG in the Iterative Rational Krylov Algorithm (IRKA) for interpolatory model reduction and in the VMC algorithm. For a model reduction problem, we show up to 70% savings in iterations, and we also demonstrate that solving the problem without recycling leads to (about) a 50% increase in runtime. Experiments with recycling BiCG for VMC gives promising results. We also present an algorithm that recycles preconditioners, leading to a dramatic reduction in the cost of VMC for large(r) systems. The main cost of the VMC method is in constructing a sequence of Slater matrices and computing the ratios of determinants for successive Slater matrices. Recent work has improved the scaling of constructing Slater matrices for insulators, so that the cost of constructing Slater matrices in these systems is now linear in the number of particles. However, the cost of computing determinant ratios remains cubic in the number of particles. With the long term aim of simulating much larger systems, we improve the scaling of computing determinant ratios in the VMC method for simulating insulators by using preconditioned iterative solvers. The main contribution here is the development of a method to efficiently compute for the Slater matrices a sequence of preconditioners that make the iterative solver converge rapidly. This involves cheap preconditioner updates, an effective reordering strategy, and a cheap method to monitor instability of ILUTP preconditioners. Using the resulting preconditioned iterative solvers to compute determinant ratios of consecutive Slater matrices reduces the scaling of the VMC algorithm from O(n^3) per sweep to roughly O(n^2), where n is the number of particles, and a sweep is a sequence of n steps, each attempting to move a distinct particle. We demonstrate experimentally that we can achieve the improved scaling without increasing statistical errors. / Ph. D.