Dissertations / Theses on the topic 'Computation of adjoints'

The technique of automatic differentiation provides directional derivatives and discrete adjoints with working accuracy. A complete complexity analysis of the basic modes of automatic differentiation is available. Therefore, the research activities are focused now on different aspects of the derivative calculation, as for example the efficient implementation by exploitation of structural information, studies of the theoretical properties of the provided derivatives in the context of optimization problems, and the development and analysis of new mathematical algorithms based on discrete adjoint information. According to this motivation, this habilitation presents an analysis of different checkpointing strategies to reduce the memory requirement of the discrete adjoint computation. Additionally, a new algorithm for computing sparse Hessian matrices is presented including a complexity analysis and a report on practical experiments. Hence, the first two contributions of this thesis are dedicated to an efficient computation of discrete adjoints. The analysis of discrete adjoints with respect to their theoretical properties is another important research topic. The third and fourth contribution of this thesis focus on the relation of discrete adjoint information and continuous adjoint information for optimal control problems. Here, differences resulting from different discretization strategies as well as convergence properties of the discrete adjoints are analyzed comprehensively. In the fifth contribution, checkpointing approaches that are successfully applied for the computation of discrete adjoints, are adapted such that they can be used also for the computation of continuous adjoints. Additionally, the fifth contributions presents a new proof of optimality for the binomial checkpointing that is based on new theoretical results. Discrete adjoint information can be applied for example for the approximation of dense Jacobian matrices. The development and analysis of new mathematical algorithms based on these approximate Jacobians is the topic of the sixth contribution. Is was possible to show global convergence to first-order critical points for a whole class of trust-region methods. Here, the usage of inexact Jacobian matrices allows a considerable reduction of the computational complexity.

The technique of automatic differentiation provides directional derivatives and discrete adjoints with working accuracy. A complete complexity analysis of the basic modes of automatic differentiation is available. Therefore, the research activities are focused now on different aspects of the derivative calculation, as for example the efficient implementation by exploitation of structural information, studies of the theoretical properties of the provided derivatives in the context of optimization problems, and the development and analysis of new mathematical algorithms based on discrete adjoint information. According to this motivation, this habilitation presents an analysis of different checkpointing strategies to reduce the memory requirement of the discrete adjoint computation. Additionally, a new algorithm for computing sparse Hessian matrices is presented including a complexity analysis and a report on practical experiments. Hence, the first two contributions of this thesis are dedicated to an efficient computation of discrete adjoints. The analysis of discrete adjoints with respect to their theoretical properties is another important research topic. The third and fourth contribution of this thesis focus on the relation of discrete adjoint information and continuous adjoint information for optimal control problems. Here, differences resulting from different discretization strategies as well as convergence properties of the discrete adjoints are analyzed comprehensively. In the fifth contribution, checkpointing approaches that are successfully applied for the computation of discrete adjoints, are adapted such that they can be used also for the computation of continuous adjoints. Additionally, the fifth contributions presents a new proof of optimality for the binomial checkpointing that is based on new theoretical results. Discrete adjoint information can be applied for example for the approximation of dense Jacobian matrices. The development and analysis of new mathematical algorithms based on these approximate Jacobians is the topic of the sixth contribution. Is was possible to show global convergence to first-order critical points for a whole class of trust-region methods. Here, the usage of inexact Jacobian matrices allows a considerable reduction of the computational complexity.

An adjoint system of the Euler equations of gas dynamics is derived in order to solve aerodynamic shape optimization problems with gradient-based methods. The derivation is based on the fully discrete flow model and involves differentiation and transposition of the system of equations obtained by an unstructured and node-centered finite-volume discretization. Solving the adjoint equations allows an efficient calculation of gradients, also when the subject of optimization is described by hundreds or thousands of design parameters. Such a fine geometry description may cause wavy or otherwise irregular designs during the optimization process. Using the one-to-one mapping defined by a Poisson problem is a known technique that produces smooth design updates while keeping a fine resolution of the geometry. This technique is extended here to combine the smoothing effect with constraints on the geometry, by defining the design updates as solutions of a quadratic programming problem associated with the Poisson problem. These methods are applied to airfoil shape optimization for reduction of the wave drag, that is, the drag caused by gas dynamic effects that occur close to the speed of sound. A second application concerns airfoil design optimization to delay the laminar-to-turbulent transition point in the boundary layer in order to reduce the drag. The latter application has been performed by the author with collaborators, also using gradient-based optimization. Here, the growth of convectively unstable disturbances are modeled by successively solving the Euler equations, the boundary layer equations, and the parabolized stability equations.

This thesis includes a brief introduction to Adjoint Algorithmic Differentiation (AAD), accompanied by numerical examples, step-by-step explanations and runtime comparisons to a finite difference method. In order to show the applicability of AAD in a stochastic setting, it is also applied in the calculation of the arbitrage free price and partial derivatives of a European call option, where the underlying stock has Geometric Brownian motion dynamics. Finally the Hull-White model is calibrated using a set of zero coupon bonds, and a set of swaptions. Using AAD, the partial derivatives of the model are found and used in a Newton-Raphson method in order to find the market's implied volatility. The end result is a Monte Carlo simulated short rate curve and its derivatives with respect to the calibration parameters, i.e. the zero coupon bond and swaption prices.
Denna uppsats innehåller en introduktion till Adjungerad Algoritmisk Differentiering (AAD), tillsammans med numeriska exempel, steg-för-steg beskrivningar samt körtidsjämförelser med en finit differensmetod. För att illustrera applicerbarheten av AAD i ett stokastiskt ramverk, tillämpas metoden i beräkningen av det arbitragefria priset och de partiella derivatorna av en europeisk köp-option, där den underliggande aktien har geometrisk Brownsk dynamik. Slutligen kalibreras Hull-White-modellen genom ett antal nollkupongsobligationer och swap-optioner. Via AAD beräknas de partiella derivatorna för modellen som sedan används i Newton-Raphsons metod för att finna markandens implicita volatilitet. Slutresultatet är en Monte Carlo-simulerad räntekurva och dess derivator med avseende på kalibreringsparametrarna, dvs. nollkupongs- och swap-optionspriserna.

Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2012.
Cataloged from PDF version of thesis.
Includes bibliographical references (p. 75-77).
The cryosphere is comprised of about 33 million km³ of ice, which corresponds to 70 meters of global mean sea level equivalent [30]. Simulating continental ice masses, such as the Antarctic or Greenland Ice Sheets, requires computational models capturing abrupt changes in ice sheet dynamics, which are still poorly understood. Input parameters, such as basal drag and topography, have large effects on the applied stress and flow fields but whose direct observation is very difficult, if not impossible. Computational methods are designed to aid in the development of ice sheet models, ideally identifying the relative importance of each parameter and formulating inverse methods to infer uncertain parameters and thus constrain ice sheet flow. Efficient computation of the tangent linear and adjoint models give researchers easy access to model derivatives. The adjoint and tangent linear models enable efficient global sensitivity computation and parameter optimization on unknown or uncertain ice sheet properties, information used to identify model properties having large effects on sea-level. The adjoint equations are not always easily obtained analytically and often require discretizing additional PDE's. Algorithmic differentiation (AD) decomposes the model into a composite of elementary operations (+, -, *, /, etc ... ) and a source-to-source transformation generates code for the Jacobian and its transpose for each operations. Derivatives computed using the tangent linear and adjoint models, with code generated by AD, are applied to parameter estimation and sensitivity analysis of simple glacier models. AD is applied to two examples, equations describing changes in borehole temperature over time and instantaneous ice velocities. Borehole model predictions and data are compared to infer paleotemperatures, geothermal heat flux, and physical ice properties. Inversion using adjoint methods and AD increases the control space, allowing inference for all uncertain parameters. The sensitivities of ice velocities to basal friction and basal topography are compared. The basal topography has significantly larger sensitivities, suggesting it plays a larger role in flow dynamics and future work should seek to invert for this parameter.
by Andrew D. Davis.
S.M.

