Globally convergent homotopy methods are used to solve difficult nonlinear systems of equations by tracking the zero curve of a homotopy map. Homotopy curve tracking involves solving a sequence of linear systems, which often vary greatly in difficulty. In this research, a popular iterative solution tool, GMRES(k), is adapted to deal with the sequence of such systems. The proposed adaptive strategy of GMRES(k) allows tuning of the restart parameter k based on the GMRES convergence rate for the given problem. Adaptive GMRES(k) is shown to be superior to several other iterative techniques on analog circuit simulation problems and on postbuckling structural analysis problems. Developing parallel techniques for robust but expensive sequential computations, such as globally convergent homotopy methods, is important. The design of these techniques encompasses the functionality of the iterative method (adaptive GMRES(k)) implemented sequentially and is based on the results of a parallel performance analysis of several implementations. An implementation of adaptive GMRES(k) with Householder reflections in its orthogonalization phase is developed. It is shown that the efficiency of linear system solution by the adaptive GMRES(k) algorithm depends on the change in problem difficulty when the problem is scaled. In contrast, a standard GMRES(k) implementation using Householder reflections maintains a constant efficiency with increase in problem size and number of processors, as concluded analytically and experimentally. The supporting numerical results are obtained on three distributed memory homogeneous parallel architectures: CRAY T3E, Intel Paragon, and IBM SP2. / Ph. D.

Krylov subspace methods are the state-of-the-art iterative algorithms for solving large, sparse systems of equations, which are ubiquitous throughout scientific computing. Even with Krylov methods, these problems are often infeasible to solve on standard workstation computers and must be solved instead on supercomputers. Most modern supercomputers fall into the category of “heterogeneous architectures”, typically meaning a combination of CPU and GPU processors. Thus, development and analysis of Krylov subspace methods on these heterogeneous architectures is of fundamental importance to modern scientific computing. This dissertation focuses on how this relates to several specific problems. Thefirst analyzes the performance of block GMRES (BGMRES) compared to GMRES for linear systems with multiple right hand sides (RHS) on both CPUs and GPUs, and modelling when BGMRES is most advantageous over GMRES on the GPU. On CPUs, the current paradigm is that if one wishes to solve a system of equations with multiple RHS, BGMRES can indeed outperform GMRES, but not always. Our original goal was to see if there are some cases for which BGMRES is slower in execution time on the CPU than GMRES on the CPU, while on the GPU, the reverse holds. This is true, and we generally observe much faster execution times and larger improvements in the case of BGMRES on the GPU. We also observe that for any fixed matrix, when the number of RHS increase, there is a point in which the improvements start to decrease and eventually any advantage of the (unrestarted) block method is lost. We present a new computational model which helps us explain why this is so. The significance of this analysis is that it first demonstrates increased potential of block Krylov methods on heterogeneous architectures than on previously studied CPU-only machines. Moreover, the theoretical runtime model can be used to identify an optimal partitioning strategy of the RHS for solving systems with many RHS. The second problem studies the s-step GMRES method, which is an implementation of GMRES that attains high performance on modern heterogeneous machines by generating s Krylov basis vectors per iteration, and then orthogonalizing the vectors in a block-wise fashion. The use of s-step GMRES is currently limited because the algorithm is prone to numerical instabilities, partially due to breakdowns in a tall-and-skinny QR subroutine. Further, a conservatively small step size must be used in practice, limiting the algorithm’s performance. To address these issues, first a novel randomized tall-and-skinny QR factorization is presented that is significantly more stable than the current practical algorithms without sacrificing performance on GPUs. Then, a novel two-stage block orthogonalization scheme is introduced that significantly improves the performance of the s-step GMRES algorithm when small step sizes are used. These contributions help make s-step GMRES a more practical method in heterogeneous, and therefore exascale, environments. / Mathematics

