Aerodynamic shape optimization and multidisciplinary optimization algorithms have the potential not only to improve conventional aircraft, but also to enable the design of novel configurations. By their very nature, these algorithms generate and analyze a large number of unique shapes, resulting in high computational costs. In order to improve their efficiency and enable their use in the early stages of the design process, a fast and robust flow solution algorithm is necessary. This thesis presents an efficient parallel Newton-Krylov-Schur flow solution algorithm for the three-dimensional Navier-Stokes equations coupled with the Spalart-Allmaras one-equation turbulence model. The algorithm employs second-order summation-by-parts (SBP) operators on multi-block structured grids with simultaneous approximation terms (SATs) to enforce block interface coupling and boundary conditions. The discrete equations are solved iteratively with an inexact-Newton method, while the linear system at each Newton iteration is solved using the flexible Krylov subspace iterative method GMRES with an approximate-Schur parallel preconditioner. The algorithm is thoroughly verified and validated, highlighting the correspondence of the current algorithm with several established flow solvers. The solution for a transonic flow over a wing on a mesh of medium density (15 million nodes) shows good agreement with experimental results. Using 128 processors, deep convergence is obtained in under 90 minutes. The solution of transonic flow over the Common Research Model wing-body geometry with grids with up to 150 million nodes exhibits the expected grid convergence behavior. This case was completed as part of the Fifth AIAA Drag Prediction Workshop, with the algorithm producing solutions that compare favourably with several widely used flow solvers. The algorithm is shown to scale well on over 6000 processors. The results demonstrate the effectiveness of the SBP-SAT spatial discretization, which can be readily extended to high order, in combination with the Newton-Krylov-Schur iterative method to produce a powerful parallel algorithm for the numerical solution of the Reynolds-averaged Navier-Stokes equations. The algorithm can efficiently solve the flow over a range of clean geometries, making it suitable for use at the core of an optimization algorithm.

Partial differential equations are the chief means of providing mathematical models in science, engineering and other fields. Optimal control of partial differential equations (PDEs) has tremendous applications in engineering and science, such as shape optimization, image processing, fluid dynamics, and chemical processes. In this thesis, we develop and analyze several efficient numerical methods for the optimal control problems governed by elliptic PDE, parabolic PDE, and wave PDE, respectively. The thesis consists of six chapters. In Chapter 1, we briefly introduce a few motivating applications and summarize some theoretical and computational foundations of our following developed approaches. In Chapter 2, we establish a new multigrid algorithm to accelerate the semi-smooth Newton method that is applied to the first-order necessary optimality system arising from semi-linear control-constrained elliptic optimal control problems. Under suitable assumptions, the discretized Jacobian matrix is proved to have a uniformly bounded inverse with respect to mesh size. Different from current available approaches, a new strategy that leads to a robust multigrid solver is employed to define the coarse grid operator. Numerical simulations are provided to illustrate the efficiency of the proposed method, which shows to be computationally more efficient than the popular full approximation storage (FAS) multigrid method. In particular, our proposed approach achieves a mesh-independent convergence and its performance is highly robust with respect to the regularization parameter. In Chaper 3, we present a new second-order leapfrog finite difference scheme in time for solving the first-order necessary optimality system of the linear parabolic optimal control problems. The new leapfrog scheme is shown to be unconditionally stable and it provides a second-order accuracy, while the classical leapfrog scheme usually is well-known to be unstable. A mathematical proof for the convergence of the proposed scheme is provided under a suitable norm. Moreover, the proposed leapfrog scheme gives a favorable structure that leads to an effective implementation of a fast solver under the multigrid framework. Numerical examples show that the proposed scheme significantly outperforms the widely used second-order backward time differentiation approach, and the resultant fast solver demonstrates a mesh-independent convergence as well as a linear time complexity. In Chapter 4, we develop a new semi-smooth Newton multigrid algorithm for solving the discretized first-order necessary optimality system that characterizes the optimal solution of semi-linear parabolic PDE optimal control problems with control constraints. A new leapfrog discretization scheme in time associated with the standard five-point stencil in space is established to achieve a second-order accuracy. The convergence (or unconditional stability) of the proposed scheme is proved when time-periodic solutions are considered. Moreover, the derived well-structured discretized Jacobian matrices greatly facilitate the development of an effective smoother in our multigrid algorithm. Numerical simulations are provided to illustrate the effectiveness of the proposed method, which validates the second-order accuracy in solution approximations as well as the optimal linear complexity of computing time. In Chapter 5, we offer a new implicit finite difference scheme in time for solving the first-order necessary optimality system arising in optimal control of wave equations. With a five-point central finite difference scheme in space, the full discretization is proved to be unconditionally convergent with a second-order accuracy, which is not restricted by the classical Courant-Friedrichs-Lewy (CFL) stability condition on the spatial and temporal step sizes. Moreover, based on its advantageous developed structure, an efficient preconditioned Krylov subspace method is provided and analyzed for solving the discretized sparse linear system. Numerical examples are presented to confirm our theoretical conclusions and demonstrate the promising performance of proposed preconditioned iterative solver. Finally, brief summaries and future research perspectives are given in Chapter 6.

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-02-13T20:18:37Z No. of bitstreams: 1 JosimaraTatianeDaSilva_DISSERT.pdf: 1557682 bytes, checksum: fac59260c784cbb83579953ae2c457f9 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-02-16T19:30:20Z (GMT) No. of bitstreams: 1 JosimaraTatianeDaSilva_DISSERT.pdf: 1557682 bytes, checksum: fac59260c784cbb83579953ae2c457f9 (MD5) / Made available in DSpace on 2017-02-16T19:30:20Z (GMT). No. of bitstreams: 1 JosimaraTatianeDaSilva_DISSERT.pdf: 1557682 bytes, checksum: fac59260c784cbb83579953ae2c457f9 (MD5) Previous issue date: 2016-07-19 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior (CAPES) / Este trabalho tem por objetivo investigar o comportamento de converg?ncia do m?todo GMRES (Generalized Minimal RESidual) e sua vers?o GMRES(m), sem e com precondicionador ILU(0) aplicado ? sistemas lineares n?o sim?tricos esparsos. Nosso interesse principal ? verificar se o comportamento destes algoritmos pode ser influenciado pela estrutura das matrizes consideradas, em particular, as Z-matrizes e a influ?ncia da escolha do grau de esparsidade. Entre os par?metros observados, concentramos no raio espectral dessas matrizes, tanto como a norma do res?duo relativo obtido por estes algoritmos. / This study aims to investigate the convergence behavior of the GMRES (Generalized Minimal Residual) method and its version GMRES(m), without and with preconditioner ILU(0) applied to sparse non-symmetric linear systems. Our main interest is to see if the behavior of these algorithms can be influenced by the structure of the matrices considered, in particular, the Z-matrices. Furthermore, the influence of the choice of the degree of sparsity. Among the observed parameters, we focus on the spectral radius of these matrices, as well as the relative residual norm obtained by these algorithms.