The discrete adjoint method allows efficient evaluation of the derivative of a function I(s) with respect to parameters s in situations where I depends on s indirectly, via an intermediate variable w(s), which is computationally expensive to evaluate. In this thesis two applications of this method in the context of computational fluid dynamics are considered. The first is shape optimisation, where the discrete adjoint approach is employed to compute the derivatives with respect to shape parameters for a performance functional depending on the solution of a mathematical flow model which has the form of a discretised system of partial differential equations. In this context particular emphasis is given to efficient solution strategies for the linear systems arising in the discretisation of the flow models. Numerical results for two example problems are presented, demonstrating the utility of the approach. The second application, in adaptive mesh design, allows efficient evaluation of the derivatives of an a posteriori error estimate with respect to the positions of the nodes in a finite element mesh. This novel approach makes additional information available which may be utilised to guide the automatic design of adaptive meshes. Special emphasis is given to problems with anisotropic solution features, for which adaptive anisotropic mesh refinement can deliver significant performance improvements over existing adaptive hrefinement approaches. Two adaptive solution algorithms are presented and compared to existing approaches by applying them to a reaction-diffusion model problem.

Les écoulements instationnaires au-dessus de surfaces discontinues produisent d'important bruit aérodynamique. L'objectif de ce travail de thèse est l'étude aéroacoustique d'écoulement au-dessus de cavités bidimensionnelles rectangulaires, et de trouver des stratégies de réduction du bruit. Des simulations numériques directes des équations bidimensionnelles de Navier-Stokes compressibles ont été réalisées afin d'étudier l'influence des conditions initiales sur le mode d'oscillation de l'écoulement pour des cavités profonde et peu profonde. Les résultats montrent que dans le cas de cavités profondes, l'écoulement oscille selon un régime de couche de cisaillement suivant le second mode de Rossiter, et ce quelle que soit la condition initiale choisie. En revanche, dans le cas de cavités peu profondes, le régime d'oscillation observé peut être en couche de cisaillement ou bien en mode de sillage suivant la condition initiale choisie. Une analyse de sensibilité d'écoulement dans le cas de cavités profondes a été réalisé en utilisant une méthode adjointe. Les équations adjointes ont été forcées par une perturbation localisée sinusoïdale soit de la quantité de mouvement suivant x adjointe (au voisinage de la couche de cisaillement), soit de la densité adjointe (loin de la cavité). Les résultats désignent une région de l'écoulement très sensible à l'ajout de masse, et localisée au voisinage du coin supérieur amont de la cavité. Par conséquent, un actionneur de type soufflage/aspiration placé au bord d'attaque de la cavité agira sur les fluctuations de quantité de mouvement suivant x au voisinage de la couche de cisaillement et sur les fluctuations de pression au loin
The unsteady flow over surface discontinuities produces high aerodynamic noise. The aim of this thesis is to study the aeroacoustics of two-dimensional rectangular cavities and to find strategies for noise reduction. Direct Numerical Simulation of the compressible Navier-Stokes equations is performed to investigate the influence of the initial condition on the oscillation modes in deep and shallow cavities. Results show that the deep cavity oscillates in shear layer regime at the second Rossiter mode regardless of the initial condition. On the other hand different initial conditions lead to a shear layer or wake mode in the shallow cavity case. A sensitivity analysis of the deep cavity is done by the use of adjoint methods. Local sinusoidal perturbations of x-momentum and density are applied to the adjoint equations. The results show a high sensitivity region to mass injection at the upstream corner. Therefore an actuator placed at the leading edge will modify the velocity fluctuations reaching the trailing edge and hence the pressure fluctuations in the far-field

Adjoint based optimisation has until now demonstrated a great promise for optimisation in aerodynamics due to its independence of the number of design variables. This is essential in large industrial applications, where hundreds of parameters might be needed so as to describe the geometry. Although the computational cost of the methodology is smaller than that of stochastic optimisation methods, the implementation and related program maintenance time and effort could be particularly high. The aim of the present is to contribute to the effort of redusing the cost above by examining whether programs using the adjoint methodology for optimisation can be automatically generated and maintained via Automatic Differentiation, while presenting comparable performance to hand derived adjoints. This could lead to accurate adjoint based optimisation codes, which would inherit any change or addition to the relative original Computational Fluid Dynamics code. Such a methodology is presented and all the different steps involved are detailed. It is found that although a considerable initial effort is required for preparation of the source code for differentiation, hand assembly of the sensitivity algorithms and scripting for the automation of the entire process, the target of this research program is achieved and fully automatically generated adjoint codes with comparable performance can be acquired. After applying the methodology to a number of aerodynamic shape optimisation examples, the logic is also extended to higher derivatives, which could also be included in the optimisation process for robust design.

This thesis describes the investigation and development of a novel CAD-based aerodynamic optimisation system, with the aim of allowing gradient-based optimisation of feature-based, parametric models within commercial CAD packages in timescales acceptable for industrial design processes. The process developed is based on linking parametric design velocities (geometric sensitivities computed from the CAD model representing the displacement of a point on the model boundary due to a perturbation of a CAD model parameter) with adjoint surface mesh sensitivities (which represent the derivative of a goal function with respect to surface mesh node position). A CAD-based design velocity computation method has been developed based on projection between discrete representations of perturbed geometries which can be linked to virtually any existing commercial CAD system. A key characteristic of the approach is that it can cope with the discontinuous changes in CAD model topology and face labelling that can occur under even small changes in CAD parameters. Use of the above approach allows computation of parametric sensitivities with respect to aerodynamic coefficients for native CAD parameters within feature-based commercial CAD modelling systems using adjoint data at a computational cost of just one adjoint analysis per objective function and one design velocity field evaluation per parameter. Gradient computation is demonstrated on test cases for an aerofoil model, a turbine blade model and a 3D wing model. Using these computed sensitivities enables the creation of a truly CAD-based aerodynamic optimisation system incorporating adjoint CFD data and using design velocities for computing geometric sensitivities and as input to a mesh deformation step. A prototype implementation of this system is presented and used to optimise a parametric CAD-based aerofoil model. In order to develop the approach further, future work should focus on resolving issues encountered when using design velocities for mesh deformation, extending the approach to more complex test cases, and potentially incorporating parametric effectiveness as a measure of the suitability of a given CAD parameterisation for optimisation purposes.

Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2011.
Cataloged from PDF version of thesis.
Includes bibliographical references (p. 75-79).
Over 10,000 premature mortalities per year globally are attributed to the exposure to particulate matter caused by aircraft emissions. Unlike previous studies that focus on the regional impacts from the aircraft emissions below 3,000 feet, this thesis studies the impact from emissions at all altitudes and across continents on increasing particulates in a receptor region, thereby increasing exposure. In addition to these intercontinental impacts, the thesis analyzes the temporal variations of sensitivities of the air quality and health, the proportion of the impacts attributable to different emission species, and the background emissions' influence on the impact of aircraft emissions. To quantify the impacts of aircraft emissions at various locations and times, this study uses the adjoint model of GEOS-Chem, a chemical transport model. The adjoint method efficiently computes sensitivities of a few objective functions, such as aggregated PM concentration and human exposure to PM concentration, with respect to many input parameters, i.e. emissions at different locations and times. Whereas emissions below 3,000 feet have mostly local impacts, cruise emissions from North America impair the air quality in Europe and Asia, and European cruise emissions affect Asia. Due to emissions entering Asia, the premature mortalities in Asia were approximately two to three times larger than the global mortalities caused by the Asian emissions. In contrast, North America observed only about one-ninth of the global premature mortalities caused by North American emissions because emissions get carried out of the region. This thesis calculates that most of the premature mortalities occured in Europe and Asia in 2006. Sensitivities to emissions also have seasonal and diurnal cycles. For example, ground level NOx emissions in the evening contribute to 50% more surface PM formation than the same emissions in the morning, and cruise level NOx emissions in early winter cause six times more PM concentration increase than the same emissions in spring. Aircraft NOx emissions cause 78% of PM from aviation emissions, and given the population exposure to PM concentration increase, NOx contributes 90% of the total impact. By showing the second-order sensitivities, this study finds that increases in background emissions of ammonia increase the impact of aircraft emissions on the air quality and increases in background NOx emissions decrease the impact. These results show the effectiveness of the adjoint model for analyzing the longterm sensitivities. Some of the analyses presented are practically only possible with the adjoint method. By regulating emissions at high sensitivities in time and region, calculated by the adjoint model, governments can design effective pollutant reduction policies.
by Jamin Koo.
S.M.

