A steady-state, single phase subchannel solver was created for the purpose of integration into a multi-physics nuclear fuel performance code. Since applications of such a code include full nuclear reactor core flow simulation, a thorough investigation of efficient solution techniques is a requirement. Execution time profiling found that formation of the Jacobian matrix required by the nonlinear Newton solve was found to be the most time-consuming step in solution of the subchannel equations, so several techniques were tested to minimize the time spent on this task, such as finite difference and the formation of an approximate Jacobian. Simple Jacobian lagging was shown to be very effective at reducing the total time computing the Jacobian throughout the Newton iteration process. Various linear solution techniques were investigated with the subchannel equations, such as the generalized minimal residual method (GMRES) and the aggregation- based algebraic multigrid method (AGMG). A number of physics-based preconditioners were created, based on a simplified formulation with no crossflow between subchannels, and it was found that of the preconditioners developed for this research, the most promising was a preconditioner that fully decoupled the subchannels by ignoring crossflow, conduction, and turbulent momentum exchange between subchannels. This independence between subchannels makes the task of parallelization in the preconditioner to be very feasible. However, AGMG clearly proved to be the most efficient linear solution technique for the subchannel equations, solving the linear systems in less than 5 percent of the time required for preconditioned GMRES.

Thèse doctorat : Informatique : Rennes 1 : 2008. Thèse doctorat : Informatique : Yaoundé 1 : 2008. / Titre provenant de la page du titre du document électronique. Bibliogr. p.110-113.

The Biconjugate Gradient (BiCG) method is an iterative Krylov subspace method that utilizes a 3-term recurrence.  BiCG is the basis of several very popular methods, such as BiCGStab.  The short recurrence makes BiCG preferable to other Krylov methods because of decreased memory usage and CPU time.  However, BiCG does not satisfy any optimality conditions and it has been shown that for up to n/2-1 iterations, a special choice of the left starting vector can cause BiCG to follow {em any} 3-term recurrence.  Despite this apparent sensitivity, BiCG often converges well in practice.  This paper seeks to explain why BiCG converges so well, and what conditions can cause BiCG to behave poorly.  We use tools such as the singular value decomposition and eigenvalue decomposition to establish bounds on the residuals of BiCG and make links between BiCG and optimal Krylov methods. / Master of Science

The GMRES method is a widely used iterative method for solving the linear systems, of the form Ax = b, especially for the solution of discretized partial differential equations. With an appropriate preconditioner, the solution of the linear system Ax = b can be achieved with less computational effort. Additive Schwarz Preconditioners have two good properties. First, they are easily parallelizable, since several smaller linear systems need to be solved: one system for each of the sub-domains, usually corresponding to the restriction of the differential operator to that subdomain. These are called local problems. Second, if a coarse problem is introduced, they are optimal in the sense that bounds on the convergence rate of the preconditioned iterative method are independent (or slowly dependent) on the finite element mesh size and the number of subproblems. We study certain cases where the same optimality can be obtained without a coarse grid correction. In another part of this thesis we consider inexact GMRES when applied to singular (or nearly singular) linear systems. This applies when instead of matrix-vector products with A, one uses A = A+E for some error matrix E which usually changes from one iteration to the next. Following a similar study by Simoncini and Szyld (2003) for nonsingular systems, we prescribe how to relax the exactness of the matrixvector product and still achieve the desired convergence. In addition, similar criteria is given to guarantee that the computed residual with the inexact method is close to the true residual. Furthermore, we give a new computable criteria to determine the inexactness of matrix-vector product using in inexact CG, and applied it onto control problems governed by parabolic partial differential equations. / Mathematics

As groundwater models are being used increasingly in the area of resource allocation, there has been an increase in the level of complexity in an attempt to capture heterogeneity, complex geometries and detail in interaction between the model domain and the outside hydraulic influences. As models strive to represent the real world in ever increasing detail, there is a strong likelihood that the boundary conditions will become nonlinear. Nonlinearities exist in the groundwater flow equation even in simple models when watertable (unconfined) conditions are simulated. This thesis is concerned with how these nonlinearities are treated numerically, with particular focus on the MODFLOW groundwater flow software and the nonlinear nature of the unconfined condition simulation. One of the limitations of MODFLOW is that it employs a first order fixed point iterative scheme to linearise the nonlinear system that arises as a result of the finite difference discretisation process, which is well known to offer slow convergence rates for highly nonlinear problems. However, Newton's method can achieve quadratic convergence and is more effective at dealing with higher levels of nonlinearity. Consequently, the main objective of this research is to investigate the inclusion of Newton's method to the suite of computational tools in MODFLOW to enhance its flexibility in dealing with the increasing complexity of real world problems, as well as providing a more competitive and efficient solution methodology. Furthermore, the underpinning linear iterative solvers that MODFLOW currently utilises are targeted at symmetric systems and a consequence of using Newton's method would be the requirement to solve non-symmetric Jacobian systems. Therefore, another important aspect of this work is to investigate linear iterative solution techniques that handle such systems, including the newer Krylov style solvers GMRES and BiCGSTAB. To achieve these objectives a number of simple benchmark problems involving nonlinearities through the simulation of unconfined conditions were established to compare the computational performance of the existing MODFLOW solvers to the new solution strategies investigated here. One of the highlights of these comparisons was that Newton's method when combined with an appropriately preconditioned Krylov solver was on average greater than 40% more CPU time efficient than the Picard based solution techniques. Furthermore, a significant amount of this time saving came from the reduction in the number of nonlinear iterations due to the quadratic nature of Newton's method. It was also found that Newton's method benefited more from improved initial conditions than Picard's method. Of all the linear iterative solvers tested, GMRES required the least amount of computational effort. While the Newton method involves more complexity in its implementation, this should not be interpreted as prohibitive in its application. The results here show that the extra work does result in performance increase, and thus the effort is certainly worth it.