Symmetric generalized eigenvalue problems arise in many physical applications and frequently only a few of the eigenpairs are of interest. Typically, the problems are large and sparse, and therefore traditional methods such as the QZ algorithm may not be considered. Moreover, it may be impractical to apply shift-and-invert Lanczos, a favored method for problems of this type, due to difficulties in applying the inverse of the shifted matrix. With these difficulties in mind, Golub and Ye developed an inverse free Krylov subspace algorithm for the symmetric generalized eigenvalue problem. This method does not rely on shift-and-invert transformations for convergence acceleration, but rather a preconditioner is used. The algorithm suffers, however, in the presence of multiple or clustered eigenvalues. Also, it is only applicable to the location of extreme eigenvalues. In this work, we extend the method of Golub and Ye by developing a block generalization of their algorithm which enjoys considerably faster convergence than the usual method in the presence of multiplicities and clusters. Preconditioning techniques for the problems are discussed at length, and some insight is given into how these preconditioners accelerate the method. Finally we discuss a transformation which can be applied so that the algorithm extracts interior eigenvalues. A preconditioner based on a QR factorization with respect to the B-1 inner product is developed and applied in locating interior eigenvalues.

By considering Krylov subspace methods in nonstandard inner products, we develop in this thesis new methods for solving large sparse linear systems and examine the effectiveness of existing preconditioners. We focus on saddle point systems and systems with a nonsymmetric, diagonalizable coefficient matrix. For symmetric saddle point systems, we present a preconditioner that renders the preconditioned saddle point matrix nonsymmetric but self-adjoint with respect to an inner product and for which scaling is not required to apply a short-term recurrence method. The robustness and effectiveness of this preconditioner, when applied to a number of test problems, is demonstrated. We additionally utilize combination preconditioning (Stoll and Wathen. SIAM J. Matrix Anal. Appl. 2008; 30:582-608) to develop three new combination preconditioners. One of these is formed from two preconditioners for which only a MINRES-type method can be applied, and yet a conjugate-gradient type method can be applied to the combination preconditioned system. Numerical experiments show that application of these preconditioners can result in faster convergence. When the coefficient matrix is diagonalizable, but potentially nonsymmetric, we present conditions under which the pseudospectra of a preconditioner and coefficient matrix are identical and characterize the pseudospectra when this condition is not exactly fulfilled. We show that when the preconditioner and coefficient matrix are self-adjoint with respect to nearby symmetric bilinear forms the convergence of a particular minimum residual method is bounded by a term that depends on the spectrum of the preconditioned coefficient matrix and a constant that is small when the symmetric bilinear forms are close. An iteration-dependent bound for GMRES in the Euclidean inner product is presented that shows precisely why a standard bound can be pessimistic. We observe that for certain problems known, effective preconditioners are either self-adjoint with respect to the same symmetric bilinear form as the coefficient matrix or one that is nearby.

Title: Analysis of Krylov subspace methods Author: Tomáš Gergelits Department: Department of Numerical Mathematics Supervisor: prof. Ing. Zdeněk Strakoš, DrSc. Abstract: After the derivation of the Conjugate Gradient method (CG) and the short review of its relationship with other fields of mathematics, this thesis is focused on its convergence behaviour both in exact and finite precision arith- metic. Fundamental difference between the CG and the Chebyshev semi-iterative method is described in detail. Then we investigate the use of the widespread lin- ear convergence bound based on Chebyshev polynomials. Through the example of the composite polynomial convergence bounds it is showed that the effects of rounding errors must be included in any consideration concerning the CG rate of convergence relevant to practical computations. Furthermore, the close corre- spondence between the trajectories of the CG approximations generated in finite precision and exact arithmetic is studied. The thesis is concluded with the discus- sion concerning the sensitivity of the closely related Gauss-Christoffel quadrature. The last two topics may motivate our further research. Keywords: Conjugate Gradient Method, Chebyshev semi-iterative method, fi- nite precision computations, delay of convergence, composite polynomial conver-...