The convergence rates for the method of Weinstein and a variant method of Aronszajn known as "truncation including the remainder" are derived in terms of the containment gaps between exact and approximating subspaces, using analytical techniques that arise in part in the convergence analysis of finite element methods for differential eigenvalue problems. An example of a one dimensional Schrodinger operator with a potential is presented which arises in quantum mechanics. Examples using the recent eigenvector-free (EVF) method of Beattie and Goerisch are considered. Since the EVF method uses finite element trial functions as approximating vectors, it produces sparse and well-structured coefficient matrices. For these large-order sparse matrix eigenvalue problems, we adapt a spectral transformation Lanczos algorithm for finding a few wanted eigenvalues. For a few particular examples of vibration in beams and plates, convergence behavior is experimentally evaluated.
Ph. D.

The Community Multiscale Air Quality (CMAQ) system is the Environmental Protection Agency's main modeling tool for atmospheric pollution studies. CMAQ-ADJ, the adjoint model of CMAQ, offers new analysis capabilities such as receptor-oriented sensitivity analysis and chemical data assimilation. This thesis presents the construction, validation, and properties of new adjoint modules in CMAQ, and illustrates their use in sensitivity analyses and data assimilation experiments. The new module of discrete adjoint of advection is implemented with the aid of automatic differentiation tool (TAMC) and is fully validated by comparing the adjoint sensitivities with finite difference values. In addition, adjoint sensitivity with respect to boundary conditions and boundary condition scaling factors are developed and validated in CMAQ. To investigate numerically the impact of the continuous and discrete advection adjoints on data assimilation, various four dimensional variational (4D-Var) data assimilation experiments are carried out with the 1D advection PDE, and with CMAQ advection using synthetic and real observation data. The results show that optimization procedure gives better estimates of the reference initial condition and converges faster when using gradients computed by the continuous adjoint approach. This counter-intuitive result is explained using the nonlinearity properties of the piecewise parabolic method (the numerical discretization of advection in CMAQ). Data assimilation experiments are carried out using real observation data. The simulation domain encompasses Texas and the simulation period is August 30 to September 1, 2006. Data assimilation is used to improve both initial and boundary conditions. These experiments further validate the tools developed in this thesis.
Master of Science

The overall goals of this dissertation are to advance the field of chemical data assimilation, and to develop efficient computational tools that allow the atmospheric science community benefit from state of the art assimilation methodologies. Data assimilation is the procedure to combine data from observations with model predictions to obtain a more accurate representation of the state of the atmosphere. As models become more complex, determining the relationships between pollutants and their sources and sinks becomes computationally more challenging. The construction of an adjoint model ( capable of efficiently computing sensitivities of a few model outputs with respect to many input parameters ) is a difficult, labor intensive, and error prone task. This work develops adjoint systems for two of the most widely used chemical transport models: Harvardâ s GEOS-Chem global model and for Environmental Protection Agencyâ s regional CMAQ regional air quality model. Both GEOS-Chem and CMAQ adjoint models are now used by the atmospheric science community to perform sensitivity analysis and data assimilation studies. Despite the continuous increase in capabilities, models remain imperfect and models alone cannot provide accurate long term forecasts. Observations of the atmospheric composition are now routinely taken from sondes, ground stations, aircraft, and satellites, etc. This work develops three and four dimensional variational data assimilation capabilities for GEOS-Chem and CMAQ which allow to estimate chemical states that best fit the observed reality. Most data assimilation systems to date use diagonal approximations of the background covariance matrix which ignore error correlations and may lead to inaccurate estimates. This dissertation develops computationally efficient representations of covariance matrices that allow to capture spatial error correlations in data assimilation. Not all observations used in data assimilation are of equal importance. Erroneous and redundant observations not only affect the quality of an estimate but also add unnecessary computational expense to the assimilation system. This work proposes techniques to quantify the information content of observations used in assimilation; information-theoretic metrics are used. The four dimensional variational approach to data assimilation provides accurate estimates but requires an adjoint construction, and uses considerable computational resources. This work studies versions of the four dimensional variational methods (Quasi 4D-Var) that use approximate gradients and are less expensive to develop and run. Variational and Kalman filter approaches are both used in data assimilation, but their relative merits and disadvantages in the context of chemical data assimilation have not been assessed. This work provides a careful comparison on a chemical assimilation problem with real data sets. The assimilation experiments performed here demonstrate for the first time the benefit of using satellite data to improve estimates of tropospheric ozone.
Ph. D.

Numerical optimization methods have made significant progress over the last decades and play an important role in modern industrial design processes. In most cases, gradient-free algorithms are used, which only require the value of the objective function in each optimization step. These methods are robust and can be integrated into a standard design process at low implementation effort. However, in aerodynamic design problems using high-fidelity Computational Fluid Dynamics (CFD), the computational cost is high, especially when a large number of design parameters are used. Gradient-based methods, on the other hand, are particularly suited for problems involving large design spaces and generally converge to a local optimum in a few design cycles. However, the computational efficiency of these methods is mainly determined by the gradient calculation.This thesis presents the development of an efficient gradient-based optimization framework for the aerodynamic design of turbomachinery applications. In particular, the adjoint approach is used to evaluate the gradients of the objective function with respect to all design parameters at low computational cost. The present work covers the various components of the optimization framework, including the solution of the flow governing equations, adjoint-based sensitivity analysis, geometry parameterization, and mesh generation. A substantial part of the thesis describes the implementation and validation of those components. The flow solver is a Reynolds-Averaged Navier-Stokes code applicable to multiblock structured grids. The spatial discretization is realized with a Roe-type upwind scheme with a MUSCL extrapolation for second order spatial accuracy. Viscous fluxes are centrally discretized, and for the turbulence closure problem the Spalart-Allmaras and the Shear-Stress Transport (SST) models are used. The code uses an implicit multistage Runge-Kutta time-stepping scheme, accelerated by local time-stepping and geometric multigrid. The corresponding discrete adjoint solver uses the same time marching scheme as the flow solver and features similar performance characteristics in terms of runtime and memory footprint. The adjoint solver has been implemented primarily by hand with selective use of algorithmic differentiation (AD) to simplify the development. The geometry parameterization is based on B-Spline representations which has two main advantages: (a) the simple integration of geometric constraints for structural requirements, and (b) the connection to Computer-Aided Design (CAD) software for manufacturing. The whole optimization framework is driven by a Sequential Quadratic Programming (SQP) algorithm. The proposed framework has been successfully applied to optimize axial and radial turbines on multiple operating points subject to aerodynamic and geometric constraints. The different studies show the effectiveness of the developed method in terms of improved performances and computational cost. In particular, a comparative study shows that the proposed method is able to find optimized blade shapes at a computational time which is about one order of magnitude lower compared to a gradient-free optimization algorithm.
Doctorat en Sciences de l'ingénieur et technologie
info:eu-repo/semantics/nonPublished