Accelerating the convergence rate of Krylov subspace methods with parallelizable preconditioners is essential for obtaining effective iterative solvers for very large linear systems of equations. Substructuring provides a framework for constructing robust and parallel preconditioners for linear systems arising from the discretization of boundary value problems. Although collocation is a very general and effective discretization technique for many PDE problems, there has been relatively little work on preconditioners for collocation problems. This thesis proposes two preconditioning methods for solving linear systems of equations arising from Hermite bicubic collocation discretization of elliptic partial differential equations on square domains with mixed boundary conditions. The first method, called <i>edge preconditioning</i>, is based on a decomposition of the domain in parallel strips, and the second, called <i>edge-vertex preconditioning</i>, is based on a two-dimensional decomposition. The preconditioners are derived in terms of two special rectangular grids -- a coarse grid with diameter <i>H</i> and a hybrid coarse/fine grid -- which together with the fine grid of diameter <i>h</i> provide the framework for approximating the interface problem induced by substructuring. We show that the proposed methods are effective for nonsymmetric indefinite problems, both from the point of view of the cost per iteration and of the number of iterations. For an appropriate choice of <i>H</i>, the edge preconditioner requires <i>O(N)</i> arithmetic operations per iteration, while the edge-vertex preconditioner requires <i>O(N^4/3)</i> operations, where <i>N</i> is the number of unknowns. For the edge-vertex preconditioner, the number of iterations is almost constant when <i>h</i> and <i>H</i> decrease such that <i>H/h</i> is held constant and it increases very slowly with <i>H</i> when <i>h</i> is held constant. For both the edge- and edge-vertex preconditioners the number of iterations depends only weakly on <i>h</i> when <i>H</i> is constant. The edge-vertex preconditioner outperforms the edge-preconditioner for small enough <i>H</i>. Numerical experiments illustrate the parallel efficiency of the preconditioners which is similar or even better than that provided by the well-known PETSc parallel software library for scientific computing. / Ph. D.

La modélisation numérique de la multi-fissuration et son influence sur les ouvrages du Génie Civil reste un sujet ouvert et nécessite le développement de nouveaux outils numériques de plus en plus performants. L’approche retenue dans cette thèse est basée sur l’utilisation des concepts des équations intégrales de Galerkin accélérées par la méthode multipôle rapide. Les méthodes intégrales sont bien connues pour leur souplesse à définir des géométries complexes en 3D. Elles restent également très performantes en mécanique de la rupture, lors de la détermination des champs singuliers au voisinage des fissures. La Méthode Multipôle Rapide, quant à elle, permet via une judicieuse reformulation des fonctions fondamentales propres aux formulations intégrales, de réduire considérablement le coût des calculs. La mise en œuvre de la FM-SGBEM a permis de pallier les difficultés rencontrées lors de la phase de résolution et ce lorsqu’on traite de domaines de grandes tailles par équations intégrales de Galerkin pures. Les présents travaux, viennent en partie optimiser et renforcer cette phase dans les environnements numériques existants. D’autre part, des adaptations et des développements théoriques des formulations FM-SGBEM pour prendre en compte le caractère hétérogène des domaines en Génie Civil qui en découlent, ont fait l’objet d’une large partie des travaux développés dans cette thèse. La modélisation du phénomène de propagation de fissures par fatigue a également été étudiée avec succès. Enfin, une application sur une structure de chaussée souple a permis de valider les modèles ainsi développés en propagation de fissures par fatigue dans des structures hétérogènes. De réelles perspectives d’optimisations et de développements de cet outil numérique restent envisagées. / The modeling of cracks and its influence on the understanding of the behaviors of the civil engineering structures is an open topic since many decades. To take into consideration complex configurations, it is necessary to construct more robust and more efficient algorithms. In this work, the approach Galerkin of the boundary integral equations (Symmetric Galerkin Boundary Element Method) coupled with the Fast Multipole Method (FMM) has been adopted. The boundary analysis are well-known for the flexibility to treat sophisticated geometries (unbounded/semi-unbounded) whilst reducing the problem dimension or for the good accuracy when dealing with the singularities. By coupling with the FMM, all the bottle-necks of the traditional BEM due to the fully-populated matrices or the slow evaluations of the integrals have been reduced, thus making the FM-SGBEM an attractive alternative for problems in fracture mechanics. In this work, the existing single-region formulations have been extended to multi-region configurations along with several types of solicitations. Many efforts have also been spent to improve the efficiency of the numerical algorithms. Fatigue crack propagations have been implemented and some practical simulations have been considered. The obtained results have validated the numerical program and have also opened many perspectives of further developments for the code.

