Optimal polygonal L1 linearization and fast interpolation of nonlinear systems

The analysis of complex nonlinear systems is often carried out using simpler piecewise linear representations of them. A principled and practical technique is proposed to linearize and evaluate arbitrary continuous nonlinear functions using polygonal (continuous piecewise linear) models under the L1 norm. A thorough error analysis is developed to guide an optimal design of two kinds of polygonal approximations in the asymptotic case of a large budget of evaluation subintervals N. The method allows the user to obtain the level of linearization (N) for a target approximation error and vice versa. It is suitable for, but not limited to, an efficient implementation in modern Graphics Processing Units (GPUs), allowing real-time performance of computationally demanding applications. The quality and efficiency of the technique has been measured in detail on two nonlinear functions that are widely used in many areas of scientific computing and are expensive to evaluate.

Automated wordlength optimization framework for multi-source statistical interval-based analysis of nonlinear systems with control-flow structures

El uso de aritmética de punto fijo es una opción de diseño muy extendida en sistemas con fuertes restricciones de área, consumo o rendimiento. Para producir implementaciones donde los costes se minimicen sin impactar negativamente en la precisión de los resultados debemos llevar a cabo una asignación cuidadosa de anchuras de palabra. Encontrar la combinación óptima de anchuras de palabra en coma fija para un sistema dado es un problema combinatorio NP-hard al que los diseñadores dedican entre el 25 y el 50 % del ciclo de diseño. Las plataformas hardware reconfigurables, como son las FPGAs, también se benefician de las ventajas que ofrece la aritmética de coma fija, ya que éstas compensan las frecuencias de reloj más bajas y el uso más ineficiente del hardware que hacen estas plataformas respecto a los ASICs. A medida que las FPGAs se popularizan para su uso en computación científica los diseños aumentan de tamaño y complejidad hasta llegar al punto en que no pueden ser manejados eficientemente por las técnicas actuales de modelado de señal y ruido de cuantificación y de optimización de anchura de palabra. En esta Tesis Doctoral exploramos distintos aspectos del problema de la cuantificación y presentamos nuevas metodologías para cada uno de ellos: Las técnicas basadas en extensiones de intervalos han permitido obtener modelos de propagación de señal y ruido de cuantificación muy precisos en sistemas con operaciones no lineales. Nosotros llevamos esta aproximación un paso más allá introduciendo elementos de Multi-Element Generalized Polynomial Chaos (ME-gPC) y combinándolos con una técnica moderna basada en Modified Affine Arithmetic (MAA) estadístico para así modelar sistemas que contienen estructuras de control de flujo. Nuestra metodología genera los distintos caminos de ejecución automáticamente, determina las regiones del dominio de entrada que ejercitarán cada uno de ellos y extrae los momentos estadísticos del sistema a partir de dichas soluciones parciales. Utilizamos esta técnica para estimar tanto el rango dinámico como el ruido de redondeo en sistemas con las ya mencionadas estructuras de control de flujo y mostramos la precisión de nuestra aproximación, que en determinados casos de uso con operadores no lineales llega a tener tan solo una desviación del 0.04% con respecto a los valores de referencia obtenidos mediante simulación. Un inconveniente conocido de las técnicas basadas en extensiones de intervalos es la explosión combinacional de términos a medida que el tamaño de los sistemas a estudiar crece, lo cual conlleva problemas de escalabilidad. Para afrontar este problema presen tamos una técnica de inyección de ruidos agrupados que hace grupos con las señales del sistema, introduce las fuentes de ruido para cada uno de los grupos por separado y finalmente combina los resultados de cada uno de ellos. De esta forma, el número de fuentes de ruido queda controlado en cada momento y, debido a ello, la explosión combinatoria se minimiza. También presentamos un algoritmo de particionado multi-vía destinado a minimizar la desviación de los resultados a causa de la pérdida de correlación entre términos de ruido con el objetivo de mantener los resultados tan precisos como sea posible. La presente Tesis Doctoral también aborda el desarrollo de metodologías de optimización de anchura de palabra basadas en simulaciones de Monte-Cario que se ejecuten en tiempos razonables. Para ello presentamos dos nuevas técnicas que exploran la reducción del tiempo de ejecución desde distintos ángulos: En primer lugar, el método interpolativo aplica un interpolador sencillo pero preciso para estimar la sensibilidad de cada señal, y que es usado después durante la etapa de optimización. En segundo lugar, el método incremental gira en torno al hecho de que, aunque es estrictamente necesario mantener un intervalo de confianza dado para los resultados finales de nuestra búsqueda, podemos emplear niveles de confianza más relajados, lo cual deriva en un menor número de pruebas por simulación, en las etapas iniciales de la búsqueda, cuando todavía estamos lejos de las soluciones optimizadas. Mediante estas dos aproximaciones demostramos que podemos acelerar el tiempo de ejecución de los algoritmos clásicos de búsqueda voraz en factores de hasta x240 para problemas de tamaño pequeño/mediano. Finalmente, este libro presenta HOPLITE, una infraestructura de cuantificación automatizada, flexible y modular que incluye la implementación de las técnicas anteriores y se proporciona de forma pública. Su objetivo es ofrecer a desabolladores e investigadores un entorno común para prototipar y verificar nuevas metodologías de cuantificación de forma sencilla. Describimos el flujo de trabajo, justificamos las decisiones de diseño tomadas, explicamos su API pública y hacemos una demostración paso a paso de su funcionamiento. Además mostramos, a través de un ejemplo sencillo, la forma en que conectar nuevas extensiones a la herramienta con las interfaces ya existentes para poder así expandir y mejorar las capacidades de HOPLITE. ABSTRACT Using fixed-point arithmetic is one of the most common design choices for systems where area, power or throughput are heavily constrained. In order to produce implementations where the cost is minimized without negatively impacting the accuracy of the results, a careful assignment of word-lengths is required. The problem of finding the optimal combination of fixed-point word-lengths for a given system is a combinatorial NP-hard problem to which developers devote between 25 and 50% of the design-cycle time. Reconfigurable hardware platforms such as FPGAs also benefit of the advantages of fixed-point arithmetic, as it compensates for the slower clock frequencies and less efficient area utilization of the hardware platform with respect to ASICs. As FPGAs become commonly used for scientific computation, designs constantly grow larger and more complex, up to the point where they cannot be handled efficiently by current signal and quantization noise modelling and word-length optimization methodologies. In this Ph.D. Thesis we explore different aspects of the quantization problem and we present new methodologies for each of them: The techniques based on extensions of intervals have allowed to obtain accurate models of the signal and quantization noise propagation in systems with non-linear operations. We take this approach a step further by introducing elements of MultiElement Generalized Polynomial Chaos (ME-gPC) and combining them with an stateof- the-art Statistical Modified Affine Arithmetic (MAA) based methodology in order to model systems that contain control-flow structures. Our methodology produces the different execution paths automatically, determines the regions of the input domain that will exercise them, and extracts the system statistical moments from the partial results. We use this technique to estimate both the dynamic range and the round-off noise in systems with the aforementioned control-flow structures. We show the good accuracy of our approach, which in some case studies with non-linear operators shows a 0.04 % deviation respect to the simulation-based reference values. A known drawback of the techniques based on extensions of intervals is the combinatorial explosion of terms as the size of the targeted systems grows, which leads to scalability problems. To address this issue we present a clustered noise injection technique that groups the signals in the system, introduces the noise terms in each group independently and then combines the results at the end. In this way, the number of noise sources in the system at a given time is controlled and, because of this, the combinato rial explosion is minimized. We also present a multi-way partitioning algorithm aimed at minimizing the deviation of the results due to the loss of correlation between noise terms, in order to keep the results as accurate as possible. This Ph.D. Thesis also covers the development of methodologies for word-length optimization based on Monte-Carlo simulations in reasonable times. We do so by presenting two novel techniques that explore the reduction of the execution times approaching the problem in two different ways: First, the interpolative method applies a simple but precise interpolator to estimate the sensitivity of each signal, which is later used to guide the optimization effort. Second, the incremental method revolves on the fact that, although we strictly need to guarantee a certain confidence level in the simulations for the final results of the optimization process, we can do it with more relaxed levels, which in turn implies using a considerably smaller amount of samples, in the initial stages of the process, when we are still far from the optimized solution. Through these two approaches we demonstrate that the execution time of classical greedy techniques can be accelerated by factors of up to ×240 for small/medium sized problems. Finally, this book introduces HOPLITE, an automated, flexible and modular framework for quantization that includes the implementation of the previous techniques and is provided for public access. The aim is to offer a common ground for developers and researches for prototyping and verifying new techniques for system modelling and word-length optimization easily. We describe its work flow, justifying the taken design decisions, explain its public API and we do a step-by-step demonstration of its execution. We also show, through an example, the way new extensions to the flow should be connected to the existing interfaces in order to expand and improve the capabilities of HOPLITE.