Les avions rencontrent de nombreuses conditions d’opérations au cours de leurs vols, comme le nombre de Mach, l’altitude et l’angle d’attaque. Leur prise en compte durant la conception améliore la robustesse du système et finalement la consommation des flottes d’avions. L’optimisation de formes aérodynamiques contribue à la conception des avions, et repose sur l’automatisation de la génération de géométries ainsi que la simulation numérique de la physique du vol. La minimisation de la trainée des formes aérodynamiques doit prendre en compte de multiples conditions d’opération, étant donne que l’optimisation a une unique condition de vol mène a des formes dont la performance se dégrade fortement quand cette condition de vol est perturbée. De plus, la flexibilité structurelle déforme les ailes différemment selon la condition de vol, et doit donc être simulée lors de telles optimisations. Dans cette thèse, la minimisation de la consommation de carburant au cours d’une mission est formulée en problème d’optimisation. Une attention particulière est apportée au choix des conditions d’opérations à inclure dans le problème d’optimisation, étant donne que celles-ci ont un impact majeur sur la qualité des résultats obtenus, et que le cout de calcul est proportionnel à leur nombre. Un nouveau cadre théorique est proposé pour adresser cette question, offrant un point de vue original et surmontant des difficultés révélées par les méthodes a l’état-de-l’ art en matière de mise en place de problèmes d’optimisation multipoints. Un algorithme appelé Gradient Span Analysis (GSA), est proposé pour automatiser le choix des conditions d’opération. Il est base sur la réduction de dimension de l’espace vectoriel engendre par les gradients adjoints aux différentes conditions de vol. Des contributions de programmation a la chaine d’optimisation ont permis d’évaluer les méthodes aux optimisations du profil académique RAE2822 et de la configuration voilure-fuselage XRF-1, représentative des avions de transport modernes. Alors que les formes résultant d’optimisation mono-point présentent de fortes dégradations de performance hors du point de conception, les optimisations multipoints adéquatement formulées fournissent de bien meilleurs compromis. Il est finalement montre que les interactions fluide-structure ajoutent de nouveaux degrés de liberté, et ont un impact sur les optimisations en de multiples conditions de vol, ouvrant des perspectives en matière d’adaptation passive de forme
An aircraft encounters a wide range of operating conditions during its missions, i.e. flight altitude, Mach number and angle of attack, which consideration at the design phase enhances the system robustness and consequently the overall fleet consumption. Numerical optimization of aerodynamic shapes contributes to aircraft design, and relies on the automation of geometry generation and numerical simulations of the flight physics. Minimization of aerodynamic shapes drag must take into account multiple operating conditions, since optimization at a single operating condition leads to a strong degradation of performance when this operating condition varies. Besides, structural flexibility deforms the wings differently depending on the operating conditions, so has to be simulated during such optimizations. In the present thesis, the mission fuel consumption minimization is formulated as an optimization problem. The focus is made on the choice of operating conditions to be included in the optimization problem, since they have a major impact on the quality of the results, and the computational cost is proportional to their number. A new theoretical framework is proposed, overcoming and giving new insights on problematic situations revealed by state-of-the-art methods for multipoint optimization problem setup. An algorithm called Gradient Span Analysis is proposed to automate the choice of operating conditions. It is based on a reduction of dimension of the vector space spanned by adjoint gradients obtained at the different operating conditions. Programming contributions to the optimization chain enabled the evaluation of the new method on the optimizations of the academic RAE2822 airfoil, and the XRF-1 wing-body configuration, representative of a modern transport aircraft. While the shapes resulting of single-point optimizations present strong degradations of the performance in off-design conditions, adequately formulated multi-Machmulti- lift optimizations present much more interesting performance compromises. It is finally shown that fluid-structure interaction adds new degrees of freedom, and has consequences on multiple flight conditions optimizations, opening the perspective of passive shape adaptation

This thesis deals with non-linear non-quadratic optimal control problems in an autonomous system and a related iterative numerical method, the Kleinman-Newton method, for solving the problem. The thesis proves the local convergence of Kleinman-Newton method using the contraction mapping theorem and then describes how this Kleinman-Newton method may be used to numerically solve for the optimal control and the corresponding solution. In order to show the proof and the related numerical work, it is necessary to review some of earlier work in the beginning of Chapter 1 [Zhang], and to introduce the Kleinman-Newton method at the end of the chapter. In Chapter 2 we will demonstrate the proof. In Chapter 3 we will show the related numerical work and results.
Ph. D.

Two new analysis methods for solar seismology are developed. Called the continuous orthonormalization (CON) and adjoint methods, their use enables both solar eigenfrequencies and eigenfrequency sensitivities (partial derivatives with respect to solar model parameters) to be computed more accurately and efficiently than with existing methods. The CON method integrates an eighth-order nonlinear system of ordinary differential equations (ODEs) which defines the linear adiabatic nonradial oscillation modes of the Sun. (The Cowling approximation is not used.) All normal modes of oscillation are treated identically, regardless of their type (pressure, gravity or fundamental) or their predominant location inside the Sun. The adjoint method integrates a related eighth-order linear inhomogeneous system of ODEs. From the resultant solution, an eigenfrequency's partial derivatives with respect to an extensive set of solar model parameters may be computed simultaneously. Extensive numerical tests confirm the validity of the two new methods. Eigenfrequencies obtained via the CON method have seven significant digits and match within 1% the eigenfrequencies obtained via finite difference or mesh approaches. (Exact agreement is neither expected nor attainable because differently defined solar models are analyzed. The CON method analyzes models which are functionally specified on a continuum of radial points; the other methods analyze models defined on discrete sets of radial points.) Eigenfrequency sensitivities obtained via the adjoint method match within 2% the results obtained by explicitly perturbing the solar model parameters and recomputing the eigenfrequencies. The usefulness and power of the two new methods are demonstrated by applying them to the solution of an elementary solar inversion problem. A sample solar model's f-mode frequencies (obtained via the CON method) are iteratively driven into agreement with an observed set of f-mode frequencies. Adjoint sensitivity results are used to alter solar model parameters within hundreds of radial bins. The frequency movement is large, comparable to the frequency separation between adjacent degree f-modes. Model changes are also large; the density near the base of the convection zone is roughly doubled, while slightly further out it is halved.