In this dissertation, we study iterative methods for computing eigenvalues and exponentials of large matrices. These types of computational problems arise in a large number of applications, including mathematical models in economics, physical and biological processes. Although numerical methods for computing eigenvalues and matrix exponentials have been well studied in the literature, there is a lack of analysis in inexact iterative methods for eigenvalue computation and certain variants of the Krylov subspace methods for approximating the matrix exponentials. In this work, we proposed an inexact inverse subspace iteration method that generalizes the inexact inverse iteration for computing multiple and clustered eigenvalues of a generalized eigenvalue problem. Compared with other methods, the inexact inverse subspace iteration method is generally more robust. Convergence analysis showed that the linear convergence rate of the exact case is preserved. The second part of the work is to present an inverse Lanczos method to approximate the product of a matrix exponential and a vector. This is proposed to allow use of larger time step in a time-propagation scheme for solving linear initial value problems. Error analysis is given for the inverse Lanczos method, the standard Lanczos method as well as the shift-and-invert Lanczos method. The analysis demonstrates different behaviors of these variants and helps in choosing which variant to use in practice.

The Generalized Minimal Residual method (GMRES) is often used to solve a nonsymmetric linear system Ax = b. But its convergence analysis is a rather difficult task in general. A commonly used approach is to diagonalize A = XΛX-1 and then separate the study of GMRES convergence behavior into optimizing the condition number of X and a polynomial minimization problem over As spectrum. This artificial separation could greatly overestimate GMRES residuals and likely yields error bounds that are too far from the actual ones. On the other hand, considering the effects of both As spectrum and the conditioning of X at the same time poses a difficult challenge, perhaps impossible to deal with in general but only possible for certain particular linear systems. This thesis will do so for a (nonsymmetric) tridiagonal Toeplitz system. Sharp error bounds on and sometimes exact expressions for residuals are obtained. These expressions and/or bounds are in terms of the three parameters that define A and Chebyshev polynomials of the first kind or the second kind.

Nesse trabalho apresentamos algoritmos adaptativos do M´etodo do Res´ıduo M´ınimo Generalizado (GMRES) [Saad e Schultz, 1986], um m´etodo iterativo para resolver sistemas de equa¸c˜oes lineares com matrizes n˜ao sim´etricas e esparsas, o qual baseia-se nos m´etodos de proje¸c˜ao ortogonal sobre um subespa¸co de Krylov. O GMRES apresenta uma vers˜ao reinicializada, denotada por GMRES(m), tamb´em proposta por [Saad e Schultz, 1986], com o intuito de permitir a utiliza¸c˜ao do m´etodo para resolver grandes sistemas de n equa¸c˜oes, sendo n a dimens˜ao da matriz dos coeficientes do sistema, j´a que a vers˜ao n˜ao-reinicializada (“Full-GMRES”) apresenta um gasto de mem´oria proporcional a n2 e de n´umero de opera¸c˜oes de ponto-flutuante proporcional a n3, no pior caso. No entanto, escolher um valor apropriado para m ´e dif´ıcil, sendo m a dimens˜ao da base do subespa¸co de Krylov, visto que dependendo do valor do m podemos obter a estagna¸c˜ao ou uma r´apida convergˆencia. Dessa forma, nesse trabalho, acrescentamos ao GMRES(m) e algumas de suas variantes um crit´erio que tem por objetivo escolher, adequadamente, a dimens˜ao, m da base do subespa¸co de Krylov para o problema o qual deseja-se resolver, visando assim uma mais r´apida, e poss´ıvel, convergˆencia. Aproximadamente duas centenas de experimentos foram realizados utilizando as matrizes da Cole¸c˜ao Harwell-Boeing [MCSD/ITL/NIST, 2003], que foram utilizados para mostrar o comportamento dos algoritmos adaptativos. Foram obtidos resultados muito bons; isso poder´a ser constatado atrav´es da an´alise das tabelas e tamb´em da observa ¸c˜ao dos gr´aficos expostos ao longo desse trabalho.