Compensation of biased excitation effects for MLS-based nonlinear systems' identification

MLS-based identification of nonlinear systems is largely affected by deviations in the excitation signal amenable to the combined effect of DC-offset and an arbitrary gain. These induce orthogonality loss in the MLS filter bank output, thus invalidating the underlying identification construction. In this paper we present a correction algorithm to derive the corrected Volterra kernels from the biased estimations provided by the standard MLS-based procedure.

New methods for the estimation of Takagi-Sugeno model based extended Kalman filter and its applications to optimal control for nonlinear systems

This paper describes new approaches to improve the local and global approximation (matching) and modeling capability of Takagi–Sugeno (T-S) fuzzy model. The main aim is obtaining high function approximation accuracy and fast convergence. The main problem encountered is that T-S identification method cannot be applied when the membership functions are overlapped by pairs. This restricts the application of the T-S method because this type of membership function has been widely used during the last 2 decades in the stability, controller design of fuzzy systems and is popular in industrial control applications. The approach developed here can be considered as a generalized version of T-S identification method with optimized performance in approximating nonlinear functions. We propose a noniterative method through weighting of parameters approach and an iterative algorithm by applying the extended Kalman filter, based on the same idea of parameters’ weighting. We show that the Kalman filter is an effective tool in the identification of T-S fuzzy model. A fuzzy controller based linear quadratic regulator is proposed in order to show the effectiveness of the estimation method developed here in control applications. An illustrative example of an inverted pendulum is chosen to evaluate the robustness and remarkable performance of the proposed method locally and globally in comparison with the original T-S model. Simulation results indicate the potential, simplicity, and generality of the algorithm. An illustrative example is chosen to evaluate the robustness. In this paper, we prove that these algorithms converge very fast, thereby making them very practical to use.