Neutron radiation detectors are an integral part of the Department of Homeland Security (DHS) efforts to detect the illicit trafficking of radioactive or special nuclear materials into the U.S. In the past decade, the DHS has deployed a vast network of radiation detection systems at various key positions to prevent or to minimize the risk associated with the malevolent use of these materials. The greatest portion of this detection burden has been borne by systems equipped with 3He because of its highly desirable physical and nuclear properties. However, a dramatic increase in demand and dwindling supply, combined with a lack of oversight for the existing 3He stockpile has produced a critical shortage of this gas which has virtually eliminated its viability for detector applications. A number of research efforts have been undertaken to develop suitable 3He replacements; however, these studies have been solely targeted toward simple detection cases where the overall detection efficiency is the only concern. For these cases, an insertion of additional detectors or materials can produce reaction rates that are sufficient, because the neutron spectral response is essentially irrelevant. However, in applications such as safeguards, non-proliferation efforts, and material control and accountability programs (MC&A), a failure to use detectors that are spectrally matched to 3He can potentially produce dire consequences. This is because these more difficult detection scenarios are associated with fissile material assessments for 239Pu and other actinides and these analyses have almost universally been calibrated to an equivalent 3He response. In these instances, a “simple” detector or material addition approach is neither appropriate nor possible, due to influences resulting from the complex nature of neutron scattering in moderators, cross sections, gas pressure variations, geometries, and surrounding structural interference. These more challenging detection cases require a detailed computational transport analysis be performed for each specific application. A leveraged approach using adjoint transport computations that are validated by forward transport and Monte Carlo computations and laboratory measurements can address these more complex detection cases and this methodology was utilized in the execution of the research. The initial task was to establish the fidelity of a computational approach by executing radiation transport models for existing BF3 and 3He tubes and then comparing the modeling results to laboratory measurements made using these identical devices. Both tubes were 19.6 cm in height, 1-inch in diameter, and operated at 1 and 4 atm pressure respectively. The models were processed using a combination of forward Monte Carlo and forward and adjoint 3-D discrete ordinates (SN) transport methods. The computer codes MCNP5 and PENTRAN were used for all calculations of a nickel-shielded plutonium-beryllium (PuBe) source term that provided a neutron output spectra equivalent to that of weapons-grade plutonium (WGPu). Once the computational design approach was validated, the adjoint SN method was used to iteratively identify six distinct plug-in models that matched the neutron spectral response and reaction rate of a 1-inch diameter 3He tube with a length of 10 cm and operating at 4 atm pressure. The equivalent designs consist of large singular tubes and dual tubes containing BF3 gas, 10B linings, and/or 10B-loaded polyvinyl toluene (PVT). The reaction rate for each plug-in design was also verified using forward PENTRAN and MCNP5 calculations. In addition to the equivalent designs, the adjoint method also yielded various insights into neutron detector design that can lead to additional designs using a combination of different detector materials such as BF3/10B-loaded PVT, 10B-lined tubes/10B-loaded PVT, etc.

Computational fluid dynamics (CFD) simulations can provide tremendous insight into complex physical processes and are often faster and more cost-effective to execute than experiments. However, each CFD result inherently contains numerical errors that can significantly degrade the accuracy of a simulation. Discretization error is typically the largest contributor to the overall numerical error in a given simulation. Discretization error can be very difficult to estimate since the generation, transport, and diffusion of these errors is a highly nonlinear function of the computational grid and discretization scheme. As CFD is increasingly used in engineering design and analysis, it is imperative that CFD practitioners be able to accurately quantify discretization errors to minimize risk and improve the performance of engineering systems. In this work, improvements are made to the accuracy and efficiency of existing error estimation techniques. Discretization error is estimated by deriving and solving an error transport equation (ETE) for the local discretization error everywhere in the computational domain. Truncation error is shown to act as the local source for discretization error in numerical solutions. An equivalence between adjoint methods and ETE methods for functional error estimation is presented. This adjoint/ETE equivalence is exploited to efficiently obtain error estimates for multiple output functionals and to extend the higher-order properties of adjoint methods to ETE methods. Higher-order discretization error estimates are obtained when truncation error estimates are sufficiently accurate. Truncation error estimates are demonstrated to deteriorate on grids with a non-smooth variation in grid metrics (e.g., unstructured grids) regardless of how smooth the underlying exact solution may be. The loss of accuracy is shown to stem from noise in the discrete solution on the order of discretization error. When using conventional least-squares reconstruction techniques, this noise is exactly captured and introduces a lower-order error into the truncation error estimate. A novel reconstruction method based on polyharmonic smoothing splines is developed to smoothly reconstruct the discrete solution and improve the accuracy of error estimates. Furthermore, a method for iteratively improving discretization error estimates is devised. Efficiency and robustness considerations are discussed. Results are presented for several inviscid and viscous flow problems. To facilitate the study of discretization error estimation, a new, higher-order finite-volume solver is developed. A detailed description of the code base is provided along with a discussion of best practices for CFD code design.
Ph. D.
Computational fluid dynamics (CFD) is a branch of computational physics at the intersection of fluid mechanics and scientific computing in which the governing equations of fluid motion, such as the Euler and Navier-Stokes equations, are solved numerically on a computer. CFD is utilized in numerous fields including biomedical engineering, meteorology, oceanography, and aerospace engineering. CFD simulations can provide tremendous insight into physical processes and are often preferred over experiments because they can be performed more quickly, are typically more cost-effective, and can provide data in regions where it may be difficult to measure. While CFD can be an extremely powerful tool, CFD simulations are inherently subject to numerical errors. These errors, which are generated when the governing equations of fluid motion are solved on a computer, can have a significant impact on the accuracy of a CFD solution. If numerical errors are not accurately quantified, ill-informed decision-making can lead to poor system performance, increased risk of injury, or even system failure. In this work, research efforts are focused on numerical error estimation for the finite -volume method, arguably the most widely used numerical algorithm for solving CFD problems. The error estimation techniques provided herein target discretization error, the largest contributor to the overall numerical error in a given simulation. Discretization error can be very difficult to estimate since these errors are generated, convected, and diffused by the same physical processes embedded in the governing equations. In this work, improvements are made to the accuracy and efficiency of existing discretization error estimation techniques. Results are presented for several inviscid and viscous flow problems. To facilitate the study of these error estimators, a new, higher-order finite -volume solver is developed. A detailed description of the code base is provided along with a discussion of best practices for CFD code design.

Hydrodynamic vortex separators (HDVSs) are used in wastewater treatment to separate solids from wastewater. The aim of this research is to devise a CFD-based methodology that optimises their performance through modification of their design. A validation study is performed to assess whether OpenFOAM can be used to reliably model the flow of water in an HDVS. The results of the simulations are compared with experimental readings, showing a good fit when the appropriate boundary layer height and turbulence model are used. The continuous adjoint method is employed to derive the adjoint equations, associated with the drift flux equations used to model the flow of wastewater. They are specialised to the typical boundary conditions of ducted flows and are coded using OpenFOAM. An optimal design is found for boundary conditions, corresponding to typical values used in practice, and is shown to improve the performance of a simplified initial design by 40%. This optimal design is subsequently subjected to a different hydraulic loading rate and dispersed-phase volume fraction at the inlet, to assess the performance variation in these circumstances. Though the optimal design removes all the solids when the dispersed-phase fraction is reduced at the inlet, initial results suggest that the design is sensitive to hydraulic loading rate and further tests are recommended before drawing more explicit conclusions. This is the first time the adjoint drift flux equations have been derived. It is also the first time they have been coded and applied to an HDVS to optimise its performance. The methodology developed in this thesis could be applied to any device that separates solids from liquid or two immiscible liquids, in order to optimise its performance.

A deep scientific understanding of complex physical systems, such as the atmosphere, can be achieved neither by direct measurements nor by numerical simulations alone. Data assimilation is a rigorous procedure to fuse information from a priori knowledge of the system state, the physical laws governing the evolution of the system, and real measurements, all with associated error statistics. Data assimilation produces best (a posteriori) estimates of model states and parameter values, and results in considerably improved computer simulations. The acquisition and use of observations in data assimilation raises several important scientific questions related to optimal sensor network design, quantification of data impact, pruning redundant data, and identifying the most beneficial additional observations. These questions originate in operational data assimilation practice, and have started to attract considerable interest in the recent past. This dissertation advances the state of knowledge in four dimensional variational (4D-Var) - data assimilation by developing, implementing, and validating a novel computational framework for estimating observation impact and for optimizing sensor networks. The framework builds on the powerful methodologies of second-order adjoint modeling and the 4D-Var sensitivity equations. Efficient computational approaches for quantifying the observation impact include matrix free linear algebra algorithms and low-rank approximations of the sensitivities to observations. The sensor network configuration problem is formulated as a meta-optimization problem. Best values for parameters such as sensor location are obtained by optimizing a performance criterion, subject to the constraint posed by the 4D-Var optimization. Tractable computational solutions to this "optimization-constrained" optimization problem are provided. The results of this work can be directly applied to the deployment of intelligent sensors and adaptive observations, as well as to reducing the operating costs of measuring networks, while preserving their ability to capture the essential features of the system under consideration.
Ph. D.

