Engineering problems frequently require solving a sequence of dual linear systems. This paper introduces recycling BiCG, that recycles the Krylov subspace from one pair of linear systems to the next pair. Augmented bi-Lanczos algorithm and modified two-term recurrence are developed for using the recycle space. Recycle space is built from the approximate invariant subspace corresponding to eigenvalues close to the origin. Recycling approach is extended to the CGS and the BiCGSTAB algorithms. Experiments on a convection-diffusion problem give promising results. / Master of Science

Ab-initio methods for calculating electronic structure represent an important field of material physics. The aim of this theses - within the project focused on developing the new method for calculating electronic states in non-periodic structures based on density functional theory, pseudopotentials, and finite elements methods - is to convert Kohn-Sham equations into the form suitable for discretisation, to suggest apropriate method for solving generalized eigenproblem resulting from this discretisation and to implement an eigenvalue solver (or to modify existing one). The thesis describes a procedure for converting the many-particle Schrödinger equation into generalized rank-k-update eigenvalue problem and discusses various methods for its solution. Eigensolver Blzpack, which makes use of the block Lanczos method, has been modified, integrated into the Sfepy framework (a tool for the finite element method calculation) and resulting code has been successfully tested.

Quantum spin models play an important role in theoretical condensed matter physics and quantum information theory. One numerical technique that is frequently used in studies of quantum spin systems is exact diagonalization. In this approach, numerical methods are used to find the lowest eigenvalues and associated eigenvectors of the Hamilton matrix of the quantum system. The computational problem is thus to determine the lowest eigenpairs of an extremely large, sparse matrix. Although many sophisticated iterative techniques for the determination of a small number of lowest eigenpairs can be found in the literature, most exact diagonalization studies of quantum spin systems have employed the Lanczos algorithm. In contrast to this, other methods have been applied very successfully to the similar problem of electronic structure calculations. The well known VASP code for example uses a Block Davidson method as well as the residual-minimization - direct inversion of the iterative subspace algorithm (RMM-DIIS). The Davidson algorithm is closely related to the Lanczos method but usually needs less iterations. The RMM-DIIS method was originally proposed by Pulay and later modified by Wood and Zunger. The RMM-DIIS method is particularly interesting if more than one eigenpair is sought since it does not require orthogonalization of the trial vectors at each step. In this work I study the efficiency of the Lanczos, Block Davidson and RMM-DIIS method when applied to basic quantum spin models like the spin-1/2 Heisenberg chain, ladder and dimerized ladder. I have implemented all three methods and are currently applying the methods to the different models. In our presentation I will compare the three algorithms based on the number of iterations to achieve convergence, the required computational time. An Intel's Many-Integrated Core architecture with Intel Xeon Phi coprocessor 5110P integrates 60 cores with 4 hardware threads per core was used for RMM-DIIS method, the achieved parallel speedups were compared with those obtained on a conventional multi-core system.

In this thesis we consider the Lanczos algoritm and its behaviour in finite precision. Having summarized theoretical properties of the algorithm and its connection to orthogonal polynomials, we recall the idea of the Lanczos method for approximating the matrix eigenvalues. As the behaviour of the algorithm is strongly influenced by finite precision arithmetic, the linear independence of the Lanczos vectors is usually lost after a few iterations. We use the most im- portant results from analysis of the finite precision Lanczos algorithm according to Paige, Greenbaum, Strakos and others. Based on that, we study formulation and properties of the mathematical model of finite presicion Lanczos computati- ons suggested by Greenbaum. We carry out numerical experiments in Matlab, which support the theoretical results.

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.