A new approach to fuzzy estimation of Takagi-Sugeno model and its applications to optimal control for nonlinear systems

An efficient approach is presented to improve the local and global approximation and modelling capability of Takagi-Sugeno (T-S) fuzzy model. The main aim is obtaining high function approximation accuracy. The main problem is that T-S identification method cannot be applied when the membership functions are overlapped by pairs. This restricts the use of the T-S method because this type of membership function has been widely used during the last two decades in the stability, controller design and are popular in industrial control applications. The approach developed here can be considered as a generalized version of T-S method with optimized performance in approximating nonlinear functions. A simple approach with few computational effort, based on the well known parameters' weighting method is suggested for tuning T-S parameters to improve the choice of the performance index and minimize it. A global fuzzy controller (FC) based Linear Quadratic Regulator (LQR) is proposed in order to show the effectiveness of the estimation method developed here in control applications. Illustrative examples of an inverted pendulum and Van der Pol system are chosen to evaluate the robustness and remarkable performance of the proposed method and the high accuracy obtained in approximating nonlinear and unstable systems locally and globally in comparison with the original T-S model. Simulation results indicate the potential, simplicity and generality of the algorithm.

Benchmarking for stability evaluation of computer systems

In this paper we propose a new benchmark to drive making decisions in maintenance of computer systems. This benchmark is made from load average sample data. The main goal is to improve reliability and performance of a set of devices or components. In particular, the stability of the system is measured in terms of variability of the load. A forecast of the behavior of this stability is also proposal as part of the reporting benchmark. At the final stage, a more stable system is obtained and its global reliability and performance can be then evaluated by means of appropriate specifications.

On the application of meshfree methods to the nonlinear dynamics of multibody systems

