In this dissertation, we develop multiscale finite element methods and uncertainty quantification technique for Richards' equation, a mathematical model to describe fluid flow in unsaturated porous media. Both coarse-level and fine-level numerical computation techniques are presented. To develop an accurate coarse-scale numerical method, we need to construct an effective multiscale map that is able to capture the multiscale features of the large-scale solution without resolving the small scale details. With a careful choice of the coarse spaces for multiscale finite element methods, we can significantly reduce errors. We introduce several methods to construct coarse spaces for multiscale finite element methods. A coarse space based on local spectral problems is also presented. The construction of coarse spaces begins with an initial choice of multiscale basis functions supported in coarse regions. These basis functions are complemented using weighted local spectral eigenfunctions. These newly constructed basis functions can capture the small scale features of the solution within a coarse-grid block and give us an accurate coarse-scale solution. However, it is expensive to compute the local basis functions for each parameter value for a nonlinear equation. To overcome this difficulty, local reduced basis method is discussed, which provides smaller dimension spaces with which to compute the basis functions. Robust solution techniques for Richards' equation at a fine scale are discussed. We construct iterative solvers for Richards' equation, whose number of iterations is independent of the contrast. We employ two-level domain decomposition pre-conditioners to solve linear systems arising in approximation of problems with high contrast. We show that, by using the local spectral coarse space for the preconditioners, the number of iterations for these solvers is independent of the physical properties of the media. Several numerical experiments are given to support the theoretical results. Last, we present numerical methods for uncertainty quantification applications for Richards' equation. Numerical methods combined with stochastic solution techniques are proposed to sample conductivities of porous media given in integrated data. Our proposed algorithm is based on upscaling techniques and the Markov chain Monte Carlo method. Sampling results are presented to prove the efficiency and accuracy of our algorithm.

A trend in parallel computer architecture is that systems with a large shared memory are becoming more and more popular. A shared memory system can be either a uniform memory architecture (UMA) or a cache coherent non-uniform memory architecture (cc-NUMA). In the present thesis, the performance of parallel PDE solvers on cc-NUMA computers is studied. In particular, we consider the shared namespace programming model, represented by OpenMP. Since the main memory is physically, or geographically distributed over several multi-processor nodes, the latency for local memory accesses is smaller than for remote accesses. Therefore, the geographical locality of the data becomes important. The focus of the present thesis is to study multithreaded PDE solvers on cc-NUMA systems, in particular their memory access pattern with respect to geographical locality. The questions posed are: (1) How large is the influence on performance of the non-uniformity of the memory system? (2) How should a program be written in order to reduce this influence? (3) Is it possible to introduce optimizations in the computer system for this purpose? The main conclusion is that geographical locality is important for performance on cc-NUMA systems. This is shown experimentally for a broad range of PDE solvers as well as theoretically using a model involving characteristics of computer systems and applications. Geographical locality can be achieved through migration directives that are inserted by the programmer or — possibly in the future — automatically by the compiler. On some systems, it can also be accomplished by means of transparent, hardware initiated migration and replication. However, a necessary condition that must be fulfilled if migration is to be effective is that the memory access pattern must not be "speckled", i.e. as few threads as possible shall make accesses to each memory page. We also conclude that OpenMP is competitive with MPI on cc-NUMA systems if care is taken to get a favourable data distribution.

