An optimization method for conceptual design in engineering systems based on high order singular value decomposition

Se presenta un nuevo método de diseño conceptual en Ingeniería Aeronáutica basado el uso de modelos reducidos, también llamados modelos sustitutos (‘surrogates’). Los ingredientes de la función objetivo se calculan para cada indiviudo mediante la utilización de modelos sustitutos asociados a las distintas disciplinas técnicas que se construyen mediante definiciones de descomposición en valores singulares de alto orden (HOSVD) e interpolaciones unidimensionales. Estos modelos sustitutos se obtienen a partir de un número limitado de cálculos CFD. Los modelos sustitutos pueden combinarse, bien con un método de optimización global de tipo algoritmo genético, o con un método local de tipo gradiente. El método resultate es flexible a la par que mucho más eficiente, computacionalmente hablando, que los modelos convencionales basados en el cálculo directo de la función objetivo, especialmente si aparecen un gran número de parámetros de diseño y/o de modelado. El método se ilustra considerando una versión simplificada del diseño conceptual de un avión. Abstract An optimization method for conceptual design in Aeronautics is presented that is based on the use of surrogate models. The various ingredients in the target function are calculated for each individual using surrogates of the associated technical disciplines that are constructed via high order singular value decomposition and one dimensional interpolation. These surrogates result from a limited number of CFD calculated snapshots. The surrogates are combined with an optimization method, which can be either a global optimization method such as a genetic algorithm or a local optimization method, such as a gradient-like method. The resulting method is both flexible and much more computationally efficient than the conventional method based on direct calculation of the target function, especially if a large number of free design parameters and/or tunablemodeling parameters are present. The method is illustrated considering a simplified version of the conceptual design of an aircraft empennage.

Evaluación de obras de conservación de suelos en el Distrito de Coixtlahuaca (Oaxaca, México) y bases para actuaciones futuras.

En el Distrito de Coixtlahuaca (Estado de Oaxaca, México) desde antiguo se han realizado obras y prácticas de conservación de suelos que intentaran paliar su degradación como consecuencia de la sobreexplotación de las actividades humanas, como el pastoreo, sistemas de cultivo como la roza, tumba y quema o la obtención de leña; a lo que se une la propia la vulnerabilidad natural de sus recursos naturales y las complicadas condiciones climáticas y orográficas. Estos factores han acabado con graves pérdidas de suelo por erosión hídrica en el centro y sur del Distrito, dificultando o impidiendo el normal desarrollo de las actividades humanas más básicas, como la agricultura o el abastecimiento de agua, o las funciones propias del ecosistema, y derivando en otros de índole socioeconómica como la marginalidad o la emigración hacia los EE. UU. y otros Estados del país. Las obras de conservación de suelos en ladera son medidas de amplia difusión en el ámbito conservacionista y de lucha contra la erosión; y han sido objeto de numerosos Programas de Gobierno, sobre todo entre 1966 y 1974. Sin embargo, la eficacia nunca ha sido comprobada para dichas tecnologías ni para el Distrito de Coixtlahuaca, con lo que los esfuerzos retomados en la actualidad continúan la inercia de las obras de conservación realizadas en el pasado, a pesar de haber sido el centro de encendidos debates. La evaluación de las obras de conservación de suelos, objeto de este estudio, analiza su eficacia, sus beneficios en relación al coste, y sus repercusiones socioeconómicas, culturales y ambientales; para lo que se ha estudiado la influencia de las obras sobre los procesos erosivos y la erosionabilidad del suelo, e integrado los distintos puntos de vista de los grupos afectados. Ello ha permitido extraer conclusiones aplicables a las que se están ejecutando actualmente, y la posibilidad de optimizar los recursos económicos empleados desde el Gobierno, la Reserva de la Biosfera a la que pertenece parte del Distrito u otras instituciones y ONGs locales; así como los recursos humanos que con tanto esfuerzo aportan los propios habitantes. Junto a las mejoras que se proponen, se hace necesario reseñar los medios que faciliten la realización de las obras de conservación de suelos, no sólo en su financiación, sino también aquellos que permitan activar los mecanismos de cambio en una sociedad en la que ha renacido una incipiente voluntad por recuperar los recursos en que basan sus medios de vida. Una implementación cuya sostenibilidad, en última instancia, sólo se puede garantizar mediante la adopción de dichas tecnologías a través los beneficios observados por ellos mismos.

Valorización de subproductos agrícolas y forestales como sustratos de cultivo en el estado de Oaxaca (México)