No / The four vector extrapolation methods, minimal polynomial extrapolation, reduced rank extrapolation, modified minimal polynomial extrapolation and the topological epsilon algorithm, when applied to linearly generated vector sequences are Krylov subspace methods and it is known that they are equivalent to some well-known conjugate gradient type methods. However, the vector -algorithm is an extrapolation method, older than the four extrapolation methods above, and no similar results are known for it. In this paper, a determinantal formula for the vector -algorithm is given. Then it is shown that, when applied to a linearly generated vector sequence, the algorithm is also a Krylov subspace method and for a class of matrices the method is equivalent to a preconditioned Lanczos method. A new determinantal formula for the CGS is given, and an algebraic comparison between the vector -algorithm for linear systems and CGS is also given.

Bilinear systems are a class of nonlinear dynamical systems that arise in a variety of applications. In order to obtain a sufficiently accurate representation of the underlying physical phenomenon, these models frequently have state-spaces of very large dimension, resulting in the need for model reduction. In this work, we introduce two new methods for the model reduction of bilinear systems in an interpolation framework. Our first approach is to construct reduced models that satisfy multipoint interpolation constraints defined on the Volterra kernels of the full model. We show that this approach can be used to develop an asymptotically optimal solution to the H_2 model reduction problem for bilinear systems. In our second approach, we construct a solution to a bilinear system realization problem posed in terms of constructing a bilinear realization whose kth-order transfer functions satisfy interpolation conditions in k complex variables. The solution to this realization problem can be used to construct a bilinear system realization directly from sampling data on the kth-order transfer functions, without requiring the formation of the realization matrices for the full bilinear system. / Ph. D.

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.