Cette thèse étudie la méthode du gradient conjugué et la méthode de Lanczos pour la résolution de problèmes aux moindres carrés non-linéaires sous déterminés et régularisés par un terme de pénalisation quadratique. Ces problèmes résultent souvent d'une approche du maximum de vraisemblance, et impliquent un ensemble de m observations physiques et n inconnues estimées par régression non linéaire. Nous supposons ici que n est grand par rapport à m. Un tel cas se présente lorsque des champs tridimensionnels sont estimés à partir d'observations physiques, par exemple dans l'assimilation de données appliquée aux modèles du système terrestre. Un algorithme largement utilisé dans ce contexte est la méthode de Gauss- Newton (GN), connue dans la communauté d'assimilation de données sous le nom d'assimilation variationnelle des données quadridimensionnelles. Le procédé GN repose sur la résolution approchée d'une séquence de moindres carrés linéaires optimale dans laquelle la fonction coût non-linéaire des moindres carrés est approximée par une fonction quadratique dans le voisinage de l'itération non linéaire en cours. Cependant, il est bien connu que cette simple variante de l'algorithme de Gauss-Newton ne garantit pas une diminution monotone de la fonction coût et sa convergence n'est donc pas garantie. Cette difficulté est généralement surmontée en utilisant une recherche linéaire (Dennis and Schnabel, 1983) ou une méthode de région de confiance (Conn, Gould and Toint, 2000), qui assure la convergence globale des points critiques du premier ordre sous des hypothèses faibles. Nous considérons la seconde de ces approches dans cette thèse. En outre, compte tenu de la grande échelle de ce problème, nous proposons ici d'utiliser un algorithme de région de confiance particulier s'appuyant sur la méthode du gradient conjugué tronqué de Steihaug-Toint pour la résolution approchée du sous-problème (Conn, Gould and Toint, 2000, p. 133-139) La résolution de ce sous-problème dans un espace à n dimensions (par CG ou Lanczos) est considérée comme l'approche primale. Comme alternative, une réduction significative du coût de calcul est possible en réécrivant l'approximation quadratique dans l'espace à m dimensions associé aux observations. Ceci est important pour les applications à grande échelle telles que celles quotidiennement traitées dans les systèmes de prévisions météorologiques. Cette approche, qui effectue la minimisation de l'espace à m dimensions à l'aide CG ou de ces variantes, est considérée comme l'approche duale. La première approche proposée (Da Silva et al., 1995; Cohn et al., 1998; Courtier, 1997), connue sous le nom de Système d'analyse Statistique de l'espace Physique (PSAS) dans la communauté d'assimilation de données, commence par la minimisation de la fonction de coût duale dans l'espace de dimension m par un CG préconditionné (PCG), puis revient l'espace à n dimensions. Techniquement, l'algorithme se compose de formules de récurrence impliquant des vecteurs de taille m au lieu de vecteurs de taille n. Cependant, l'utilisation de PSAS peut être excessivement coûteuse car il a été remarqué que la fonction de coût linéaire des moindres carrés ne diminue pas monotonement au cours des itérations non-linéaires. Une autre approche duale, connue sous le nom de méthode du gradient conjugué préconditionné restreint (RPCG), a été proposée par Gratton and Tshimanga (2009). Celle-ci génère les mêmes itérations en arithmétique exacte que l'approche primale, à nouveau en utilisant la formule de récurrence impliquant des vecteurs taille m. L'intérêt principal de RPCG est qu'il en résulte une réduction significative de la mémoire utilisée et des coûts de calcul tout en conservant la propriété de convergence souhaitée, contrairement à l'algorithme PSAS. / This thesis investigates the conjugate-gradient method and the Lanczos method for the solution of under-determined nonlinear least-squares problems regularized by a quadratic penalty term. Such problems often result from a maximum likelihood approach, and involve a set of m physical observations and n unknowns that are estimated by nonlinear regression. We suppose here that n is large compared to m. These problems are encountered for instance when three-dimensional fields are estimated from physical observations, as is the case in data assimilation in Earth system models. A widely used algorithm in this context is the Gauss-Newton (GN) method, known in the data assimilation community under the name of incremental four dimensional variational data assimilation. The GN method relies on the approximate solution of a sequence of linear least-squares problems in which the nonlinear least-squares cost function is approximated by a quadratic function in the neighbourhood of the current nonlinear iterate. However, it is well known that this simple variant of the Gauss-Newton algorithm does not ensure a monotonic decrease of the cost function and that convergence is not guaranteed. Removing this difficulty is typically achieved by using a line-search (Dennis and Schnabel, 1983) or trust-region (Conn, Gould and Toint, 2000) strategy, which ensures global convergence to first order critical points under mild assumptions. We consider the second of these approaches in this thesis. Moreover, taking into consideration the large-scale nature of the problem, we propose here to use a particular trust-region algorithm relying on the Steihaug-Toint truncated conjugate-gradient method for the approximate solution of the subproblem (Conn, Gould and Toint, 2000, pp. 133-139). Solving this subproblem in the n-dimensional space (by CG or Lanczos) is referred to as the primal approach. Alternatively, a significant reduction in the computational cost is possible by rewriting the quadratic approximation in the m-dimensional space associated with the observations. This is important for large-scale applications such as those solved daily in weather prediction systems. This approach, which performs the minimization in the m-dimensional space using CG or variants thereof, is referred to as the dual approach. The first proposed dual approach (Courtier, 1997), known as the Physical-space Statistical Analysis System (PSAS) in the data assimilation community starts by solving the corresponding dual cost function in m-dimensional space by a standard preconditioned CG (PCG), and then recovers the step in n-dimensional space through multiplication by an n by m matrix. Technically, the algorithm consists of recurrence formulas involving m-vectors instead of n-vectors. However, the use of PSAS can be unduly costly as it was noticed that the linear least-squares cost function does not monotonically decrease along the nonlinear iterations when applying standard termination. Another dual approach has been proposed by Gratton and Tshimanga (2009) and is known as the Restricted Preconditioned Conjugate Gradient (RPCG) method. It generates the same iterates in exact arithmetic as those generated by the primal approach, again using recursion formula involving m-vectors. The main interest of RPCG is that it results in significant reduction of both memory and computational costs while maintaining the desired convergence property, in contrast with the PSAS algorithm. The relation between these two dual approaches and the question of deriving efficient preconditioners (Gratton, Sartenaer and Tshimanga, 2011), essential when large-scale problems are considered, was not addressed in Gratton and Tshimanga (2009).