El presente trabajo aborda el aprovechamiento de algunos subproductos agrícolas (bagazo de maguey y fibra de coco) y forestales (corteza de pino) en el Estado de Oaxaca (Sur de México). El objetivo principal se centra en localizar, cuantificar y caracterizar estos con vistas a su aplicación como sustratos o componentes de sustratos en cultivos ornamentales, forestales y hortícolas, y a su uso como enmiendas en cultivos tipo. Así mismo se persigue reducir el uso de la turba y la tierra de monte como sustratos mayoritarios en la actualidad. Para la localización de los subproductos se utilizaron los datos de los registros parcelarios de los productores de coco para la obtención de copra (generadores de fibra de coco) de la región costa y de los productores de mezcal (generadores del residuo de bagazo de maguey) de la región valles centrales, así como las ubicaciones de los aserraderos forestales en el Estado de Oaxaca. Se emplea un Sistema de Información Geográfica (SIG) con una cartografía digitalizada de los elementos del medio (clima, geología y suelo), de los cultivos generadores (bagazo de maguey, fibra de coco y corteza de pino), de la agricultura protegida como receptora (tomate) y de la agricultura extensiva con cultivos receptores de enmienda (café, hule, limón, mango, palma de coco y maguey). La producción anual de los residuos se cartografía y cuantifica con los siguientes resultados: bagazo de maguey 624.000 t, fibra de coco 86.000 m3 y 72.000 t de corteza de pino. Mediante el estudio de las características de los suelos de los cultivos receptores y de los requerimientos de materia orgánica de cada cultivo se calcularon las necesidades totales de materia orgánica para cada suelo. Los resultados de las cantidades globales para cada cultivo en todo el Estado muestran una necesidad total de 3.112.000 t de materia orgánica como enmienda. Con los datos obtenidos y a través de un algoritmo matemático se realiza una propuesta de localización de dos plantas de compostaje (de bagazo de maguey y fibra de coco) y cuatro plantas de compostaje de corteza de pino. Con el fin de conocer los subproductos a valorizar como sustrato o componente de sustrato se caracteriza su composición física‐química, siguiendo Normas UNE‐EN, y se analizan mediante Resonancia Magnética Nuclear (RMN). Para el acondicionamiento de bagazo de maguey y la corteza de pino se realizaron ensayos de compostaje. Al final de 241 días la temperatura y la humedad de ambos procesos se encontraban en los rangos recomendados, indicando que los materiales estaban estabilizados y con calidad para ser utilizados como sustrato o componente de sustrato. Para la fibra de coco se realizó el proceso de molienda en seco de conchas de coco provenientes de la comunidad de Río Grande Oaxaca (Principal zona productora de copra en Oaxaca). Posteriormente se emplean los materiales obtenidos como componentes para sustratos de cultivo. Se estudia el compost de bagazo de maguey y siete mezclas; el compost de corteza de pino y ocho mezclas y la fibra de coco con tres mezclas. Estos sustratos alternativos permiten obtener mezclas y reducir el uso de la tierra de monte, turba, arcilla expandida y vermiculita, siendo por tanto una alternativa sostenible para la producción en invernadero. Se elaboraron mezclas especificas para el cultivo de Lilium hibrido asiático y oriental (siete mezclas), sustratos eco‐compatibles para cultivo de tomate (nueve mezclas), para la producción de planta forestal (siete mezclas) y para la producción de plántula hortícola (ocho mezclas). Como resultados más destacados del bagazo de maguey, corteza de pino y las mezclas obtenidas se resume lo siguiente: el bagazo de maguey, con volúmenes crecientes de turba (20, 30, 50 y 60 %) y la corteza de pino, con volúmenes de turba 40 y 60%, presentan valores muy recomendados de porosidad, capacidad de aireación, capacidad de retención de humedad y equilibrio agua‐aire. Para la fibra de coco, la procedente de Río Grande presenta mejor valoración que la muestra comercial de fibra de coco de Morelos. Por último se llevó a cabo la evaluación agronómica de los sustratos‐mezclas, realizando cinco experimentos por separado, estudiando el desarrollo vegetal de cultivos tipo, que se concretan en los siguientes ensayos: 1. Producción de Lilium asiático y oriental en cama para flor de corte; 2. Producción de Lilium oriental en contenedor para flor de corte; 3. Producción de plántula forestal (Pinus greggii E y Pinus oaxacana M); 4. Producción de tomate (Solanum lycopersicum L) y 5. Producción de plántula de tomate en semillero (Solanum lycopersicum L). En relación a la producción de Lilium hibrido asiático en cama los sustratos corteza de pino (CPTU 80:20 v/v), corteza de pino + sustrato comercial (CPSC 80:20 v/v) y corteza de pino+turba+arcilla expandida+vermiculita (CPTAEV2 30:40:15:15 v/v) presentan los mejores resultados. Dichos sustratos también presentan adecuados resultados para Lilium hibrido oriental con excepción de la corteza de pino + turba (CPTU 80:20 v/v). En la producción de Lilium hibrido oriental en contenedor para flor de corte, además de los sustratos de CPSC y CPTAEV2, la mezcla de corteza de pino+turba+arcilla expandida+vermiculita (CPTAEV 70:20:5:5 v/v) manifestó una respuesta favorable. En el ensayo de producción de plántulas de Pinus greggii E y Pinus oaxacana Mirov, las mezclas con corteza de pino+turba+arcilla expandida+vermiculita (CPTAEV2 30:40:15:15 v/v) y bagazo de maguey turba+arcilla expandida+vermiculita (BMTAEV2 30:60:5:5 v/v) son una alternativa que permite disminuir el empleo de turba, arcilla expandida y vermiculita, en comparación con el sustrato testigo de turba+arcilla expandida+vermiculita (TAEV 60:30:10 v/v). En la producción de tomate (Solanum lycopersicum L) frente a la utilización actual del serrín sin compostar (SSC), las mezclas alternativas de bagazo de maguey+turba (BMT 70:30 v/v), fibra de coco de Río Grande (FCRG 100v/v) y corteza de pino+turba (CPT 70:30 v/v), presentaron los mejores resultados en rendimientos. Así mismo, en la producción de plántulas de tomate las dos mezclas alternativas de bagazo de maguey+turba+ arcilla expandida+vermiculita (BMTAEV5 50:30:10:10 v/v) y (BMTAEV6 40:40:10:10 v/v) presentaron mejores resultados que los obtenidos en la mezcla comercial (Sunshine 3), mayoritariamente utilizada en México en la producción de plántula de tomate y hortícola. ABSTRACT This paper addresses the use of some agricultural products (maguey bagasse and coconut fiber) and forestry (pine bark) in the State of Oaxaca (southern Mexico). The principal purpose is to locate, quantify and characterize these with the idea of applying them as substrates or substrate components in ornamental crops, forestry, horticultural, and their use as crop amendments. On the other hand, the reduction of peat and forest soil as main substrates is pursued. For the location of the products, registry parcel data from copra producers (coconut fiber generators) of the coastal region and mescal producers (maguey bagasse residue generators) of the central valleys region, as well as the locations of forest mills in the State of Oaxaca. A Geographic Information System (GIS) with digital mapping of environmental factors (climate, geology and soil), crop generators of residues (maguey bagasse, coconut and pine bark) receptors of amendments such as protected agriculture (tomato) and extensive agriculture crops (coffee, rubber, lemon, mango, coconut and agave). The annual production of waste is mapped and quantified with the following results: 624,000t maguey bagasse, coconut fiber 72,000 m3 and 86,000 t of pine bark. Through the study of receiving crops soils properties of and organic matter requirements of each crop, total needs of organic matter for each soil were estimated. The results of the total quantities for each crop across the state show a total of 3,112,000 t of organic matter needed as amendment. Using that data and a mathematical algorithm, the location of two composting plants (agave bagasse and coconut fiber) and four composting plants pine bark was proposed. In order to know the by‐products that were going to be used as substrates or substrate components, their physical‐chemical composition was analyzed following UNE‐EN technics. Furthermore they were analyzed by Nuclear Magnetic Resonance (NMR). For conditioning of maguey bagasse and pine bark, composting essays were conducted. At the end of 241 days the temperature and humidity of both processes were at the recommended ranges, indicating that the materials were stabilized and had reached the quality to be used as a substrate or substrate component. Coconut shells from the community of Rio Grande Oaxaca (Main copra producing area in Oaxaca) were put through a process of dry milling. Subsequently, the obtained materials were used as components for growing media. We studied the maguey bagasse compost and seven mixtures; the pine bark compost and eight blends and coconut fiber with three mixtures. These alternative substrates allow obtaining mixtures and reduce the use of forest soil, peat, vermiculite and expanded clay, making it a sustainable alternative for greenhouse production. Specific mixtures were prepared for growing Lillium, Asian and eastern hybrids (seven blends), eco‐compatible substrates for tomato (nine mixtures), for producing forest plant (seven mixtures) and for the production of horticultural seedlings (eight mixtures). Results from maguey bagasse, pine bark and mixtures obtained are summarized as follows: the maguey bagasse, with increasing volumes of peat (20, 30, 50 and 60%) and pine bark mixed with 40 and 60% peat by volume, have very recommended values of porosity, aeration capacity, water retention capacity and water‐air balance. Coconut fiber from Rio Grande had better quality than commercial coconut fiber from Morelos. Finally the agronomic evaluation of substrates‐mixtures was carried out conducting five experiments separately: 1. Production of Asiatic and Eastern Lilium in bed for cut flower, 2. Production of oriental Lillium in container for cut flower, 3.Production of forest seedlings (Pinus greggii E and Pinus oaxacana M), 4. Production of tomato (Solanum lycopersicum L) and 5. Tomato seedling production in seedbed (Solanum lycopersicum L). In relation to the production of hybrid Asian Lilium in bed, pine bark substrates (CPTU 80:20 v/v), pine bark + commercial substrate (CPSC 80:20 v/v) and pine bark + peat + expanded clay + vermiculite (CPTAEV2 30:40:15:15 v/v) showed the best results. Such substrates also have adequate results for Lilium Oriental hybrid except pine bark + peat (CPTU 80:20 v / v). In the production of Lilium oriental hybrid container for cut flower, besides the CPSC and CPTAEV2 substrates, the mixture of pine bark + peat + vermiculite expanded clay (CPTAEV 70:20:5:5 v / v) showed a favorable response. In the production of Pinus greggii E and Pinus oaxacana Mirov seedlings trial, mixtures with pine bark + peat + expanded clay + vermiculite (CPTAEV2 30:40:15:15 v/v) and maguey bagasse+ peat+ expanded clay + vermiculite (BMTAEV2 30:60:5:5 v / v) are an alternative which allows reducing the use of peat, vermiculite and expanded clay in comparison with the control substrate made of peat + expanded clay+ vermiculite (60:30 TAEV: 10 v/v). In the production of tomato (Solanum lycopersicum L), alternative mixes of maguey bagasse + peat (BMT 70:30 v/v), coconut fiber from Rio Grande (FCRG 100 v / v) and pine bark + peat (CPT 70:30 v / v) showed the best results in yields versus the current use of sawdust without compost (SSC). Likewise, in the production of tomato seedlings of the two alternative mixtures maguey bagasse + peat expanded clay + vermiculite (BMTAEV5 50:30:10:10 v/v) and (BMTAEV6 40:40:10:10 v/v) had better results than those obtained in the commercial mixture (Sunshine 3), mainly used in Mexico in tomato seedling production and horticulture.