Les problèmes de tournées de véhicules sont des problèmes d’optimisation combinatoire épineux avec des enjeux économiques et environnementaux importants au sein de la chaîne logistique. Le problème fondamental est de desservir des clients avec un ensemble de véhicules de façon à minimiser la distance totale parcourue. En pratique, il y a une grande variété d’objectifs et de contraintes additionnelles, liées à la législation et à la diversité des domaines d’applications. Ces problèmes de tournées sont très fréquents pour de nombreuses industries et la conception d’approches de résolution génériques est devenue une question de recherche importante.Cette thèse porte sur la conception et le développement d’un nouveau moteur de résolution pour les logiciels de tournées de véhicules proposés par l’entreprise GEOCONCEPT. Le solveur mis au point s’appuie sur la programmation par contraintes (PPC) pour améliorer la flexibilité (prise en compte de contraintes additionnelles), la déclarativité et la maintenance qui sont les limites des solveurs actuels de GEOCONCEPT fondés sur la recherche locale.Dans un premier temps, un modèle de graphe est établi pour la représentation unifiée des données et de nombreuses contraintes métiers. La résolution s’effectue par des approches à base de voisinage large disponibles dans les solveurs de PPC modernes. On peut ainsi traiter des instances de très grandes tailles efficacement tout en conservant une approche déclarative pour exprimer une classe très large de problèmes de tournées de véhicules. Dans un second temps, des modèles PPC s’appuyant sur des représentations redondantes du problème sont proposés afin de renforcer le filtrage. Nous nous intéressons en détails aux mécanismes de filtrage c’est-à-dire aux processus d’élimination des valeurs infaisables ou sous-optimales dans les domaines des variables. Ces algorithmes permettent de simplifier rapidement le problème et de fournir des bornes inférieures afin d’évaluer la qualité des solutions obtenues. Les bornes inférieures sont obtenues en résolvant des relaxations du plus célèbre des problèmes de la Recherche Opérationnelle : le problème du voyageur de commerce (TSP). Ce problème est le cœur de la contrainte globale weightedcircuit permettant de modéliser les problèmes de tournées en PPC. Nous proposons de nouveaux mécanismes de filtrage pour cette contrainte s’appuyant sur trois relaxations du TSP. Ces relaxations sont comparées sur les plans théorique et expérimental. L’originalité de ce travail est de proposer un nouvel algorithme de filtrage permettant de raisonner à la fois sur les successeurs directs d’un client et sur sa position dans la tournée. Ces raisonnements sont particulièrement utiles en présence de contraintes de fenêtres de temps, très communes dans les problèmes industriels.Le nouveau moteur de résolution offre d’excellentes performances sur des problèmes académiques et industriels tout en proposant des bornes inférieures informatives à des problèmes industriels réels. / Vehicle routing problems are very hard combinatorial optimization problems with significant economic and environmental challenges. The fundamental problem is to visit a set of customers with a given fleet of vehicles in order to minimize the total distance travelled. Moreover, these problems arise with a wide variety of objectives and additional constraints, related to the legislation and the diversity of industrial sectors. They are very common for many industries and the design of generic solvers has become an important research issue.This thesis focuses on the design and implementation of a new solver for the vehicle routing services offered by the company GEOCONCEPT. The proposed solver is based on constraint programming (CP) to improve flexibility (ability to take additional constraints into account), declarative modelling and maintenance, which are the limits of current GEOCONCEPT solvers based on local search.Firstly, a graph model is established to provide a common representation of the input-data and the numerous business constraints. The resolution is performed using large neighbourhood search methods available in modern CP solvers. It is thus possible to deal with large instances efficiently with a declarative approach where a broad class of vehicle routing problems can be modelled. Secondly, several CP models based on redundant views of the problem are proposed to strengthen the filtering. We focus on the filtering mechanisms for removing infeasible or suboptimal values in the domains of the variables. These algorithms can quickly simplify the problem and derive lower bounds to assert the quality of the solutions found. The lower bounds are obtained by solving relaxations of the most famous problem in Operations Research: the Traveling Salesman Problem (TSP). This problem is the core of the global constraint WEIGTEHDCIRCUIT for modelling routing problems in CP. We propose new filtering algorithms for this constraint based on three relaxations of the TSP. These relaxations are compared theoretically and experimentally. The originality of this work is to propose a new filtering algorithm for reasoning on the direct successors of a customer as well as his position in the tour. It is particularly useful in the presence of time window constraints, which are very common in industrial problems.The new solver shows excellent performance on academic and industrial problems and can compute informative lower bounds for real-life problems.

This dissertation shows that the bounded property verification of hardware Register Transfer Level (RTL) designs can be efficiently performed by precise abstract interpretation of a software representation of the RTL. The first part of this dissertation presents a novel framework for RTL verification using native software analyzers. To this end, we first present a translation of the hardware circuit expressed in Verilog RTL into the software in C called the software netlist. We then present the application of native software analyzers based on SAT/SMT-based decision procedures as well as abstraction-based techniques such as abstract interpretation for the formal verification of the software netlist design generated from the hardware RTL. In particular, we show that the path-based symbolic execution techniques, commonly used for automatic test case generation in system softwares, are also effective for proving bounded safety as well as detecting bugs in the software netlist designs. Furthermore, by means of experiments, we show that abstract interpretation techniques, commonly used for static program analysis, can also be used for bounded as well as unbounded safety property verification of the software netlist designs. However, the analysis using abstract interpretation shows high degree of imprecision on our benchmarks which is handled by manually guiding the analysis with various trace partitioning directives. The second part of this dissertation presents a new theoretical framework and a practical instantiation for automatically refining the precision of abstract interpretation using Conflict Driven Clause Learning (CDCL)-style analysis. The theoretical contribution is the abstract interpretation framework that generalizes CDCL to precise safety verification for automatic transformer refinement called Abstract Conflict Driven Learning for Safety (ACDLS). The practical contribution instantiates ACDLS over a template polyhedra abstract domain for bounded safety verification of the software netlist designs. We experimentally show that ACDLS is more efficient than a SAT-based analysis as well as sufficiently more precise than a commercial abstract interpreter.