Esta tesis propone una completa formulación termo-mecánica para la simulación no-lineal de mecanismos flexibles basada en métodos libres de malla. El enfoque se basa en tres pilares principales: la formulación de Lagrangiano total para medios continuos, la discretización de Bubnov-Galerkin, y las funciones de forma libres de malla. Los métodos sin malla se caracterizan por la definición de un conjunto de funciones de forma en dominios solapados, junto con una malla de integración de las ecuaciones discretas de balance. Dos tipos de funciones de forma se han seleccionado como representación de las familias interpolantes (Funciones de Base Radial) y aproximantes (Mínimos Cuadrados Móviles). Su formulación se ha adaptado haciendo sus parámetros compatibles, y su ausencia de conectividad predefinida se ha aprovechado para interconectar múltiples dominios de manera automática, permitiendo el uso de mallas de fondo no conformes. Se propone una formulación generalizada de restricciones, juntas y contactos, válida para sólidos rígidos y flexibles, siendo estos últimos discretizados mediante elementos finitos (MEF) o libres de malla. La mayor ventaja de este enfoque reside en que independiza completamente el dominio con respecto de las uniones y acciones externas a cada sólido, permitiendo su definición incluso fuera del contorno. Al mismo tiempo, también se minimiza el número de ecuaciones de restricción necesarias para la definición de uniones realistas. Las diversas validaciones, ejemplos y comparaciones detalladas muestran como el enfoque propuesto es genérico y extensible a un gran número de sistemas. En concreto, las comparaciones con el MEF indican una importante reducción del error para igual número de nodos, tanto en simulaciones mecánicas, como térmicas y termo-mecánicas acopladas. A igualdad de error, la eficiencia numérica de los métodos libres de malla es mayor que la del MEF cuanto más grosera es la discretización. Finalmente, la formulación se aplica a un problema de diseño real sobre el mantenimiento de estructuras masivas en el interior de un reactor de fusión, demostrando su viabilidad en análisis de problemas reales, y a su vez mostrando su potencial para su uso en simulación en tiempo real de sistemas no-lineales. A new complete formulation is proposed for the simulation of nonlinear dynamic of multibody systems with thermo-mechanical behaviour. The approach is founded in three main pillars: total Lagrangian formulation, Bubnov-Galerkin discretization, and meshfree shape functions. Meshfree methods are characterized by the definition of a set of shape functions in overlapping domains, and a background grid for integration of the Galerkin discrete equations. Two different types of shape functions have been chosen as representatives of interpolation (Radial Basis Functions), and approximation (Moving Least Squares) families. Their formulation has been adapted to use compatible parameters, and their lack of predefined connectivity is used to interconnect different domains seamlessly, allowing the use of non-conforming meshes. A generalized formulation for constraints, joints, and contacts is proposed, which is valid for rigid and flexible solids, being the later discretized using either finite elements (FEM) or meshfree methods. The greatest advantage of this approach is that makes the domain completely independent of the external links and actions, allowing to even define them outside of the boundary. At the same time, the number of constraint equations needed for defining realistic joints is minimized. Validation, examples, and benchmarks are provided for the proposed formulation, demonstrating that the approach is generic and extensible to further problems. Comparisons with FEM show a much lower error for the same number of nodes, both for mechanical and thermal analyses. The numerical efficiency is also better when coarse discretizations are used. A final demonstration to a real problem for handling massive structures inside of a fusion reactor is presented. It demonstrates that the application of meshfree methods is feasible and can provide an advantage towards the definition of nonlinear real-time simulation models.

Computation of nonlinear streaky structures in boundary layer flow

En esta tesis se integran numéricamente las ecuaciones reducidas de Navier Stokes (RNS), que describen el flujo en una capa límite tridimensional que presenta también una escala característica espacial corta en el sentido transversal. La formulación RNS se usa para el cálculo de “streaks” no lineales de amplitud finita, y los resultados conseguidos coinciden con los existentes en la literatura, obtenidos típicamente utilizando simulación numérica directa (DNS) o nonlinear parabolized stability equations (PSE). El cálculo de los “streaks” integrando las RNS es mucho menos costoso que usando DNS, y no presenta los problemas de estabilidad que aparecen en la formulación PSE cuando la amplitud del “streak” deja de ser pequeña. El código de integración RNS se utiliza también para el cálculo de los “streaks” que aparecen de manera natural en el borde de ataque de una placa plana en ausencia de perturbaciones en la corriente uniforme exterior. Los resultados existentes hasta ahora calculaban estos “streaks” únicamente en el límite lineal (amplitud pequeña), y en esta tesis se lleva a cabo el cálculo de los mismos en el régimen completamente no lineal (amplitud finita). En la segunda parte de la tesis se generaliza el código RNS para incluir la posibilidad de tener una placa no plana, con curvatura en el sentido transversal que varía lentamente en el sentido de la corriente. Esto se consigue aplicando un cambio de coordenadas, que transforma el dominio físico en uno rectangular. La formulación RNS se integra también expresada en las correspondientes coordenadas curvilíneas. Este código generalizado RNS se utiliza finalmente para estudiar el flujo de capa límite sobre una placa con surcos que varían lentamente en el sentido de la corriente, y es usado para simular el flujo sobre surcos que crecen en tal sentido. Abstract In this thesis, the reduced Navier Stokes (RNS) equations are numerically integrated. This formulation describes the flow in a three-dimensional boundary layer that also presents a short characteristic space scale in the spanwise direction. RNS equations are used to calculate nonlinear finite amplitude “streaks”, and the results agree with those reported in the literature, typically obtained using direct numerical simulation (DNS) or nonlinear parabolized stability equations (PSE). “Streaks” simulations through the RNS integration are much cheaper than using DNS, and avoid stability problems that appear in the PSE when the amplitude of the “streak” is not small. The RNS integration code is also used to calculate the “streaks” that naturally emerge at the leading edge of a flat plate boundary layer in the absence of any free stream perturbations. Up to now, the existing results for these “streaks” have been only calculated in the linear limit (small amplitude), and in this thesis their calculation is carried out in the fully nonlinear regime (finite amplitude). In the second part of the thesis, the RNS code is generalized to include the possibility of having a non-flat plate, curved in the spanwise direction and slowly varying in the streamwise direction. This is achieved by applying a change of coordinates, which transforms the physical domain into a rectangular one. The RNS formulation expressed in the corresponding curvilinear coordinates is also numerically integrated. This generalized RNS code is finally used to study the boundary layer flow over a plate with grooves which vary slowly in the streamwise direction; and this code is used to simulate the flow over grooves that grow in the streamwise direction.