Airport Taxi Planning: Lagrangian Decomposition

The airport taxi planning (TP) module is a decision tool intended to guide airport surface management operations. TP is defined by a flow network optimization model that represents flight ground movements and improves aircraft taxiing routes and schedules during periods of aircraft congestion. TP is not intended to operate as a stand‐alone tool for airport operations management: on the contrary, it must be used in conjunction with existing departing and arriving traffic tools and overseen by the taxi planner of the airport, also known as the aircraft ground controller. TP must be flexible in order to accommodate changing inputs while maintaining consistent routes and schedules already delivered from past executions. Within this dynamic environment, the execution time of TP may not exceed a few minutes. Classic methods for solving binary multi‐commodity flow networks with side constraints are not efficient enough; therefore, a Lagrangian decomposition methodology has been adapted to solve it. We demonstrate TP Lagrangian decomposition using actual data from the Madrid‐Barajas Airport

An interpolation tool for aerodynamic mesh deformation problems based on octree decomposition

Desarrollo de algoritmo de interpolación basado en descomposición octree y funciones radiales de soporte compacto para movimiento de mallas en problemas aerolásticos

Decomposition driven interface evolution for layers of binary mixtures: I. Model dirivation and base states

A dynamical model is proposed to describe the coupled decomposition and profile evolution of a free surfacefilm of a binary mixture. An example is a thin film of a polymer blend on a solid substrate undergoing simultaneous phase separation and dewetting. The model is based on model-H describing the coupled transport of the mass of one component (convective Cahn-Hilliard equation) and momentum (Navier-Stokes-Korteweg equations) supplemented by appropriate boundary conditions at the solid substrate and the free surface. General transport equations are derived using phenomenological nonequilibrium thermodynamics for a general nonisothermal setting taking into account Soret and Dufour effects and interfacial viscosity for the internal diffuse interface between the two components. Focusing on an isothermal setting the resulting model is compared to literature results and its base states corresponding to homogeneous or vertically stratified flat layers are analyzed.