This thesis considers three separate but connected problems regarding energy networks: the load flow problem, the optimal power flow problem, and the islanding problem. All three problems are non-convex non linear problems, and so have the potential of returning local solutions. The goal of this thesis is to find solution methods to each of these problems that will minimize the chances of returning a local solution. The thesis first considers the load ow problem and looks into a novel approach to solving load flows, the Holomorphic Embedding Load Flow Method (HELM). The current literature does not provide any HELM models that can accurately handle general power networks containing PV and PQ buses of realistic sizes. This thesis expands upon previous work to present models of HELM capable of solving general networks efficiently, with computational results for the standard IEEE test cases provided for comparison. The thesis next considers the optimal power flow problem, and creates a framework for a load flow-based OPF solver. The OPF solver is designed with incorporating HELM as the load flow solver in mind, and is tested on IEEE test cases to compare it with other available OPF solvers. The OPF solvers are also tested with modified test cases known to have local solutions to show how a LF-OPF solver using HELM is more likely to find the global optimal solution than the other available OPF solvers. The thesis finally investigates solving a full AC-islanding problem, which can be considered as an extension of the transmission switching problem, using a standard MINLP solver and comparing the results to solutions obtained from approximations to the AC problem. Analysing in detail the results of the AC-islanding problem, alterations are made to the standard MINLP solver to allow better results to be obtained, all the while considering the trade-off between results and elapsed time.

Multi-dimensional digital signals have become an intertwined part of day to day life, from digital images and videos used to capture and share life experiences, to more powerful scene representations such as light field images, which open the gate to previously challenging tasks, such as post capture refocusing or eliminating visible occlusions from a scene. This dissertation delves into the world of multi-dimensional signal processing and introduces a tool of particular use for gradient based solutions of well-known signal processing problems. Specifically, a technique to reconstruct a signal from a given gradient data set is developed in the case of two dimensional (2-D), three dimensional (3-D) and four dimensional (4-D) digital signals. The reconstruction technique is multiresolution in nature, and begins by using the given gradient to generate a multi-dimensional Haar wavelet decomposition of the signals of interest, and then reconstructs the signal by Haar wavelet synthesis, performed on successive resolution levels. The challenges in developing this technique are non-trivial and are brought about by the applications at hand. For example, in video content replacement, the gradient data from which a video sequence needs to be reconstructed is a combination of gradient values that belong to different video sequences. In most cases, such operations disrupt the conservative nature of the gradient data set. The effects of the non-conservative nature of the newly generated gradient data set are attenuated by using an iterative Poisson solver at each resolution level during the reconstruction. A second and more important challenge is brought about by the increase in signal dimensionality. In a previous approach, an intermediate extended signal with symmetric region of support is obtained, and the signal of interest is extracted from it. This approach is reasonable in 2-D, but becomes less appealing as the signal dimensionality increases. To avoid generating data that is then discarded, a new approach is proposed, in which signal extension is no longer performed. Instead, different procedures are suggested to generate a non-symmetric Haar wavelet decomposition of the signals of interest. In the case of 2-D and 3-D signals, ways to obtain this decomposition exactly from the given gradient data and the average value of the signal are proposed. In addition, ways to approximate a subset of decomposition coefficients are introduced and the visual consequences of such approximations are studied in the special case of 2-D digital images. Several ways to approximate the same subset of decomposition coefficients are developed in the special case of 4-D light field images. Experiments run on various 2-D, 3-D and 4-D test signals are included to provide an insight on the performance of the reconstruction technique. The value of the multi-dimensional reconstruction technique is then demonstrated by including it in a number of signal processing applications. First, an efficient algorithm is developed with the purpose of combining information from the gradient of a set of 2-D images with different regions in focus or different exposure times, with the purpose of generating an all-in-focus image or revealing details that were lost due to improper exposure setting. Moving on to 3-D signal processing applications, two video editing problems are studied and gradient based solutions are presented. In the first one, the objective is to seamlessly place content from one video sequence in another, while in the second one, to combine elements from two video sequences and generate a transparency effect. Lastly, a gradient based technique for editing 4-D scene representations (light fields) is presented, as well as a technique to combine information from two light fields with the purpose of generating a light field with more details of the imaged scene. All these applications show that the developed technique is a reliable tool for gradient domain based solutions of signal processing problems. / Graduate