Thesis (MSc)--Stellenbosch University, 2011. / ENGLISH ABSTRACT: In several numerical approaches to PDEs shifted linear systems of the form (zI - A)x = b, need to be solved for several values of the complex scalar z. Often, these linear systems are large and sparse. This thesis investigates efficient numerical methods for these systems that arise from a contour integral approximation to PDEs and compares these methods with direct solvers. In the first part, we present three model PDEs and discuss numerical approaches to solve them. We use the first problem to demonstrate computations with a dense matrix, the second problem to demonstrate computations with a sparse symmetric matrix and the third problem for a sparse but nonsymmetric matrix. To solve the model PDEs numerically we apply two space discrerization methods, namely the finite difference method and the Chebyshev collocation method. The contour integral method mentioned above is used to integrate with respect to the time variable. In the second part, we study a Hessenberg reduction method for solving shifted linear systems with a dense matrix and present numerical comparison of it with the built-in direct linear system solver in SciPy. Since both are direct methods, in the absence of roundoff errors, they give the same result. However, we find that the Hessenberg reduction method is more efficient in CPU-time than the direct solver. As application we solve a one-dimensional version of the heat equation. In the third part, we present efficient techniques for solving shifted systems with a sparse matrix by Krylov subspace methods. Because of their shift-invariance property, the Krylov methods allow one to obtain approximate solutions for all values of the parameter, by generating a single approximation space. Krylov methods applied to the linear systems are generally slowly convergent and hence preconditioning is necessary to improve the convergence. The use of shift-invert preconditioning is discussed and numerical comparisons with a direct sparse solver are presented. As an application we solve a two-dimensional version of the heat equation with and without a convection term. Our numerical experiments show that the preconditioned Krylov methods are efficient in both computational time and memory space as compared to the direct sparse solver. / AFRIKAANSE OPSOMMING: In verskeie numeriese metodes vir PDVs moet geskuifde lineêre stelsels van die vorm (zI − A)x = b, opgelos word vir verskeie waardes van die komplekse skalaar z. Hierdie stelsels is dikwels groot en yl. Hierdie tesis ondersoek numeriese metodes vir sulke stelsels wat voorkom in kontoerintegraalbenaderings vir PDVs en vergelyk hierdie metodes met direkte metodes vir oplossing. In die eerste gedeelte beskou ons drie model PDVs en bespreek numeriese benaderings om hulle op te los. Die eerste probleem word gebruik om berekenings met ’n vol matriks te demonstreer, die tweede probleem word gebruik om berekenings met yl, simmetriese matrikse te demonstreer en die derde probleem vir yl, onsimmetriese matrikse. Om die model PDVs numeries op te los beskou ons twee ruimte-diskretisasie metodes, naamlik die eindige-verskilmetode en die Chebyshev kollokasie-metode. Die kontoerintegraalmetode waarna hierbo verwys is word gebruik om met betrekking tot die tydveranderlike te integreer. In die tweede gedeelte bestudeer ons ’n Hessenberg ontbindingsmetode om geskuifde lineêre stelsels met ’n vol matriks op te los, en ons rapporteer numeriese vergelykings daarvan met die ingeboude direkte oplosser vir lineêre stelsels in SciPy. Aangesien beide metodes direk is lewer hulle dieselfde resultate in die afwesigheid van afrondingsfoute. Ons het egter bevind dat die Hessenberg ontbindingsmetode meer effektief is in terme van rekenaartyd in vergelyking met die direkte oplosser. As toepassing los ons ’n een-dimensionele weergawe van die hittevergelyking op. In die derde gedeelte beskou ons effektiewe tegnieke om geskuifde stelsels met ’n yl matriks op te los, met Krylov subruimte-metodes. As gevolg van hul skuifinvariansie eienskap, laat die Krylov metodes mens toe om benaderde oplossings te verkry vir alle waardes van die parameter, deur slegs een benaderingsruimte voort te bring. Krylov metodes toegepas op lineêre stelsels is in die algemeen stadig konvergerend, en gevolglik is prekondisionering nodig om die konvergensie te verbeter. Die gebruik van prekondisionering gebasseer op skuif-en-omkeer word bespreek en numeriese vergelykings met direkte oplossers word aangebied. As toepassing los ons ’n twee-dimensionele weergawe van die hittevergelyking op, met ’n konveksie term en daarsonder. Ons numeriese eksperimente dui aan dat die Krylov metodes met prekondisionering effektief is, beide in terme van berekeningstyd en rekenaargeheue, in vergelyking met die direkte metodes.

We propose a new framework for understanding block Krylov subspace methods, which hinges on a matrix-valued inner product. We can recast the ``classical" block Krylov methods, such as O'Leary's block conjugate gradients, global methods, and loop-interchange methods, within this framework. Leveraging the generality of the framework, we develop an efficient restart procedure and error bounds for the shifted block full orthogonalization method (Sh-BFOM(m)). Regarding BFOM as the prototypical block Krylov subspace method, we propose another formalism, which we call modified BFOM, and show that block GMRES and the new block Radau-Lanczos method can be regarded as modified BFOM. In analogy to Sh-BFOM(m), we develop an efficient restart procedure for shifted BGMRES with restarts (Sh-BGMRES(m)), as well as error bounds. Using this framework and shifted block Krylov methods with restarts as a foundation, we formulate block Krylov subspace methods with restarts for matrix functions acting on multiple vectors f(A)B. We obtain convergence bounds for \bfomfom (BFOM for Functions Of Matrices) and block harmonic methods (i.e., BGMRES-like methods) for matrix functions. With various numerical examples, we illustrate our theoretical results on Sh-BFOM and Sh-BGMRES. We also analyze the matrix polynomials associated to the residuals of these methods. Through a variety of real-life applications, we demonstrate the robustness and versatility of B(FOM)^2 and block harmonic methods for matrix functions. A particularly interesting example is the tensor t-function, our proposed definition for the function of a tensor in the tensor t-product formalism. Despite the lack of convergence theory, we also show that the block Radau-Lanczos modification can reduce the number of cycles required to converge for both linear systems and matrix functions. / Mathematics