We provide a unifying projection-based framework for structure-preserving interpolatory model reduction of parameterized linear dynamical systems, i.e., systems having a structured dependence on parameters that we wish to retain in the reduced-order model. The parameter dependence may be linear or nonlinear and is retained in the reduced-order model. Moreover, we are able to give conditions under which the gradient and Hessian of the system response with respect to the system parameters is matched in the reduced-order model. We provide a systematic approach built on established interpolatory $\mathcal{H}_2$ optimal model reduction methods that will produce parameterized reduced-order models having high fidelity throughout a parameter range of interest. For single input/single output systems with parameters in the input/output maps, we provide reduced-order models that are \emph{optimal} with respect to an $\mathcal{H}_2\otimes\mathcal{L}_2$ joint error measure. The capabilities of these approaches are illustrated by several numerical examples from technical applications.

We consider large and sparse eigenproblems where the spectrum exhibits special symmetries. Here we focus on Hamiltonian symmetry, that is, the spectrum is symmetric with respect to the real and imaginary axes. After briefly discussing quadratic eigenproblems with Hamiltonian spectra we review structured Krylov subspace methods to aprroximate parts of the spectrum of Hamiltonian operators. We will discuss the optimization of the free parameters in the resulting symplectic Lanczos process in order to minimize the conditioning of the (non-orthonormal) Lanczos basis. The effects of our findings are demonstrated for several numerical examples.

The purpose of this thesis is to study how to overcome difficulties one typically encounters when solving non-negative inverse problems by standard Krylov subspace methods. We first give a theoretical background to the non-negative inverse problems. Then we concentrate on selected modifications of Krylov subspace methods known to improve the solution significantly. We describe their properties, provide their implementation and propose an improvement for one of them. After that, numerical experiments are presented giving a comparison of the methods and analyzing the influence of the present parameters on the behavior of the solvers. It is clearly demonstrated, that the methods imposing nonnegativity perform better than the unconstrained methods. Moreover, our improvement leads in some cases to a certain reduction of the number of iterations and consequently to savings of the computational time while preserving a good quality of the approximation.

Die vorliegende Arbeit befasst sich mit der Fragestellung, inwiefern sich gegebene Verfahren zur Approximation von rationalen Krylow-Räumen zur Berechnung von Matrixfunktionen eignen. Als Modellproblem wird dazu eine 2.5D-Formulierung eines Problems aus der Gleichstrom-Geoelektrik mit finiten Elementen formuliert und dann mittels Matrixfunktionen auf rationalen Krylow-Unterräumen gelöst. Ein weiterer Teil beschäftigt sich mit dem Vergleich zweier Verfahren zur Transformation bestehender rationaler Krylow-Räume. Bei beiden Varianten werden die zugrunde liegenden Pole getauscht ohne dass ein explizites Invertieren von Matrizen notwendig ist. In dieser Arbeit werden die über mehrere Publikationen verteilten Grundlagen einheitlich zusammengetragen und fehlende Zusammenhänge ergänzt. Beide Verfahren eignen sich prinzipiell um rationale Krylow-Räume zu approximieren. Dies wird anhand mehrerer Beispiele gezeigt. Anhand des Modellproblems werden Beschränkungen der Methoden verdeutlicht.

No description available.

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

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.