O Problema de Balanceamento e Sequenciamento de Linhas de Montagem com Tempos de Setup dependentes da Sequência (SUALBSP, em inglês Setup Assembly Line Balancing and Scheduling) envolve a atribuição de tarefas às estações de trabalho e o sequenciamento destas tarefas dentro da estação à qual foi atribuída. Trabalhos anteriores propuseram soluções heurísticas com excelentes resultados, porém o uso de métodos exatos, por meio de algum resolvedor de Programação Inteira Mista, tem apresentado desempenhos decepcionantes, pois contém um subproblema NP-hard em todas as estações. Enquanto o modelo de Scholl, Boysen e Fliedner (2013) minimiza prioritariamente o número de estações, o modelo proposto neste trabalho parte da premissa que este é um dado definido. A partir de uma estimativa inicial de número de estações, processa-se o modelo com o objetivo de distribuir as tarefas e minimizar o tempo total de estação, que é o segundo objetivo do modelo original. Se este processamento for infactível, incrementa-se o número de estações em uma unidade e reprocessa-se o modelo até se encontrar um resultado factível. Experimentos computacionais em 101 instâncias de dados confirmam o bom desempenho da abordagem proposta, sem qualquer prejuízo à qualidade da solução. Portanto, os resultados apresentados demonstram que há espaço para estudos futuros a partir do uso de matheurísticas. / The Setup Assembly Line Balancing and Scheduling Problem (SUALBSP) involves the assigning of tasks to workstations and the sequencing of these tasks within the station to which they are assigned. Previous work has proposed heuristic solutions with excellent results, but the use of exact methods, by some Mixed-Integer Programming solver, has shown disappointing performance, because it contains an NP-hard sub problems in every station. While the model proposed by Scholl, Boysen and Fliedner (2013) primarily minimizes the numbers of stations, our model assumes it as a parameter. From an initial estimate of the number of stations, we process the model for allocating tasks and minimize station times, which is the second objective of the original model. If this processing is infeasible, we increase the number of stations by one unit and we reprocess the model to find a feasible result. Computational experiments in 101 instances of data set confirm the good performance of the proposed approach, without harming the quality of the solution. Therefore, the results show that there are opportunities for future studies based on the use of matheuristics.

Master of Science / Mechanical and Nuclear Engineering / Hitesh Bindra / This thesis extends the application of Lattice Boltzmann Methods (LBM) to radiation transport problems in thermal sciences and nuclear engineering. LBM is used to solve the linear Boltzmann transport equation through discretization into Lattice Boltzmann Equations (LBE). The application of weighted summations for the scattering integral as set forth by Bindra and Patil are used in this work. Simplicity and localized discretization are the main advantages of using LBM with fixed lattice configurations for radiation transport problems. Coupled solutions to radiation transport and material energy transport are obtained using a single framework LBM. The resulting radiation field of a one dimensional participating and conducting media are in very good agreement with benchmark results using spherical harmonics, the P₁ method. Grid convergence studies were performed for this coupled conduction-radiation problem and results are found to be first-order accurate in space. In two dimensions, angular discretization for LBM is extended to higher resolution schemes such as D₂Q₈ and a generic formulation is adopted to derive the weights for Radiation Transport Equations (RTEs). Radiation transport in a two dimensional media is solved with LBM and the results are compared to those obtained from the commercial software COMSOL, which uses the Discrete Ordinates Method (DOM) with different angular resolution schemes. Results obtained from different lattice Boltzmann configurations such as D₂Q₄ and D₂Q₈ are compared with DOM and are found to be in good agreement. The verified LBM based radiation transport models are extended for their application into coupled multi-physics problems. A porous radiative burner is modeled as a homogeneous media with an analytical velocity field. Coupling is performed between the convection-diffusion energy transport equation with the analytical velocity field. Results show that radiative transport heats the participating media prior to its entering into the combustion chamber. The limitations of homogeneous models led to the development of a fully coupled LBM multi-physics model for a heterogeneous porous media. This multi-physics code solves three physics: fluid flow, conduction-convection and radiation transport in a single framework. The LBE models in one dimension are applied to solve one-group and two-group eigenvalue problems in bare and reflected slab geometries. The results are compared with existing criticality benchmark reports for different problems. It is found that results agree with benchmark reports for thick slabs (>4 mfp) but they tend to disagree when the critical slab dimensions are less than 3 mfp. The reason for this disagreement can be attributed to having only two angular directions in the one dimensional problems.