Um desafio constante no projeto aerodinâmico de uma superfície é obter a forma geométrica que permite, baseado em uma determinada medida de mérito, o melhor desempenho possível. No contexto de projeto de aeronaves de transporte, o desempenho ótimo em cruzeiro é a principal meta do projetista. Nesse cenário, o uso da Dinâmica do Fluidos Computacional como não só uma ferramenta de análise mas também de síntese torna-se uma forma atrativa para melhorar o projeto de aeronaves que é uma atividade dispendiosa em termos de tempo e recursos financeiros. O método adotado para projeto aerodinâmico é baseado na teoria de controle ótimo. Essa abordagem para o problema de otimização aerodinâmica foi inicialmente proposta por Jameson (1997) e é chamada de método adjunto. Esse método apresenta uma grande diminuição de custo computacional se comparado com a abordagem de diferenças finitas para a otimização baseada em gradiente. Essa dissertação apresenta o método adjunto contínuo aplicado às equações de Euler. Tal método está inserido no contexto de um ciclo de projeto inverso aerodinâmico. Nesse ciclo, tanto o código computacional de solução das equações do escoamento quanto o código de solução das equações adjuntas foram desenvolvidos ao longo desse trabalho. Além disso, foi adotada uma metodologia de redução do gradiente da função de mérito em relação às variáveis de projeto. O algorítmo utilizado para a busca do mínimo da função de mérito é o steepest descent. Os binômios de Bernstein foram escolhidos para representar a geometria do aerofólio de acordo com a parametrização proposta por Kulfan e Bussoletti (2006). Apresenta-se um estudo dessa parametrização mostrando suas características relevantes para a otimização aerodinâmica. Os resultados apresentados estão divididos em dois grupos: validação do ciclo de projeto inverso e aplicações práticas. O primeiro grupo consiste em exercícios de projeto inverso nos quais são estabelecidas distribuições de pressão desejadas obtidas a partir de geometrias conhecidas, desta forma garante-se que tais distribuições são realizáveis. No segundo grupo, porém, as distribuições desejadas são propostas pelo projetista baseado em sua experiência e, portanto, não sendo garantida a realizabilidade dessas distribuições. Em ambos os grupos, incluem-se resultados nos regimes de escoamento transônico e subsônico incompressível.
A constant endeavor in aerodynamic design is to find the shape that yields optimum performance, according to some context-dependent measure of merit. In particular for transport aircrafts, an optimum cruise performance is usually the designers main goal. In this scenario the use of the Computational Fluid Dynamics (CFD) technique as not only an analysis tool but as a design tool becomes an attractive aid to the time and financial resource consuming activity that is aircraft design. The method adopted for aerodynamic design is based on optimal control theory. This approach to the design problem was first proposed by Jameson (1997) and it is called adjoint method. It shows a great computational cost advantage over the finite difference approach to gradient-based optimization. This dissertation presents an Euler adjoint method implemented in context of an inverse aerodynamic design loop. In this loop both the flow solver and the adjoint solver were developed during the course of this work and their formulation are presented. Further on, a gradient reduction methodology is used to obtain the gradient of the cost function with respect to the design variables. The method chosen to drive the cost function to its minimum is the steepest descent. Bernstein binomials were chosen to represent the airfoil geometry as proposed by Kulfan and Bussoletti (2006). A study of such geometric representation method is carried on showing its relevant properties for aerodynamic optimization. Results are presented in two groups: inverse design loop validation and practical application. The first group consists of inverse design exercises in which the target pressure distribution is from a known geometry, this way such distribution is guaranteed to be realizable. On the second group however, the target distribution is proposed based on the designers knowledge and its not necessarily realizable. In both groups the results include transonic and subsonic incompressible conditions.

Ao longo da última década o método adjunto tem sido consolidado como uma das mais versáteis e bem sucedidas ferramentas de otimização aerodinâmica e projeto inverso na Dinâmica dos Fluidos Computacional. Ele se tornou uma área de pesquisa por si só, criando uma grande variedade de aplicações e uma literatura prolífica. Entretanto, alguns aspectos relevantes do método permanecem ainda relativamente pouco explorados na literatura. Como é o caso das condições de contorno adjuntas e, mais especificamente, com respeito a fronteiras permeáveis. Esta dissertação discute detalhadamente uma nova forma de tratar o problema de contorno, que tem como objetivo assegurar que as equações adjuntas sejam bem-postas. O principal objetivo da otimização aerodinâmica consiste na tentativa de minimizar (ou maximizar) uma determinada medida de mérito. As aplicações de projeto inverso são desenvolvidas para escoamentos Euler 2-D ao redor de aerofólios, representados com a parametrização CST (Class-Shape function Transformation) proposta por Kulfan e Bussoletti (2006), em regime de vôo transônico e com domínio discretizado por malhas não-estruturadas de triângulos através de um ciclo de projeto, que utiliza o método steepest descent como algoritmo de busca da direção que minimiza (ou maximiza) a função de mérito. As equações adjuntas são derivadas na sua formulação contínua e suas condições de contorno são determinadas por equações diferenciais características adjuntas e relações de compatibilidade compatíveis com as variações realizáveis da física do escoamento. As variáveis adjuntas são, então, vistas como forças de vínculo generalizadas, que asseguram a realizabilidade de variações do escoamento.
Over the last decade the adjoint method has been consolidated as one of the most versatile and successful tools of aerodynamic optimization and inverse design in Computational Fluid Dynamics. It has become a research area of its own, spawning a large variety of applications and a prolific literature. Yet, some relevant aspects of the method remain relatively less explored in the literature. Such is the case with the adjoint boundary conditions and, more specifically, with regard to permeable boundaries. This dissertation discusses at length a novel approach to the boundary problem, which aims at ensuring the well-posedness of the adjoint equations. The main goal of aerodynamic optimization consists in attempting to minimize (or maximize) a certain mesure of merit. The inverse design applications are developed for 2-D Euler flows around airfoils, represented with the CST (Class-Shape function Transformation) parameterization proposed by Kulfan and Bussoletti (2006), in the transonic flight regime and domain discretized by triangle unstructured meshes in a design loop which makes use of the steepest descent method as search direction that minimizes (or maximizes) the mesure of merit. Adjoint equations are derived in the continuous formulation and their boundary conditions are determined by adjoint characteristic differential equations and compatibility relations. The latter are derived so as to be compatible with the realizable variations of physical quantities. The adjoint variables are seen as generalized constraint forces, which ensure the realizability of flow variations.