Decomposition driven interface evolution for layers of binary mixtures: I. Model dirivation and base states

Algebraic topology (homology) is used to analyze the state of spiral defect chaos in both laboratory experiments and numerical simulations of Rayleigh-Bénard convection. The analysis reveals topological asymmetries that arise when non-Boussinesq effects are present. The asymmetries are found in different flow fields in the simulations and are robust to substantial alterations to flow visualization conditions in the experiment. However, the asymmetries are not observable using conventional statistical measures. These results suggest homology may provide a new and general approach for connecting spatiotemporal observations of chaotic or turbulent patterns to theoretical models.

Overal reaction rate and stoichiometry for thermal decomposition of hydrazine

An asymptotic analysîs of the Eberstein-Glassman kinetic mechanlsm for the thermal décomposition of hydrazine is carried out. It is shown that at températures near 800°K and near 1000°K,and for hydrazine molar fractions of the order of unity, 10-2 the entire kinetics reduces to a single, overall reaction. Characteristic times for the chemical relaxation of ail active, intermediate species produced in the décomposition, and for the overall reaction, are obtained. Explicit expressions for the overall reaction rate and stoichiometry are given as functions of température, total molar concentration (or pressure)and hydrazine molar fraction. Approximate, patched expressions can then be obtained for values of température and hydrazine molar fraction between 750 and 1000°K, and 1 and 10-3 respectively.