Power system stability of a small sized isolated network supplied by a combined wind-pumped storage generation system: a case study in the Canary Islands

Massive integration of renewable energy sources in electrical power systems of remote islands is a subject of current interest. The increasing cost of fossil fuels, transport costs to isolated sites and environmental concerns constitute a serious drawback to the use of conventional fossil fuel plants. In a weak electrical grid, as it is typical on an island, if a large amount of conventional generation is substituted by renewable energy sources, power system safety and stability can be compromised, in the case of large grid disturbances. In this work, a model for transient stability analysis of an isolated electrical grid exclusively fed from a combination of renewable energy sources has been studied. This new generation model will be installed in El Hierro Island, in Spain. Additionally, an operation strategy to coordinate the generation units (wind, hydro) is also established. Attention is given to the assessment of inertial energy and reactive current to guarantee power system stability against large disturbances. The effectiveness of the proposed strategy is shown by means of simulation results.

Resilience analysis of networked systems-of-systems based on structural and dynamic interdependencies

Critical infrastructures support everyday activities in modern societies, facilitating the exchange of services and quantities of various nature. Their functioning is the result of the integration of diverse technologies, systems and organizations into a complex network of interconnections. Benefits from networking are accompanied by new threats and risks. In particular, because of the increased interdependency, disturbances and failures may propagate and render unstable the whole infrastructure network. This paper presents a methodology of resilience analysis of networked systems of systems. Resilience generalizes the concept of stability of a system around a state of equilibrium, with respect to a disturbance and its ability of preventing, resisting and recovery. The methodology provides a tool for the analysis of off-equilibrium conditions that may occur in a single system and propagate through the network of dependencies. The analysis is conducted in two stages. The first stage of the analysis is qualitative. It identifies the resilience scenarios, i.e. the sequence of events, triggered by an initial disturbance, which include failures and the system response. The second stage is quantitative. The most critical scenarios can be simulated, for the desired parameter settings, in order to check if they are successfully handled, i.e recovered to nominal conditions, or they end into the network failure. The proposed methodology aims at providing an effective support to resilience-informed design.

Coherent excitation of nonlinear oscillators

Coherently driven, dissipative nonlinear oscillators,(driving kept permanently in phase with the oscillators response) are proposed as systems with interesting dynamics. Results for simple, preliminary examples, which do not show chaotic behavior, are briefly discussed.

Hybrid analysis of nonlinear circuits: DAE models with indices zero and one

We extend in this paper some previous results concerning the differential-algebraic index of hybrid models of electrical and electronic circuits. Specifically, we present a comprehensive index characterization which holds without passivity requirements, in contrast to previous approaches, and which applies to nonlinear circuits composed of uncoupled, one-port devices. The index conditions, which are stated in terms of the forest structure of certain digraph minors, do not depend on the specific tree chosen in the formulation of the hybrid equations. Additionally, we show how to include memristors in hybrid circuit models; in this direction, we extend the index analysis to circuits including active memristors, which have been recently used in the design of nonlinear oscillators and chaotic circuits. We also discuss the extension of these results to circuits with controlled sources, making our framework of interest in the analysis of circuits with transistors, amplifiers, and other multiterminal devices.

Systematic Method to Assess Small-Signal Stability of DC-Distributed Power-System-Architecture

The objective of this paper is to present a simplified method to analyze small-signal stability of a power system and provide performance metrics for stability assessment of a given power-system-architecture. The stability margins are stated utilizing a concept of maximum peak criteria (MPC), derived from the behavior of an impedance-based sensitivity function that provides a single number to state the robustness of the stability of a well-defined minor-loop gain. For each minor-loop gain, defined at every system interface, the robustness of the stability is provided as a maximum value of the corresponding sensitivity function. Typically power systems comprise of various interfaces and, therefore, in order to compare different architecture solutions in terms of stability, a single number providing an overall measure of the whole system stability is required. The selected figure of merit is geometric average of each maximum peak value within the system, combined with the worst case value of system interfaces.