Dans cette thèse, nous nous sommes penchés d’un point de vue à la foisthéorique et pratique sur la conception d’algorithmes et detechniques d’ordonnancement adaptées aux architectures complexes dessuperordinateurs modernes. Nous nous sommes en particulier intéressésà l’utilisation mémoire et la gestion des communications desalgorithmes pour le calcul haute performance (HPC). Nous avonsexploité l’hétérogénéité des superordinateurs modernes pour améliorerles performances du calcul matriciel. Nous avons étudié lapossibilité d’alterner intelligemment des étapes de factorisation LU(plus rapide) et des étapes de factorisation QR (plus stablenumériquement mais plus deux fois plus coûteuses) pour résoudre unsystème linéaire dense. Nous avons amélioré les performances desystèmes d’exécution dynamique à l’aide de pré-calculs statiquesprenants en compte l’ensemble du graphe de tâches de la factorisationCholesky ainsi que l’hétérogénéité de l’architecture. Nous noussommes intéressés à la complexité du problème d’ordonnancement degraphes de tâches utilisant de gros fichiers d’entrée et de sortiesur une architecture hétérogène avec deux types de ressources,utilisant chacune une mémoire spécifique. Nous avons conçu denombreuses heuristiques en temps polynomial pour la résolution deproblèmes généraux que l’on avait prouvés NP-complet aupréalable. Enfin, nous avons conçu des algorithmes optimaux pourordonnancer un graphe de différentiation automatique sur uneplateforme avec deux types de mémoire : une mémoire gratuite maislimitée et une mémoire coûteuse mais illimitée
Throughout this thesis, we have designed memory-aware algorithms and scheduling techniques suitedfor modern memory architectures. We have shown special interest in improving the performance ofmatrix computations on multiple levels. At a high level, we have introduced new numerical algorithmsfor solving linear systems on large distributed platforms. Most of the time, these linear solvers rely onruntime systems to handle resources allocation and data management. We also focused on improving thedynamic schedulers embedded in these runtime systems by adding static information to their decisionprocess. We proposed new memory-aware dynamic heuristics to schedule workflows, that could beimplemented in such runtime systems.Altogether, we have dealt with multiple state-of-the-art factorization algorithms used to solve linearsystems, like the LU, QR and Cholesky factorizations. We targeted different platforms ranging frommulticore processors to distributed memory clusters, and worked with several reference runtime systemstailored for these architectures, such as P A RSEC and StarPU. On a theoretical side, we took specialcare of modelling convoluted hierarchical memory architectures. We have classified the problems thatare arising when dealing with these storage platforms. We have designed many efficient polynomial-timeheuristics on general problems that had been shown NP-complete beforehand

Strides in modern computational fluid dynamics and leaps in high-power computing have led to unprecedented capabilities for handling large aerodynamic problem. In particular, the emergence of adjoint design methods has been a break-through in the field of aerodynamic shape optimization. It enables expensive, high-dimensional optimization problems to be tackled efficiently using gradient-based methods in CFD; a task that was previously inconceivable. However, adjoint design methods are intended for gradient-based optimization; the curse of dimensionality is still very much alive when it comes to design space exploration, where gradient-free methods cannot be avoided. This research describes a novel approach for reducing dimensionality in large, computationally expensive design problems to a point where gradient-free methods become possible. This is done using an innovative application of Principal Component Analysis (PCA), where the latter is applied to the gradient distribution of the objective function; something that had not been done before. This yields a linear transformation that maps a high-dimensional problem onto an equivalent low-dimensional subspace. None of the original variables are discarded; they are simply linearly combined into a new set of variables that are fewer in number. The method is tested on a range of analytical functions, a two-dimensional staggered airfoil test problem and a three-dimensional Over-Wing Nacelle (OWN) integration problem. In all cases, the method performed as expected and was found to be cost effective, requiring only a relatively small number of samples to achieve large dimensionality reduction.

Dans cette thèse, nous nous intéressons à trois problèmes issus de l'informatique théorique, à savoir le placement de formes rectangulaires dans un conteneur (OPP), la coloration dite "forte" d'arêtes des graphes et les codes identifiants dans les graphes. L'OPP consiste à décider si un ensemble d'items rectangulaires peut être placé sans chevauchement dans un conteneur rectangulaire et sans dépassement des bords de celui-ci. Une contrainte supplémentaire est prise en compte, à savoir l'interdiction de rotation des items. Le problème est NP-difficile même dans le cas où le conteneur et les formes sont des carrés. Nous présentons un algorithme de résolution efficace basé sur une caractérisation du problème par des graphes d'intervalles, proposée par Fekete et Schepers. L'algorithme est exact et utilise les MPQ-arbres - structures de données qui encodent ces graphes de manière compacte tout en capturant leurs propriétés remarquables. Nous montrons les résultats expérimentaux de notre approche en les comparant aux performances d'autres algorithmes existants. L'étude de la coloration forte d'arêtes et des codes identifiants porte sur les aspects structurels et de calculabilité de ces deux problèmes. Dans le cas de la coloration forte d'arêtes nous nous intéressons plus particulièrement aux familles des graphes planaires et des graphes subcubiques. Nous montrons des bornes optimales pour l'indice chromatique fort des graphes subcubiques en fonction du degré moyen maximum et montrons que tout graphe planaire subcubique sans cycles induits de longueur 4 et 5 est coloriable avec neuf couleurs. Enfin nous confirmons la difficulté du problème de décision associé, en prouvant qu'il est NP-complet dans des sous-classes restreintes des graphes planaires subcubiques. La troisième partie de la thèse est consacrée aux codes identifiants. Nous proposons une caractérisation des graphes identifiables dont la cardinalité du code identifiant minimum est n − 1, où n est l'ordre du graphe. Nous étudions la classe des graphes adjoints et nous prouvons des bornes inférieures et supérieures serrées pour la cardinalité du code identifiant minimum dans cette classe. Finalement, nous montrons qu'il existe un algorithme linéaire de calcul de ce paramètre dans la classe des graphes adjoints L(G) où G a une largeur arborescente bornée par une constante. En revanche nous nous apercevons que le problème est NP-complet dans des sous-classes très restreintes des graphes parfaits.