Estudio de viabilidad técnica e hidrológica para el almacenamiento de agua de lluvia en la Barranca del Carbón, San Juan Ihualtepec, Oaxaca (México)

La comunidad de San Juan Ihualtepec, ubicada en una de las zonas de la Región Mixteca con mayores índices de rezago social y pobreza, no está aislada de la problemática de falta de agua. Por lo que respecta a la utilización de sus recursos, principalmente suelo y agua, se observa un uso intensivo de los mismos, pero sin considerar prácticas para su manejo y conservación. La agricultura es la actividad principal de esta comunidad, la cual se ve afectada por la escasa precipitación. La falta de agua para el riego durante la época de estiaje es de difícil solución, ya que la baja precipitación reduce la presencia de fuentes de abastecimiento de agua permanentes, lo que ha obligado a los campesinos a una agricultura prácticamente de auto-consumo y de subsistencia. En este trabajo se evaluó la factibilidad hidrológica y geológica de almacenar agua de lluvia con fines de desarrollo rural, llevándose a cabo estudios hidrológicos, topográficos y geológicos.

Optimization methods for the operating room management under uncertainty: stochastic programming vs. decomposition approach

The operating theatres are the engine of the hospitals; proper management of the operating rooms and its staff represents a great challenge for managers and its results impact directly in the budget of the hospital. This work presents a MILP model for the efficient schedule of multiple surgeries in Operating Rooms (ORs) during a working day. This model considers multiple surgeons and ORs and different types of surgeries. Stochastic strategies are also implemented for taking into account the uncertain in surgery durations (pre-incision, incision, post-incision times). In addition, a heuristic-based methods and a MILP decomposition approach is proposed for solving large-scale ORs scheduling problems in computational efficient way. All these computer-aided strategies has been implemented in AIMMS, as an advanced modeling and optimization software, developing a user friendly solution tool for the operating room management under uncertainty.

The Proper Generalized Decomposition With Application In Problems Of Dynamics

In this paper we address the new reduction method called Proper Generalized Decomposition (PGD) which is a discretization technique based on the use of separated representation of the unknown fields, specially well suited for solving multidimensional parametric equations. In this case, it is applied to the solution of dynamics problems. We will focus on the dynamic analysis of an one-dimensional rod with a unit harmonic load of frequency (ω) applied at a point of interest. In what follows, we will present the application of the methodology PGD to the problem in order to approximate the displacement field as the sum of the separated functions. We will consider as new variables of the problem, parameters models associated with the characteristic of the materials, in addition to the frequency. Finally, the quality of the results will be assessed based on an example.

Fast modularisation and aomic decomposition of ontologies using axiom dependency hypergraphs

In this paper we define the notion of an axiom dependency hypergraph, which explicitly represents how axioms are included into a module by the algorithm for computing locality-based modules. A locality-based module of an ontology corresponds to a set of connected nodes in the hypergraph, and atoms of an ontology to strongly connected components. Collapsing the strongly connected components into single nodes yields a condensed hypergraph that comprises a representation of the atomic decomposition of the ontology. To speed up the condensation of the hypergraph, we first reduce its size by collapsing the strongly connected components of its graph fragment employing a linear time graph algorithm. This approach helps to significantly reduce the time needed for computing the atomic decomposition of an ontology. We provide an experimental evaluation for computing the atomic decomposition of large biomedical ontologies. We also demonstrate a significant improvement in the time needed to extract locality-based modules from an axiom dependency hypergraph and its condensed version.

Strong Connectivity in Directed Hypergraphs and its Application to the Atomic Decomposition of Ontologies