A restarted symplectic Lanczos method for the Hamiltonian eigenvalue problem is presented. The Lanczos vectors are constructed to form a symplectic basis. Breakdowns and near-breakdowns are overcome by inexpensive implicit restarts. The method is used to compute eigenvalues, eigenvectors and invariant subspaces of large and sparse Hamiltonian matrices and low rank approximations to the solution of continuous-time algebraic Riccati equations with large and sparse coefficient matrices.

A restarted symplectic Lanczos method for the Hamiltonian eigenvalue problem is presented. The Lanczos vectors are constructed to form a symplectic basis. Breakdowns and near-breakdowns are overcome by inexpensive implicit restarts. The method is used to compute eigenvalues, eigenvectors and invariant subspaces of large and sparse Hamiltonian matrices and low rank approximations to the solution of continuous-time algebraic Riccati equations with large and sparse coefficient matrices.

<p>We consider a system of few electrons trapped in a two-dimensional circularquantum dot with harmonic confinement and in the presence of ahomogeneous magnetic field, with focus on the role of e-e interaction. Byperforming the exact diagonalization of the Hamiltonian in second quantization,the low-lying energy levels for spin polarized system are obtained. The singlet-triplet oscillation in the ground state of the two-electron system showing up inthe result is explained due to the role of Coulomb interaction. The splitting ofthe lowest Landau level is another effect of the e-e interaction, which is alsoobserved in the results.</p>

We consider a system of few electrons trapped in a two-dimensional circularquantum dot with harmonic confinement and in the presence of ahomogeneous magnetic field, with focus on the role of e-e interaction. Byperforming the exact diagonalization of the Hamiltonian in second quantization,the low-lying energy levels for spin polarized system are obtained. The singlet-triplet oscillation in the ground state of the two-electron system showing up inthe result is explained due to the role of Coulomb interaction. The splitting ofthe lowest Landau level is another effect of the e-e interaction, which is alsoobserved in the results.