Cette thèse s’intéresse aux formalismes qui permettent de représenter mathématiquement non seulement le sens de phrases indépendantes mais aussi de textes entiers, en incluant les liens de sens que les différentes phrases qui les composent entretiennent les unes avec les autres. Ces liens de sens — les relations discursives — sont divers ; nous trouvons notamment des relations temporelles, causales et contrastives. Nous ne nous posons pas seulement la question du sens et de sa représentation, mais aussi celle de la détermination algorithmique de cette représentation à partir des séquences de mots qui composent les énoncés. Nous nous situons donc à l’interface de trois traditions : l’analyse discursive, la sémantique formelle et la linguistique computationnelle.La plupart de travaux formels portant sur le discours ne prêtent que peu d’attention aux verbes de dire (affirmer, dire, etc.) et d’attitude propositionnelle (penser, croire, etc.). Tous ces verbes, que nous regroupons sous l’abréviation « VAP », ont en commun d’exprimer l’attitude ou la position d’une personne sur une proposition donnée. Ils sont utilisés fréquemment et introduisent de nombreuses subtilités échappant de fait aux théories actuelles. Cette thèse a pour objectif principal de mettre à jour les principes d’une grammaire formelle compatible avec l’analyse du discours et prenant en compte les VAP. Nous commençons donc par présenter de nombreuses données linguistiques illustrant les interactions entre VAP et relations discursives.Il est souvent considéré que les connecteurs adverbiaux (ensuite, par exemple, etc.) sont anaphoriques. Cependant, nous pouvons nous demander si, en pratique, un système de linguistique computationnelle ne peut pas gérer cette catégorie particulière d’anaphore comme s’il s’agissait d’un type de dépendance structurelle, étendant d’une certaine manière la syntaxe au-delà de la phrase. C’est ce que nous nous proposons de faire à l’aide du formalisme D-STAG. Une telle approche, bien qu’ayant un certain nombre de propriétés intéressantes dans le cadre de l’analyse automatique du discours, fait peser un poids important sur la syntaxe, et nous discutons alors les difficultés qu’elle soulève.Cela nous amène à développer une approche anaphorique, c’est-à-dire dans laquelle les arguments des relations discursives ne sont plus déterminés uniquement par la structure grammaticale des énoncés. Ce sont les mêmes outils conceptuels que nous utilisons pour rendre compte de l’anaphoricité des connecteurs adverbiaux, des structures discursives non-arborées (observées avec tout type de connecteurs), mais aussi de l’usage évidentiel des VAP.Cependant, si nous employons la notion d’anaphore, nous voulons l’intégrer explicitement dans le formalisme grammatical, en spécifiant quand sont exécutées les résolutions d’anaphore et avec quelles informations en entrée. Cela est possible avec la sémantique par continuation, que nous utilisons en combinaison à la sémantique événementielle. Les événements sont souvent invoqués pour exprimer la sémantique des relations notamment causales ou temporelles, mais posent aussi un certain nombre de questions, liées aux schémas logiques d’inférence qu’autorisent les énoncés linguistiques ainsi qu’à la présence de la négation pour exprimer les arguments des relations discursives. Nous avançons plusieurs pistes pour y répondre et étudions plus en détail le cas de la négation.Nous revenons ainsi sur les difficultés que pose la négation linguistique pour une analyse sémantique événementielle, qui concernent autant l’interface syntaxe-sémantique que le niveau purement sémantique. Nous montrons que ces difficultés ont pour origine l’analyse standard de la négation, qui traite phrases positives et phrases négatives de manière fondamentalement différente. Rejetant cette vue, nous présentons une formalisation nouvelle de la notion d’événement négatif, adaptée à l’analyse de divers phénomènes linguistiques
This thesis focuses on the formalisms that make it possible to mathematically represent not only the meaning of independent sentences, but also whole texts, including the meaning relations that link sentences together. These links — the discourse relations — include temporal, causal and contrastive relations. Not only are we interested in meaning and its representation, but also on the algorithmic process of how this representation is computed using the sequence of words that constitute the text. We thus find ourselves at a point where three disciplines intersect: discourse analysis, formal semantics and computational linguistics.Most formal work on discourse pay little attention to reporting verbs (say, tell, etc.) and attitude verbs (think, believe, etc.). These verbs, henceforth ‘AVs’, all express the attitude or stance of one person on a given proposition. They are used frequently and introduce many subtleties that are not addressed in current theories. The main objective of this thesis is to shed light on the principles of a formal grammar that is compatible with discourse analysis that takes AVs into account. We therefore start by presenting a set of linguistic data illustrating the interactions between AVs and discourse relations.Adverbial connectives (then, for example, etc.) are usually considered anaphoric. One might wonder, however, whether, in practice, a computational linguistic system cannot deal with this particular category of anaphora as a kind of structural dependency, meaning that syntax is somehow extended above the sentence level. This is what we try to achieve using the D-STAG formalism. While it has properties that are relevant for automatic discourse analysis, such an approach imposes quite the burden on syntax. We therefore discuss the difficulties that this approach poses.Consequently, we develop an anaphor based approach, in which the arguments of discourse relations are not determined solely by the grammatical structures of the utterances. We use the same conceptual tools to account for the anaphoricity of adverbial connectives, the shape of non-tree discourse structures (observed for all type of connectives) but also the evidential use of AVs.If, however, we look at the notion of anaphora, our aim is to have it explicitly integrated into grammatical formalism. In particular, we set out to specify when anaphora resolution is performed and on which input. This is made possible by continuation semantics, which we use in conjunction with event semantics. Events have often been appealed to in order to describe the semantics of causal and temporal relations. Nevertheless, events raise a number of questions related to the possibility of some inference patterns that are observed, in addition to the presence of negation in the arguments of discourse relations. We suggest a number of potential answers and study the case of negation in more detail.We therefore review the issues facing event semantics when dealing with negation. Such issues concern both the syntax-semantics interface and the purely semantics level. We argue that these difficulties originate from the standard analysis of negation, which interprets positive and negative sentences is an essentially different fashion. Rejecting this view, we propose a novel formalisation of negative events that is relevant to the analysis of various linguistic phenomena

Advances in numerical optimization have raised the possibility that efficient and novel aircraft configurations may be ``discovered'' by an algorithm. To begin exploring this possibility, a fast and robust set of tools for aerodynamic shape optimization is developed. Parameterization and mesh-movement are integrated to accommodate large changes in the geometry. This integrated approach uses a coarse B-spline control grid to represent the geometry and move the computational mesh; consequently, the mesh-movement algorithm is two to three orders faster than a node-based linear elasticity approach, without compromising mesh quality. Aerodynamic analysis is performed using a flow solver for the Euler equations. The governing equations are discretized using summation-by-parts finite-difference operators and simultaneous approximation terms, which permit nonsmooth mesh continuity at block interfaces. The discretization results in a set of nonlinear algebraic equations, which are solved using an efficient parallel Newton-Krylov-Schur strategy. A gradient-based optimization algorithm is adopted. The gradient is evaluated using adjoint variables for the flow and mesh equations in a sequential approach. The flow adjoint equations are solved using a novel variant of the Krylov solver GCROT. This variant of GCROT is flexible to take advantage of non-stationary preconditioners and is shown to outperform restarted flexible GMRES. The aerodynamic optimizer is applied to several studies of induced-drag minimization. An elliptical lift distribution is recovered by varying spanwise twist, thereby validating the algorithm. Planform optimization based on the Euler equations produces a nonelliptical lift distribution, in contrast with the predictions of lifting-line theory. A study of spanwise vertical shape optimization confirms that a winglet-up configuration is more efficient than a winglet-down configuration. A split-tip geometry is used to explore nonlinear wake-wing interactions: the optimized split-tip demonstrates a significant reduction in induced drag relative to a single-tip wing. Finally, the optimal spanwise loading for a box-wing configuration is investigated.

The use of steady-state aerodynamic optimization methods in the computational fluid dynamic (CFD) community is fairly well established. In particular, the use of adjoint methods has proven to be very beneficial because their cost is independent of the number of design variables. The application of numerical optimization to airframe-generated noise, however, has not received as much attention, but with the significant quieting of modern engines, airframe noise now competes with engine noise. Optimal control techniques for unsteady flows are needed in order to be able to reduce airframe-generated noise. In this thesis, a general framework is formulated to calculate the gradient of a cost function in a nonlinear unsteady flow environment via the discrete adjoint method. The unsteady optimization algorithm developed in this work utilizes a Newton-Krylov approach since the gradient-based optimizer uses the quasi-Newton method BFGS, Newton's method is applied to the nonlinear flow problem, GMRES is used to solve the resulting linear problem inexactly, and last but not least the linear adjoint problem is solved using Bi-CGSTAB. The flow is governed by the unsteady two-dimensional compressible Navier-Stokes equations in conjunction with a one-equation turbulence model, which are discretized using structured grids and a finite difference approach. The effectiveness of the unsteady optimization algorithm is demonstrated by applying it to several problems of interest including shocktubes, pulses in converging-diverging nozzles, rotating cylinders, transonic buffeting, and an unsteady trailing-edge flow. In order to address radiated far-field noise, an acoustic wave propagation program based on the Ffowcs Williams and Hawkings (FW-H) formulation is implemented and validated. The general framework is then used to derive the adjoint equations for a novel hybrid URANS/FW-H optimization algorithm in order to be able to optimize the shape of airfoils based on their calculated far-field pressure fluctuations. Validation and application results for this novel hybrid URANS/FW-H optimization algorithm show that it is possible to optimize the shape of an airfoil in an unsteady flow environment to minimize its radiated far-field noise while maintaining good aerodynamic performance.