Los hipergrafos dirigidos se han empleado en problemas relacionados con lógica proposicional, bases de datos relacionales, linguística computacional y aprendizaje automático. Los hipergrafos dirigidos han sido también utilizados como alternativa a los grafos (bipartitos) dirigidos para facilitar el estudio de las interacciones entre componentes de sistemas complejos que no pueden ser fácilmente modelados usando exclusivamente relaciones binarias. En este contexto, este tipo de representación es conocida como hiper-redes. Un hipergrafo dirigido es una generalización de un grafo dirigido especialmente adecuado para la representación de relaciones de muchos a muchos. Mientras que una arista en un grafo dirigido define una relación entre dos de sus nodos, una hiperarista en un hipergrafo dirigido define una relación entre dos conjuntos de sus nodos. La conexión fuerte es una relación de equivalencia que divide el conjunto de nodos de un hipergrafo dirigido en particiones y cada partición define una clase de equivalencia conocida como componente fuertemente conexo. El estudio de los componentes fuertemente conexos de un hipergrafo dirigido puede ayudar a conseguir una mejor comprensión de la estructura de este tipo de hipergrafos cuando su tamaño es considerable. En el caso de grafo dirigidos, existen algoritmos muy eficientes para el cálculo de los componentes fuertemente conexos en grafos de gran tamaño. Gracias a estos algoritmos, se ha podido averiguar que la estructura de la WWW tiene forma de “pajarita”, donde más del 70% del los nodos están distribuidos en tres grandes conjuntos y uno de ellos es un componente fuertemente conexo. Este tipo de estructura ha sido también observada en redes complejas en otras áreas como la biología. Estudios de naturaleza similar no han podido ser realizados en hipergrafos dirigidos porque no existe algoritmos capaces de calcular los componentes fuertemente conexos de este tipo de hipergrafos. En esta tesis doctoral, hemos investigado como calcular los componentes fuertemente conexos de un hipergrafo dirigido. En concreto, hemos desarrollado dos algoritmos para este problema y hemos determinado que son correctos y cuál es su complejidad computacional. Ambos algoritmos han sido evaluados empíricamente para comparar sus tiempos de ejecución. Para la evaluación, hemos producido una selección de hipergrafos dirigidos generados de forma aleatoria inspirados en modelos muy conocidos de grafos aleatorios como Erdos-Renyi, Newman-Watts-Strogatz and Barabasi-Albert. Varias optimizaciones para ambos algoritmos han sido implementadas y analizadas en la tesis. En concreto, colapsar los componentes fuertemente conexos del grafo dirigido que se puede construir eliminando ciertas hiperaristas complejas del hipergrafo dirigido original, mejora notablemente los tiempos de ejecucion de los algoritmos para varios de los hipergrafos utilizados en la evaluación. Aparte de los ejemplos de aplicación mencionados anteriormente, los hipergrafos dirigidos han sido también empleados en el área de representación de conocimiento. En concreto, este tipo de hipergrafos se han usado para el cálculo de módulos de ontologías. Una ontología puede ser definida como un conjunto de axiomas que especifican formalmente un conjunto de símbolos y sus relaciones, mientras que un modulo puede ser entendido como un subconjunto de axiomas de la ontología que recoge todo el conocimiento que almacena la ontología sobre un conjunto especifico de símbolos y sus relaciones. En la tesis nos hemos centrado solamente en módulos que han sido calculados usando la técnica de localidad sintáctica. Debido a que las ontologías pueden ser muy grandes, el cálculo de módulos puede facilitar las tareas de re-utilización y mantenimiento de dichas ontologías. Sin embargo, analizar todos los posibles módulos de una ontología es, en general, muy costoso porque el numero de módulos crece de forma exponencial con respecto al número de símbolos y de axiomas de la ontología. Afortunadamente, los axiomas de una ontología pueden ser divididos en particiones conocidas como átomos. Cada átomo representa un conjunto máximo de axiomas que siempre aparecen juntos en un modulo. La decomposición atómica de una ontología es definida como un grafo dirigido de tal forma que cada nodo del grafo corresponde con un átomo y cada arista define una dependencia entre una pareja de átomos. En esta tesis introducimos el concepto de“axiom dependency hypergraph” que generaliza el concepto de descomposición atómica de una ontología. Un modulo en una ontología correspondería con un componente conexo en este tipo de hipergrafos y un átomo de una ontología con un componente fuertemente conexo. Hemos adaptado la implementación de nuestros algoritmos para que funcionen también con axiom dependency hypergraphs y poder de esa forma calcular los átomos de una ontología. Para demostrar la viabilidad de esta idea, hemos incorporado nuestros algoritmos en una aplicación que hemos desarrollado para la extracción de módulos y la descomposición atómica de ontologías. A la aplicación la hemos llamado HyS y hemos estudiado sus tiempos de ejecución usando una selección de ontologías muy conocidas del área biomédica, la mayoría disponibles en el portal de Internet NCBO. Los resultados de la evaluación muestran que los tiempos de ejecución de HyS son mucho mejores que las aplicaciones más rápidas conocidas. ABSTRACT Directed hypergraphs are an intuitive modelling formalism that have been used in problems related to propositional logic, relational databases, computational linguistic and machine learning. Directed hypergraphs are also presented as an alternative to directed (bipartite) graphs to facilitate the study of the interactions between components of complex systems that cannot naturally be modelled as binary relations. In this context, they are known as hyper-networks. A directed hypergraph is a generalization of a directed graph suitable for representing many-to-many relationships. While an edge in a directed graph defines a relation between two nodes of the graph, a hyperedge in a directed hypergraph defines a relation between two sets of nodes. Strong-connectivity is an equivalence relation that induces a partition of the set of nodes of a directed hypergraph into strongly-connected components. These components can be collapsed into single nodes. As result, the size of the original hypergraph can significantly be reduced if the strongly-connected components have many nodes. This approach might contribute to better understand how the nodes of a hypergraph are connected, in particular when the hypergraphs are large. In the case of directed graphs, there are efficient algorithms that can be used to compute the strongly-connected components of large graphs. For instance, it has been shown that the macroscopic structure of the World Wide Web can be represented as a “bow-tie” diagram where more than 70% of the nodes are distributed into three large sets and one of these sets is a large strongly-connected component. This particular structure has been also observed in complex networks in other fields such as, e.g., biology. Similar studies cannot be conducted in a directed hypergraph because there does not exist any algorithm for computing the strongly-connected components of the hypergraph. In this thesis, we investigate ways to compute the strongly-connected components of directed hypergraphs. We present two new algorithms and we show their correctness and computational complexity. One of these algorithms is inspired by Tarjan’s algorithm for directed graphs. The second algorithm follows a simple approach to compute the stronglyconnected components. This approach is based on the fact that two nodes of a graph that are strongly-connected can also reach the same nodes. In other words, the connected component of each node is the same. Both algorithms are empirically evaluated to compare their performances. To this end, we have produced a selection of random directed hypergraphs inspired by existent and well-known random graphs models like Erd˝os-Renyi and Newman-Watts-Strogatz. Besides the application examples that we mentioned earlier, directed hypergraphs have also been employed in the field of knowledge representation. In particular, they have been used to compute the modules of an ontology. An ontology is defined as a collection of axioms that provides a formal specification of a set of terms and their relationships; and a module is a subset of an ontology that completely captures the meaning of certain terms as defined in the ontology. In particular, we focus on the modules computed using the notion of syntactic locality. As ontologies can be very large, the computation of modules facilitates the reuse and maintenance of these ontologies. Analysing all modules of an ontology, however, is in general not feasible as the number of modules grows exponentially in the number of terms and axioms of the ontology. Nevertheless, the modules can succinctly be represented using the Atomic Decomposition of an ontology. Using this representation, an ontology can be partitioned into atoms, which are maximal sets of axioms that co-occur in every module. The Atomic Decomposition is then defined as a directed graph such that each node correspond to an atom and each edge represents a dependency relation between two atoms. In this thesis, we introduce the notion of an axiom dependency hypergraph which is a generalization of the atomic decomposition of an ontology. A module in the ontology corresponds to a connected component in the hypergraph, and the atoms of the ontology to the strongly-connected components. We apply our algorithms for directed hypergraphs to axiom dependency hypergraphs and in this manner, we compute the atoms of an ontology. To demonstrate the viability of this approach, we have implemented the algorithms in the application HyS which computes the modules of ontologies and calculate their atomic decomposition. In the thesis, we provide an experimental evaluation of HyS with a selection of large and prominent biomedical ontologies, most of which are available in the NCBO Bioportal. HyS outperforms state-of-the-art implementations in the tasks of extracting modules and computing the atomic decomposition of these ontologies.