abstract: Moore's law has been the most important driving force for the tremendous progress of semiconductor industry. With time the transistors which form the fundamental building block of any integrated circuit have been shrinking in size leading to smaller and faster electronic devices.As the devices scale down thermal effects and the short channel effects become the important deciding factors in determining transistor architecture.SOI (Silicon on Insulator) devices have been excellent alternative to planar MOSFET for ultimate CMOS scaling since they mitigate short channel effects. Hence as a part of thesis we tried to study the benefits of the SOI technology especially for lower technology nodes when the channel thickness reduces down to sub 10nm regime. This work tries to explore the effects of structural confinement due to reduced channel thickness on the electrostatic behavior of DG SOI MOSFET. DG SOI MOSFET form the Qfinfet which is an alternative to existing Finfet structure. Qfinfet was proposed and patented by the Finscale Inc for sub 10nm technology nodes. As part of MS Thesis we developed electrostatic simulator for DG SOI devices by implementing the self consistent full band Schrodinger Poisson solver. We used the Empirical Pseudopotential method in conjunction with supercell approach to solve the Schrodinger Equation. EPM was chosen because it has few empirical parameters which give us good accuracy for experimental results. Also EPM is computationally less expensive as compared to the atomistic methods like DFT(Density functional theory) and NEGF (Non-equilibrium Green's function). In our workwe considered two crystallographic orientations of Si,namely [100] and [110]. / Dissertation/Thesis / Masters Thesis Electrical Engineering 2016

O Problema de Balanceamento e Sequenciamento de Linhas de Montagem com Tempos de Setup dependentes da Sequência (SUALBSP, em inglês Setup Assembly Line Balancing and Scheduling) envolve a atribuição de tarefas às estações de trabalho e o sequenciamento destas tarefas dentro da estação à qual foi atribuída. Trabalhos anteriores propuseram soluções heurísticas com excelentes resultados, porém o uso de métodos exatos, por meio de algum resolvedor de Programação Inteira Mista, tem apresentado desempenhos decepcionantes, pois contém um subproblema NP-hard em todas as estações. Enquanto o modelo de Scholl, Boysen e Fliedner (2013) minimiza prioritariamente o número de estações, o modelo proposto neste trabalho parte da premissa que este é um dado definido. A partir de uma estimativa inicial de número de estações, processa-se o modelo com o objetivo de distribuir as tarefas e minimizar o tempo total de estação, que é o segundo objetivo do modelo original. Se este processamento for infactível, incrementa-se o número de estações em uma unidade e reprocessa-se o modelo até se encontrar um resultado factível. Experimentos computacionais em 101 instâncias de dados confirmam o bom desempenho da abordagem proposta, sem qualquer prejuízo à qualidade da solução. Portanto, os resultados apresentados demonstram que há espaço para estudos futuros a partir do uso de matheurísticas. / The Setup Assembly Line Balancing and Scheduling Problem (SUALBSP) involves the assigning of tasks to workstations and the sequencing of these tasks within the station to which they are assigned. Previous work has proposed heuristic solutions with excellent results, but the use of exact methods, by some Mixed-Integer Programming solver, has shown disappointing performance, because it contains an NP-hard sub problems in every station. While the model proposed by Scholl, Boysen and Fliedner (2013) primarily minimizes the numbers of stations, our model assumes it as a parameter. From an initial estimate of the number of stations, we process the model for allocating tasks and minimize station times, which is the second objective of the original model. If this processing is infeasible, we increase the number of stations by one unit and we reprocess the model to find a feasible result. Computational experiments in 101 instances of data set confirm the good performance of the proposed approach, without harming the quality of the solution. Therefore, the results show that there are opportunities for future studies based on the use of matheuristics.