Aerodynamic database reconstruction via gappy high order singular value decomposition

Esta Tesis se centra en el desarrollo de un método para la reconstrucción de bases de datos experimentales incompletas de más de dos dimensiones. Como idea general, consiste en la aplicación iterativa de la descomposición en valores singulares de alto orden sobre la base de datos incompleta. Este nuevo método se inspira en el que ha servido de base para la reconstrucción de huecos en bases de datos bidimensionales inventado por Everson y Sirovich (1995) que a su vez, ha sido mejorado por Beckers y Rixen (2003) y simultáneamente por Venturi y Karniadakis (2004). Además, se ha previsto la adaptación de este nuevo método para tratar el posible ruido característico de bases de datos experimentales y a su vez, bases de datos estructuradas cuya información no forma un hiperrectángulo perfecto. Se usará una base de datos tridimensional de muestra como modelo, obtenida a través de una función transcendental, para calibrar e ilustrar el método. A continuación se detalla un exhaustivo estudio del funcionamiento del método y sus variantes para distintas bases de datos aerodinámicas. En concreto, se usarán tres bases de datos tridimensionales que contienen la distribución de presiones sobre un ala. Una se ha generado a través de un método semi-analítico con la intención de estudiar distintos tipos de discretizaciones espaciales. El resto resultan de dos modelos numéricos calculados en C F D . Por último, el método se aplica a una base de datos experimental de más de tres dimensiones que contiene la medida de fuerzas de una configuración ala de Prandtl obtenida de una campaña de ensayos en túnel de viento, donde se estudiaba un amplio espacio de parámetros geométricos de la configuración que como resultado ha generado una base de datos donde la información está dispersa. ABSTRACT A method based on an iterative application of high order singular value decomposition is derived for the reconstruction of missing data in multidimensional databases. The method is inspired by a seminal gappy reconstruction method for two-dimensional databases invented by Everson and Sirovich (1995) and improved by Beckers and Rixen (2003) and Venturi and Karniadakis (2004). In addition, the method is adapted to treat both noisy and structured-but-nonrectangular databases. The method is calibrated and illustrated using a three-dimensional toy model database that is obtained by discretizing a transcendental function. The performance of the method is tested on three aerodynamic databases for the flow past a wing, one obtained by a semi-analytical method, and two resulting from computational fluid dynamics. The method is finally applied to an experimental database consisting in a non-exhaustive parameter space measurement of forces for a box-wing configuration.

Aerodynamic database error filtering via high order singular value decomposition

Esta Tesis presenta un nuevo método para filtrar errores en bases de datos multidimensionales. Este método no precisa ninguna información a priori sobre la naturaleza de los errores. En concreto, los errrores no deben ser necesariamente pequeños, ni de distribución aleatoria ni tener media cero. El único requerimiento es que no estén correlados con la información limpia propia de la base de datos. Este nuevo método se basa en una extensión mejorada del método básico de reconstrucción de huecos (capaz de reconstruir la información que falta de una base de datos multidimensional en posiciones conocidas) inventado por Everson y Sirovich (1995). El método de reconstrucción de huecos mejorado ha evolucionado como un método de filtrado de errores de dos pasos: en primer lugar, (a) identifica las posiciones en la base de datos afectadas por los errores y después, (b) reconstruye la información en dichas posiciones tratando la información de éstas como información desconocida. El método resultante filtra errores O(1) de forma eficiente, tanto si son errores aleatorios como sistemáticos e incluso si su distribución en la base de datos está concentrada o esparcida por ella. Primero, se ilustra el funcionamiento delmétodo con una base de datosmodelo bidimensional, que resulta de la dicretización de una función transcendental. Posteriormente, se presentan algunos casos prácticos de aplicación del método a dos bases de datos tridimensionales aerodinámicas que contienen la distribución de presiones sobre un ala a varios ángulos de ataque. Estas bases de datos resultan de modelos numéricos calculados en CFD. ABSTRACT A method is presented to filter errors out in multidimensional databases. The method does not require any a priori information about the nature the errors. In particular, the errors need not to be small, neither random, nor exhibit zero mean. Instead, they are only required to be relatively uncorrelated to the clean information contained in the database. The method is based on an improved extension of a seminal iterative gappy reconstruction method (able to reconstruct lost information at known positions in the database) due to Everson and Sirovich (1995). The improved gappy reconstruction method is evolved as an error filtering method in two steps, since it is adapted to first (a) identify the error locations in the database and then (b) reconstruct the information in these locations by treating the associated data as gappy data. The resultingmethod filters out O(1) errors in an efficient fashion, both when these are random and when they are systematic, and also both when they concentrated and when they are spread along the database. The performance of the method is first illustrated using a two-dimensional toymodel database resulting fromdiscretizing a transcendental function and then tested on two CFD-calculated, three-dimensional aerodynamic databases containing the pressure coefficient on the surface of a wing for varying values of the angle of attack. A more general performance analysis of the method is presented with the intention of quantifying the randomness factor the method admits maintaining a correct performance and secondly, quantifying the size of error the method can detect. Lastly, some improvements of the method are proposed with their respective verification.