The thesis deals with the theoretical and practical study of mathematical programming methodologies to the analysis complex networks and their application in economic and social problems. More specifically, it applies models and methods for solving linear and integer programming problems to network models exploiting the matrix structure of such models, resulting in efficient computational procedures and small processing time. As a consequence, it allows the study of larger and more complex networks models that arise in many economical and sociological applications. The main efforts have been addressed to the development of a rigorous mathematical programming based framework, which is able to capture many classes of complex network problems. Such a framework involves a general and flexible modeling approach, based on linear and integer programmin, as well as a collection of efficient probabilistic procedures to deal with these models. The computer implementation has been carried out by high level programming languages, such as Java, MatLab, R and AMPL. The final chapter of the thesis introduced an extension of the analyzed model to the case of microeconomic interaction, providing a fruitful mathematical linkage between its optimization-like properties and its multi-agents properties. The theoretical and practical use of optimization methods represents the trait-de-union of the different chapters. The overall structure of the thesis manuscript contains three parts: Part I: The fine-grained structure of complex networks: theories, models and methods; Chapter 1 and Chapter 2. Part II: Mathematical Programming based approaches for random models of network formation; Chapter 3, Chapter 4 and Chapter 5. Part III: Strategic models of network formation. Chapter 6. Results of this research have generated four working papers in quality scientific journals: one has been accepted and three are under review. Some results have been also presented in four international conferences. / La tesis aborda el estudio teórico y práctico de las metodologías de programación matemática para el análisis de redes complejas y su aplicación a problemas económicos y sociales. Más específicamente, se aplica modelos y métodos para resolver problemas de programación lineal y de programación lineal entera explotando las estructuras matriciales de tales modelos, lo que resulta en procedimientos computacionales eficientes y bajo coste de procesamiento. Como consecuencia de ello, las metodologías propuestas permiten el estudio de modelos complejos de gran dimensión, para redes complejas que surgen en muchas aplicaciones económicas y sociológicas. Los principales esfuerzos se han dirigido al desarrollo de un marco teórico basado en la programación matemática, que es capaz de capturar muchas clases de problemas de redes complejas. Dicho marco teórico envuelve un sistema general y flexible de modelado y una colección de procedimientos probabilísticos para solucionar eficientemente dichos modelos, basados en la programación linear y entera. Las implementaciones informáticas se han llevado a cabo mediante lenguajes de programación de alto nivel, como Java, Matlab, R y AMPL. El último capítulo de la tesis introduce una extensión de los modelos analizados, para el caso de la interacción microeconómica, con el objetivo de establecer un nexo metodológico entre sus propiedades de optimización y sus propiedades multi-agentes. El uso teórico y práctico de los métodos de optimización representa el elemento de conjunción de los distintos capítulos. Parte I: The fine-grained structure of complex networks: theories, models and methods; - Capitulo 1 y Capitulo 2. Parte II: Mathematical Programming based approaches for random models of network formation; - Capitulo 3, Capitulo 4 y Capitulo 5. Parte III: Strategic models of network formation. - Capitulo 6. Los resultados de esta investigación han generado cuatro papers en revistas científicas indexadas: uno ha sido aceptado, tres están en revisión. Algunos resultados han sido también presentados en cuatro conferencias internacionales

This thesis aims at developing numerical methods based on level-set techniques suitable for the direct numerical simulation (DNS) of free surface and interfacial flows, in order to be used on basic research and industrial applications. First, the conservative level-set method for capturing the interface between two fluids is combined with a variable density projection scheme in order to simulate incompressible two-phase flows on unstructured meshes. All equations are discretized by using a finite-volume approximation on a collocated grid arrangement. A high order scheme based on a flux limiter formulation, is adopted for approximating the convective terms, while the diffusive fluxes are centrally differenced. Gradients are computed by the least-squares approach, whereas physical properties are assumed to vary smoothly in a narrow band around the interface to avoid numerical instabilities. Surface tension force is calculated according to the continuous surface force approach. The numerical method is validated against experimental and numerical data reported in the scientific literature. Second, the conservative level-set method is applied to study the gravity-driven bubbly flow. Unlike the cases presented in the first part, a periodic boundary condition is applied in the vertical direction, in order to mimic a channel of infinite length. The shape and terminal velocity of a single bubble which rises in a quiescent liquid are calculated and validated against experimental results reported in the literature. In addition, different initial arrangements of bubble pairs were considered to study its hydrodynamic interaction, and, finally the interaction of multiple bubbles is explored in a periodic vertical duct, allowing their coalescence. In the third part of this thesis, a new methodology is presented for simulation of surface-tension-driven interfacial flows by combining volume-of-fluid with level-set methods. The main idea is to benefit from the advantage of each strategy, which is to minimize mass loss through the volume-of-fluid method, and to keep a fine description of the interface curvature using a level-set function. With the information of the interface given by the volume-of-fluid method, a signed distance function is reconstructed following an iterative geometric algorithm, which is used to compute surface tension force. This numerical method is validated on 2D and 3D test cases well known in the scientific literature. The simulations reveal that numerical schemes afford qualitatively similar results to those obtained by the conservative level-set method. Mass conservation is shown to be excellent, while geometrical accuracy remains satisfactory even for the most complex cases involving topology changes. In the fourth part of the thesis a novel multiple marker level-set method is presented. This method is deployed to perform numerical simulation of deformable fluid particles without numerical coalescence of their interfaces, which is a problem inherent to standard interface tracking methodologies (e.g. level-set and volume of fluid). Each fluid particle is described by a separate level-set function, thus, different interfaces can be solved in the same control volume, avoiding artificial and potentially unphysical coalescence of fluid particles. Therefore, bubbles or droplets are able to approach each other closely, within the size of one grid cell, and can even collide. The proposed algorithm is developed in the context of the conservative levelset method, whereas, surface tension is modeled by the continuous surface force approach. The pressure-velocity coupling is solved by the fractional-step projection method. For validation of the proposed numerical method, the gravity-driven impact of a droplet on a liquid-liquid interface is studied; then, the binary droplet collision with bouncing outcome is examined, and finally, it is applied on simulation of gravity-driven bubbly flow in a vertical column. The study of these cases contributed to shed some light into physics present in bubble and droplet flows. / Ésta tesis se enfoca en el desarrollo de métodos numéricos basados en la aplicación de técnicas level-set para la Simulación Numérica Directa (DNS) de flujos interfaciales y flujos de superficie libre, con el objetivo de ser usados tanto en investigación básica como en aplicaciones industriales. Primero, el método level-set conservativo desarrollado para la captura de interfaces entre dos fluidos, es combinado con un esquema de proyección adaptado para un fluido de densidad variable, con el objetivo de simular flujos de dos fases en mallas no estructuradas. Todas las ecuaciones son discretizadas mediante una aproximación de volúmenes finitos sobre un arreglo de malla colocada. Un esquema de alto orden cuya formulación se basa en el uso de limitadores de flujo, es usado para la discretización de los términos convectivos, mientras que los flujos difusivos son calculados mediante diferencias centradas. Los gradientes son calculados mediante el método de los mínimos cuadrados, en tanto que se asume que las propiedades físicas varían suavemente en una zona estrecha alrededor de la interface con el objetivo de evitar inestabilidades numéricas. La tensión superficial es incorporada mediante el enfoque de la fuerza superficial continua. El método numérico es validado con respecto a los datos experimentales y numéricos reportados en la literatura científica. Segundo, el método level-set conservativo es aplicado en el estudio del flujo de burbujas conducidas por la gravedad. A diferencia de los casos precedentes, se aplica una condición de frontera periódica en la dirección vertical, con el objetivo de simular un canal de longitud infinita. La forma y velocidad terminal de una burbuja ascenciendo en un líquido inicialmente en reposo son calculadas y contrastadas con los resultados reportados en la literatura. Adicionalmente se estudia la interacción hidrodinámica de un par de burbujas para diferentes configuraciones, y finalmente se explora la interacción de un emjambre de burbujas ascendiendo en un canal vertical. En la tercera parte de ésta tesis, se presenta una nueva metodología para la simulación de flujos interfaciales conducidos por la tensión superficial, mediante la combinación de los métodos volume-of-fluid y level-set. La idea principal se basa en usar el método volume-of-fluid para advectar la interface, minimizando las pérdidas de masa, mientras que las propiedades geométricas de la interface se calculan a partir de una función level-set obtenida mediante un algoritmo geométrico iterativo. La propiedades geométricas así calculadas son usadas para el cómputo de la tensión superficial. El método numérico es validado mediante casos bi y tri-dimensionales bien conocidos en la literatura científica. La conservación de la masa es excelente en tanto que la precisión del método es altamente satisfactoria incluso en los casos más complejos. En la cuarta parte de ésta tesis se presenta un nuevo método level-set de múltiples marcadores. Éste método es diseñado para llevar a cabo simulaciones numéricas de partículas de fluido deformables, evitando la coalescencia numérica de las interfaces. Cada partícula de fluido es capturada por una función level-set distinta, así, diferentes interfaces pueden ser resueltas en el mismo volumen de control, evitando la coalescencia artificial y potencialmente no-física de las partículas fluidas. Por lo tanto, las burbujas (o gotas) pueden acercarce y colisionar. El algoritmo es propuesto en el contexto del método level-set conservativo, mientras que la tensión superficial se resuelve mediante una adaptación del enfoque de la fuerza superficial continua. Para su validación, se estudia el impacto conducido por la gravedad de una gota sobre una interface líquido-líquido; luego, se estudia la collisión de dos gotas con salida rebotante, y finalmente el método numérico es aplicado para la simulación de un enjambre de burbujas sin coalescencia numérica.

Term unification is a basic operation in several areas of computer science, specially in those related to logic. Generally speaking, it consists on solving equations over expressions called terms. Depending on the kind of variables allowed to occur in the terms and under which conditions two terms are considered to be equal, several frameworks of unification such as first-order unification, higher-order unification, syntactic unification, and unification modulo theories can be distinguished. Moreover, other variants of term unification arise when we consider nontrivial representations for terms. In this thesis we study variants of the classic first-order syntactic term unification problem resulting from the introduction of context variables, i.e. variables standing for contexts, and/or assuming that the input is given in some kind of compressed representation. More specifically, we focus on two of such compressed representations: the well-known Directed Acyclic Graphs (DAGs) and Singleton Tree Grammars (STGs). Similarly as DAGs allow compression by exploiting the reusement of repeated instances of a subterm in a term, STGs are a grammar-based compression mechanism based on the reusement of repeated (multi)contexts. An interesting property of the STG formalism is that many operations on terms can be efficiently performed directly in their compressed representation thus taking advantage of the compression also when computing with the represented terms. Although finding a minimal STG representation of a term is computationally difficult, this limitation has been successfully overcome is practice, and several STG-compressors for terms are available. The STG representation has been applied in XML processing and analysis of Term Rewrite Systems. Moreover, STGs are a very useful concept for the analysis of unification problems since, roughly speaking, allow to represent solutions in a succinct but still efficiently verifiable form. / La unificació de termes és una operación básica en diverses àrees de la informática, especialment en aquelles relacionades amb la lógica. En termes generals, consisteix en resoldre equacions sobre expressions anomenades termes. Depenent del tipus de variables que apareguin en els termes i de sota quines condicions dos termes són considerats iguals, podem definir diverses variants del problema d'unificació de termes. A més a més, altres variants del problema d'unificació de termes sorgeixen quan considerem representacions no trivials per als termes. S'estudia variants del problema clàssic d'unificació sintáctica de primer ordre resultants de la introducció de variables de context i/o de l'assumpció de que l'entrada és donada en format comprimit. Ens centrem en l'estudi de dues representacions comprimides: els grafs dirigits acíclics i les gramàtiques d'arbre singletó. Similarment a com els grafs dirigits acíclics permeten compressió mitjançant el reús d'instàncies repetides d'un mateix subterme, les gramàtiques d'arbres singletó són un sistema de compressió basat en el reús de (multi)contexts. Una propietat interessant d'aquest formalisme és que moltes de les operacions comuns sobre termes es poden realizar directament sobre la versió comprimida d'aquests de forma eficient, sense cap mena de descompressió prèvia. Tot i que trobar una representació minimal d'un terme amb una gramática singletó és una tasca computacionalment difícil, aquesta limitació ha estat resolta de forma satisfactòria en la pràctica, hi ha disponibles diversos compressors per a termes. La representació de termes amb gramàtiques singletó ha estat útil per al processament de documents XML i l'anàlisi de sistemes de reescriptura de termes. Les gramàtiques singletó són concepte molt útil per a l'anàlisi de problemas d'unificació, ja que permeten representar solucions de forma comprimida sense renunciar a que puguin ser verificades de forma eficient. A la primera part d'aquesta tesi s'estudien els problemas d'unificació i matching de primer ordre sota l'assumpció de que els termes de l'entrada són representats fent servir gramàtiques singletó. Presentem algorismes de temps polinòmic per a aquests problemas, així com propostes d'implementacions i resultats experimentals. Aquests resultats s'utilitzen més endevant en aquesta tesi per a l'anàlisi de problemes d'unificació i matching amb variables de contexte i entrada comprimida. A la resta d'aquesta tesi ens centrem en variants d'unificació amb variables de contexte, que són un cas particular de variables d'ordre superior. Més concretament, a la segona part d'aquesta tesi, ens centrem en un cas particular d'unificació de contextes on nomès es permet una sola variable de context en l'entrada. Aquest problema s'anomena "one context unification". Mostrem que aquest problema es pot resoldre en temps polinòmic indeterminista, no només quan els termes de l'entrada són representats de forma explícita, sino també quan es representen fent servir grafs dirigits acíclics i gramàtiques singletó. També presentem un resultat parcial recent en la tasca de trobar un algorisme de temps polinòmic per a one context unification. Al final de la tesi, estudiem el problema de matching per a entrades amb variables de contexte, que és un cas particular d'unificació on només un dels dos termes de cada equació té variables. En contrast amb el problema general, matching de contextes ha estat classificat com a problema NP-complet. Mostrem que matching de contextes és NP-complet fins i tot quan es fan servir gramàtiques com a formalisme de representació de termes. Això implica que afegir compressió no ens porta a un augment dràstic de la complexitat del problema. També demostrem que la restricció de matching de contextes on el nombre de variables de contexte està afitat per una constant fixa del problema es pot resoldre en temps polinòmic, fins i tot quan es fan servir grafs dirigits acíclics com formalisme de representació de termes

En aquesta tesi presentem una metodologia sistemàtica la qual permet caracteritzar sistemes biològics dinàmics a partir de dades de series temporals. Del treball desenvolupat se’n desprenen tres publicacions. En la primera desenvolupem un mètode d’optimització global determinista basat en l’outer approximation per a la estimació de paràmetres en sistemes biològics dinàmics. El nostre mètode es basa en la reformulació d’un conjunt d’equacions diferencials ordinàries al seu equivalent algebraic mitjançant l’ús de mètodes de col•locació ortogonal, donant lloc a un problema no convex programació no lineal (NLP). Aquest problema no convex NLP es descompon en dos nivells jeràrquics: un problema master de programació entera mixta (MILP) que proporciona una cota inferior rigorosa al solució global, i una NLP esclau d’espai reduït que dóna un límit superior. L’algorisme itera entre aquests dos nivells fins que un criteri de terminació es satisfà. En les publicacions segona i tercera vam desenvolupar un mètode que és capaç d’identificar l’estructura regulatòria amb els corresponents paràmetres cinètics a partir de dades de series temporals. En la segona publicació vam definir un problema d’optimització dinàmica entera mixta (MIDO) on minimitzem el criteri d’informació d’Akaike. En la tercera publicació vam adoptar una perspectiva MIDO multicriteri on minimitzem l’ajust i complexitat simultàniament mitjançant el mètode de l’epsilon constraint on un dels objectius es tracta com la funció objectiu mentre que la resta es converteixen en restriccions auxiliars. En ambdues publicacions els problemes MIDO es reformulen a programació entera mixta no lineal (MINLP) mitjançant la col•locació ortogonal en elements finits on les variables binàries s’utilitzem per modelar l’existència d’interaccions regulatòries. / En esta tesis presentamos una metodología sistemática que permite caracterizar sistemas biológicos dinámicos a partir de datos de series temporales. Del trabajo desarrollado se desprenden tres publicaciones. En la primera desarrollamos un método de optimización global determinista basado en el outer approximation para la estimación de parámetros en sistemas biológicos dinámicos. Nuestro método se basa en la reformulación de un conjunto de ecuaciones diferenciales ordinarias a su equivalente algebraico mediante el uso de métodos de colocación ortogonal, dando lugar a un problema no convexo de programación no lineal (NLP). Este problema no convexo NLP se descompone en dos niveles jerárquicos: un problema master de programación entera mixta (MILP) que proporciona una cota inferior rigurosa al solución global, y una NLP esclavo de espacio reducido que da un límite superior. El algoritmo itera entre estos dos niveles hasta que un criterio de terminación se satisface. En las publicaciones segunda y tercera desarrollamos un método que es capaz de identificar la estructura regulatoria con los correspondientes parámetros cinéticos a partir de datos de series temporales. En la segunda publicación definimos un problema de optimización dinámica entera mixta (MIDO) donde minimizamos el criterio de información de Akaike. En la tercera publicación adoptamos una perspectiva MIDO multicriterio donde minimizamos el ajuste y complejidad simultáneamente mediante el método del epsilon constraint donde uno de los objetivos se trata como la función objetivo mientras que el resto se convierten en restricciones auxiliares. En ambas publicaciones los problemas MIDO se reformulan a programación entera mixta no lineal (MINLP) mediante la colocación ortogonal en elementos finitos donde las variables binarias se utilizan para modelar la existencia de interacciones regulatorias. / In this thesis we present a systematic methodology to characterize dynamic biological systems from time series data. From the work we derived three publications. In the first we developed a deterministic global optimization method based on the outer approximation for parameter estimation in dynamic biological systems. Our method is based on reformulating the set of ordinary differential equations into an equivalent set of algebraic equations through the use of orthogonal collocation methods, giving rise to a nonconvex nonlinear programming (NLP) problem. This nonconvex NLP is decomposed into two hierarchical levels: a master mixed-integer linear programming problem (MILP) that provides a rigorous lower bound on the optimal solution, and a reduced-space slave NLP that yields an upper bound. The algorithm iterates between these two levels until a termination criterion is satisfied. In the second and third publications we developed a method that is able to identify the regulatory structure and its corresponding kinetic parameters from time series data. In the second publication we defined a mixed integer dynamic optimization problem (MIDO) which minimize the Akaike information criterion. In the third publication, we adopted a multi-criteria MIDO which minimize complexity and fit simultaneously using the epsilon constraint method in which one objective is treated as the objective function while the rest are converted to auxiliary constraints. In both publications MIDO problems were reformulated to mixed integer nonlinear programming (MINLP) through the use of orthogonal collocation on finite elements where binary variables are used to model the existence of regulatory interactions.

The present thesis aims at developing a basis for the numerical simulation of multiphase flows of immiscible fluids. This approach, although limited by the computational power of the present computers, is potentially very important, since most of the physical phenomena of these flows often happen on space and time scales where experimental techniques are impossible to be utilized in practice. In particular, this research is focused on developing numerical discretizations suitable for three-dimensional (3-D) unstructured meshes. In detail, the first chapter delimits the considered multiphase flows to the case in which the components are immiscible fluids. In particular, the focus is placed on those cases where two or more continuous streams of different fluids are separated by interfaces, and hence, correspondingly named separated flows. Additionally, once the type of flow is determined, the chapter introduces the physical characteristics and the models available to predict its behavior, as well as the mathematical formulation that sustains the numerical techniques developed within this thesis. The second chapter introduces and analyzes a new geometrical Volume-of-Fluid (VOF) method for capturing interfaces on 3-D Cartesian and unstructured meshes. The method reconstructs interfaces as first- and second-order piecewise planar approximations (PLIC), and advects volumes in a single unsplit Lagrangian-Eulerian (LE) geometrical algorithm based on constructing flux polyhedrons by tracing back the Lagrangian trajectories of the cell-vertex velocities. In this way, the situations of overlapping between flux polyhedrons are minimized. Complementing the previous chapter, the third one proposes a parallelization strategy for the VOF method. The main obstacle is that the computing costs are concentrated in the interface between fluids. Consequently, if the interface is not homogeneously distributed, standard domain decomposition (DD) strategies lead to imbalanced workload distributions. Hence, the new strategy is based on a load balancing process complementary to the underlying domain decomposition. Its parallel efficiency has been analyzed using up to 1024 CPU-cores, and the results obtained show a gain with respect to the standard DD strategy up to 12x, depending on the size of the interface and the initial distribution. The fourth chapter describes the discretization of the single-phase Navier-Stokes equations to later extend it to the case of multiphase immiscible flow. One of the most important characteristics of the discretization schemes, aside from accuracy, is their capacity to discretely conserve kinetic energy, specially when solving turbulent flow. Hence, this chapter analyzes the accuracy and conservation properties of two particular collocated and staggered mesh schemes. The extension of the numerical schemes suitable for the single-phase Navier-Stokes equations to the case of multiphase immiscible flow is developed in the fifth chapter. Particularly, while the numerical techniques for the simulation of turbulent flow have evolved to discretely preserve mass, momentum and, specially, kinetic energy, the mesh schemes for the discretization of multiphase immiscible flow have evolved to improve their stability and robustness. Therefore, this chapter presents and analyzes two particular collocated and staggered mesh discretizations, able to simulate multiphase immiscible flow, which favor the discrete conservation of mass, momentum and kinetic energy. Finally, the sixth chapter numerically simulates the Richtmyer-Meshkov (RM) instability of two incompressible immiscible liquids. This chapter is a general assessment of the numerical methods developed along this thesis. In particular, the instability has been simulated by means of a VOF method and a staggered mesh scheme. The corresponding numerical results have shown the capacity of the discrete system to obtain accurate results for the RM instability. / Aquesta tesi té com a objectiu desenvolupar una base per a la simulació numèrica de fluids multi-fase immiscibles. Aquesta estratègia, encara que limitada per la potència computacional dels computadors actuals, és potencialment molt important, ja que la majoria de la fenomenologia d'aquests fluids sovint passa en escales temporals i especials on les tècniques experimentals no poden ser utilitzades. En particular, aquest treball es centra en desenvolupar discretitzacions numèriques aptes per a malles no-estructurades en tres dimensions (3-D). En detall, el primer capítol delimita els casos multifásics considerats al cas en que els components són fluids immiscibles. En particular, la tesi es centra en aquells casos en que dos o més fluids diferents són separats per interfases, i per tant, corresponentment anomenats fluxos separats. A més a més, un cop el tipus de flux es determinat, el capítol introdueix les característiques físiques i els models disponibles per predir el seu comportament, així com també la formulació matemàtica i les tècniques numèriques desenvolupades en aquesta tesi. El segon capítol introdueix i analitza un nou mètode "Volume-of-Fluid" (VOF) apte per a capturar interfases en malles Cartesianes i no-estructurades 3-D. El mètode reconstrueix les interfases com aproximacions "piecewise planar approximations" (PLIC) de primer i segon ordre, i advecciona els volums amb un algoritme geomètric "unsplit Lagrangian-Eulerian" (LE) basat en construïr els poliedres a partir de les velocitats dels vèrtexs de les celdes. D'aquesta manera, les situacions de sobre-solapament entre poliedres són minimitzades. Complementant el capítol anterior, el tercer proposa una estratègia de paral·lelització pel mètode VOF. L'obstacle principal és que els costos computacionals estan concentrats en les celdes de l'interfase entre fluids. En conseqüència, si la interfase no està ben distribuïda, les estratègies de "domain decomposition" (DD) resulten en distribucions de càrrega desequilibrades. Per tant, la nova estratègia està basada en un procés de balanceig de càrrega complementària a la DD. La seva eficiència en paral·lel ha sigut analitzada utilitzant fins a 1024 CPU-cores, i els resultats obtinguts mostren uns guanys respecte l'estratègia DD de fins a 12x, depenent del tamany de la interfase i de la distribució inicial. El quart capítol descriu la discretització de les equacions de Navier-Stokes per a una sola fase, per després estendre-ho al cas multi-fase. Una de les característiques més importants dels esquemes de discretització, a part de la precisió, és la seva capacitat per conservar discretament l'energia cinètica, específicament en el cas de fluxos turbulents. Per tant, aquest capítol analitza la precisió i propietats de conservació de dos esquemes de malla diferents: "collocated" i "staggered". L'extensió dels esquemes de malla aptes per els casos de una sola fase als casos multi-fase es desenvolupa en el cinquè capítol. En particular, així com en el cas de la simulació de la turbulència les tècniques numèriques han evolucionat per a preservar discretament massa, moment i energia cinètica, els esquemes de malla per a la discretització de fluxos multi-fase han evolucionat per millorar la seva estabilitat i robustesa. Per lo tant, aquest capítol presenta i analitza dos discretitzacions de malla "collocated" i "staggered" particulars, aptes per simular fluxos multi-fase, que afavoreixen la conservació discreta de massa, moment i energia cinètica. Finalment, el capítol sis simula numèricament la inestabilitat de Richtmyer-Meshkov (RM) de dos fluids immiscibles i incompressibles. Aquest capítol es una prova general dels mètodes numèrics desenvolupats al llarg de la tesi. En particular, la inestabilitat ha sigut simulada mitjançant un mètode VOF i un esquema de malla "staggered". Els resultats numèrics corresponents han demostrat la capacitat del sistema discret en obtenir bons resultats per la inestabilitat RM.

Avui dia, gràcies als avanços en la ciència mèdica, existeixen diverses tècniques d’imatges mèdiques destinades a tractar de revelar, diagnosticar o examinar una malaltia. Moltes d’aquestes tècniques produeixen grans quantitats de dades, especialment les modalitats de tomografia com- putada (CT), imatges per ressonància magnètica (MRI) i tomografia per emissió de positrons (PET). Per gestionar aquestes dades, els centres mèdics utilitzen PACS i l’estàndard DICOM per emmagatzemar, recuperar, distribuir i visualitzar imatges mèdiques. Com a resultat de l’alt cost d’emmagatzematge i transmissió d’imatges mèdiques digitals, la compressió de dades juga un paper clau. JPEG2000 és l’estat de l’art en tècniques de compressió d’imatges per a l’emmagatzematge i transmissió d’imatges mèdiques. És el més recent sistema de codificació inclòs en DICOM i propor- ciona algunes característiques que són interessants per a la codificació d’aquestes imatges. JPEG2000 permet l’ús de finestres d’interès, accés a diferents grandàries de la imatge o la decodificació una regió específica d’ella. Aquesta tesi aborda tres problemes diferents detectats en la codificació de CT. El primer prob- lema de la codificació d’aquestes imatges, és el soroll que tenen. Aquest soroll és produït per l’ús d’unes dosis baixes de radiació durant l’exploració, produint imatges de baixa qualitat i penalitzant el rendiment de la codificació. L’ús de diferents filtres de soroll, fa millorar la qualitat i també augmentar el rendiment de codificació. La segona qüestió que s’aborda en aquesta tesi, és l’ús de transformacions multi-component en la codificació de les CT. Depenent de la correlació entre les diferents imatges que formen una CT, el rendiment en la codificació usant aquestes transformacions pot variar, fins i tot disminuir pel que fa a JPEG2000. Finalment, l’última contribució d’aquesta tesi tracta sobre el paradigma de la codificació diagnòstica sense pèrdua, i proposa un nou mètode ivde segmentació. A través de la utilització de mètodes de segmentació, per detectar l’àrea biològica i descartar la zona no-biològica, JPEG2000 pot aconseguir millores de rendiment de més de 2 bpp. / Hoy en día, gracias a los avances en la ciencia médica, existen diversas técnicas de imágenes médicas destinadas a tratar de revelar, diagnosticar o examinar una enfermedad. Muchas de estas técnicas producen grandes cantidades de datos, en especial las modalidades de tomografía com- putarizada (CT), imágenes por resonancia magnética (MRI) y tomografía por emisión de positrones (PET). Para gestionar estos datos, los centros médicos utilizan PACS y el estándar DICOM para almacenar, recuperar, distribuir y visualizar imágenes médicas. Como resultado del alto coste de almacenamiento y transmisión de imágenes médicas digitales, la compresión de datos juega un papel clave. JPEG2000 es el estado del arte en técnicas de compresión de imágenes para el almacenamiento y transmisión de imágenes médicas. Es el más reciente sistema de codificación incluido en DICOM y proporciona algunas características que son interesantes para la codificación de estas imágenes. JPEG2000 permite el uso de ventanas de interés, acceso a diferentes tamaños de la imagen o decodificar una región específica de ella. Esta tesis aborda tres problemas diferentes detectados en la codificación de CT. El primer problema de la codificación de estas imágenes, es el ruido que tienen. Este ruido es producido por el uso de unas dosis bajas de radiación durante la exploración, lo cual produce imágenes de baja calidad y penaliza el rendimiento de la codificación. El uso de diferentes filtros de ruido, hace mejorar la calidad y también aumentar el rendimiento de codificación. La segunda cuestión que se aborda en esta tesis, es el uso de transformaciones multicomponente en la codificación de las CT. Dependiendo de la correlación entre las diferentes imágenes que forman una CT, el rendimiento en la codificación usando estas transformaciones puede variar, incluso disminuir con respecto a JPEG2000. Final- mente, la última contribución de esta tesis trata sobre el paradigma de la codificación diagnóstica sin pérdida, y propone un nuevo método de segmentación. A través de la utilización de métodos de segmentación, para detectar el área biológica y descartar la zona no-biológica, JPEG2000 puede lograr mejoras de rendimiento de más de 2bpp. / Nowadays, thanks to the advances in medical science, there exist many different medical imaging techniques aimed at seeking to reveal, diagnose, or examine a disease. Many of these techniques produce very large amounts of data, especially from Computed Tomography (CT), Magnetic Res- onance Imaging (MRI) and Positron Emission Tomography (PET) modalities. To manage these data, medical centers use PACS and the DICOM standard to store, retrieve, distribute, and display medical images. As a result of the high cost of storage and transmission of medical digital images, data compression plays a key role. JPEG2000 is the state-of-the-art of image compression for the storage and transmission of med- ical images. It is the latest coding system included in DICOM and it provides some interesting capabilities for medical image coding. JPEG2000 enables the use of use of windows of interest, access different resolutions sizes of the image or decode an specific region of the image. This thesis deals with three different problems detected in CT image coding. The first coding problem is the noise that CT have. These noise is produced by the use of low radiation dose during the scan and it produces a low quality images and penalizes the coding performance. The use of different noise filters, enhance the quality and also increase the coding performance. The second question addressed in this dissertation is the use of multi-component transforms in Computed Tomography image coding. Depending on the correlation among the slices of a Computed Tomography, the coding performance of these transforms can vary even decrease with respect to JPEG2000. Finally, the last contribution deals with the diagnostically lossless coding paradigm, and it is proposed a new segmentation method. Through the use of segmentation methods to detect the biological area and to discard the non-biological area, JPEG2000 can achieve improvements of more than 2bpp.

The first parts of this Thesis are focused on the study of the supervised evaluation of image segmentation algorithms. Supervised in the sense that the segmentation results are compared to a human-made annotation, known as ground truth, by means of different measures of similarity. The evaluation depends, therefore, on three main points. First, the image segmentation techniques we evaluate. We review the state of the art in image segmentation, making an explicit difference between those techniques that provide a flat output, that is, a single clustering of the set of pixels into regions; and those that produce a hierarchical segmentation, that is, a tree-like structure that represents regions at different scales from the details to the whole image. Second, ground-truth databases are of paramount importance in the evaluation. They can be divided into those annotated only at object level, that is, with marked sets of pixels that refer to objects that do not cover the whole image; or those with annotated full partitions, which provide a full clustering of all pixels in an image. Depending on the type of database, we say that the analysis is done from an object perspective or from a partition perspective. Finally, the similarity measures used to compare the generated results to the ground truth are what will provide us with a quantitative tool to evaluate whether our results are good, and in which way they can be improved. The main contributions of the first parts of the thesis are in the field of the similarity measures. First of all, from an object perspective, we review the used basic measures to compare two object representations and show that some of them are equivalent. In order to evaluate full partitions and hierarchies against an object, one needs to select which of their regions form the object to be assessed. We review and improve these techniques by means of a mathematical model of the problem. This analysis allows us to show that hierarchies can represent objects much better with much less number of regions than flat partitions. From a partition perspective, the literature about evaluation measures is large and entangled. Our first contribution is to review, structure, and deduplicate the measures available. We provide a new measure that we show that improves previous ones in terms of a set of qualitative and quantitative meta-measures. We also extend the measures on flat partitions to cover hierarchical segmentations. The second part of this Thesis moves from the evaluation of image segmentation to its application to object detection. In particular, we build on some of the conclusions extracted in the first part to generate segmented object candidates. Given a set of hierarchies, we build the pairs and triplets of regions, we learn to combine the set from each hierarchy, and we rank them using low-level and mid-level cues. We conduct an extensive experimental validation that show that our method outperforms the state of the art in many metrics tested.

La necesidad de analizar grandes conjuntos de datos de diferentes tipos de aplicaciones ha popularizado el uso de modelos de programación simplicados como MapReduce. La popularidad actual se justifica por ser una abstracción útil para expresar procesamiento paralelo de datos y también ocultar eficazmente la sincronización de datos, tolerancia a fallos y la gestión de balanceo de carga para el desarrollador de la aplicación. Frameworks MapReduce también han sido adaptados a los sistema multi-core y de memoria compartida. Estos frameworks proponen que cada core de una CPU ejecute una tarea Map o Reduce de manera concurrente. Las fases Map y Reduce también comparten una estructura de datos común donde se aplica el procesamiento principal. En este trabajo se describen algunas limitaciones de los actuales frameworks para arquitecturas multi-core. En primer lugar, se describe la estructura de datos que se utiliza para mantener todo el archivo de entrada y datos intermedios en la memoria. Los frameworks actuales para arquitecturas multi-core han estado diseñado para mantener todos los datos intermedios en la memoria. Cuando se ejecutan aplicaciones con un gran conjunto de datos de entrada, la memoria disponible se convierte en demasiada pequeña para almacenar todos los datos intermedios del framework, presentando así una grave pérdida de rendimiento. Proponemos un subsistema de gestión de memoria que permite a las estructuras de datos procesar un número ilimitado de datos a través del uso de un mecanismo de spilling en el disco. También implementamos una forma de gestionar el acceso simultáneo al disco por todos los threads que realizan el procesamiento. Por último, se estudia la utilización eficaz de la jerarquía de memoria de los frameworks MapReduce y se propone una nueva implementación de una tarea MapReduce parcial para conjuntos de datos de entrada. El objetivo es hacer un buen uso de la caché, eliminando las referencias a los bloques de datos que ya no están en uso. Nuestra propuesta fue capaz de reducir significativamente el uso de la memoria principal y mejorar el rendimiento global con el aumento del uso de la memoria caché. / The need of analyzing large data sets from many different application fields has fostered the use of simplified programming models like MapReduce. Its current popularity is justified by being a useful abstraction to express data parallel processing and also by effectively hiding synchronization, fault tolerance and load balancing management details from the application developer. MapReduce frameworks have also been ported to multi-core and shared memory computer systems. These frameworks propose to dedicate a different computing CPU core for each map or reduce task to execute them concurrently. Also, Map and Reduce phases share a common data structure where main computations are applied. In this work we describe some limitations of current multi-core MapReduce frameworks. First, we describe the relevance of the data structure used to keep all input and intermediate data in memory. Current multi-core MapReduce frameworks are designed to keep all intermediate data in memory. When executing applications with large data input, the available memory becomes too small to store all framework intermediate data and there is a severe performance loss. We propose a memory management subsystem to allow intermediate data structures the processing of an unlimited amount of data by the use of a disk spilling mechanism. Also, we have implemented a way to manage concurrent access to disk of all threads participating in the computation. Finally, we have studied the effective use of the memory hierarchy by the data structures of the MapReduce frameworks and proposed a new implementation of partial MapReduce tasks to the input data set. The objective is to make a better use of the cache and to eliminate references to data blocks that are no longer in use. Our proposal was able to significantly reduce the main memory usage and improves the overall performance with the increasing of cache memory usage.

Matrix computations lie at the heart of most scientific computational tasks. The solution of linear systems of equations is a very frequent operation in many fields in science, engineering, surveying, physics and others. Other matrix operations occur frequently in many other fields such as pattern recognition and classification, or multimedia applications. Therefore, it is important to perform matrix operations efficiently. The work in this thesis focuses on the efficient execution on commodity processors of matrix operations which arise frequently in different fields.We study some important operations which appear in the solution of real world problems: some sparse and dense linear algebra codes and a classification algorithm. In particular, we focus our attention on the efficient execution of the following operations: sparse Cholesky factorization; dense matrix multiplication; dense Cholesky factorization; and Nearest Neighbor Classification.A lot of research has been conducted on the efficient parallelization of numerical algorithms. However, the efficiency of a parallel algorithm depends ultimately on the performance obtained from the computations performed on each node. The work presented in this thesis focuses on the sequential execution on a single processor.There exists a number of data structures for sparse computations which can be used in order to avoid the storage of and computation on zero elements. We work with a hierarchical data structure known as hypermatrix. A matrix is subdivided recursively an arbitrary number of times. Several pointer matrices are used to store the location ofsubmatrices at each level. The last level consists of data submatrices which are dealt with as dense submatrices. When the block size of this dense submatrices is small, the number of zeros can be greatly reduced. However, the performance obtained from BLAS3 routines drops heavily. Consequently, there is a trade-off in the size of data submatrices used for a sparse Cholesky factorization with the hypermatrix scheme. Our goal is that of reducing the overhead introduced by the unnecessary operation on zeros when a hypermatrix data structure is used to produce a sparse Cholesky factorization. In this work we study several techniques for reducing such overhead in order to obtain high performance.One of our goals is the creation of codes which work efficiently on different platforms when operating on dense matrices. To obtain high performance, the resources offered by the CPU must be properly utilized. At the same time, the memory hierarchy must be exploited to tolerate increasing memory latencies. To achieve the former, we produce inner kernels which use the CPU very efficiently. To achieve the latter, we investigate nonlinear data layouts. Such data formats can contribute to the effective use of the memory system.The use of highly optimized inner kernels is of paramount importance for obtaining efficient numerical algorithms. Often, such kernels are created by hand. However, we want to create efficient inner kernels for a variety of processors using a general approach and avoiding hand-made codification in assembly language. In this work, we present an alternative way to produce efficient kernels automatically, based on a set of simple codes written in a high level language, which can be parameterized at compilation time. The advantage of our method lies in the ability to generate very efficient inner kernels by means of a good compiler. Working on regular codes for small matrices most of the compilers we used in different platforms were creating very efficient inner kernels for matrix multiplication. Using the resulting kernels we have been able to produce high performance sparse and dense linear algebra codes on a variety of platforms.In this work we also show that techniques used in linear algebra codes can be useful in other fields. We present the work we have done in the optimization of the Nearest Neighbor classification focusing on the speed of the classification process.Tuning several codes for different problems and machines can become a heavy and unbearable task. For this reason we have developed an environment for development and automatic benchmarking of codes which is presented in this thesis.As a practical result of this work, we have been able to create efficient codes for several matrix operations on a variety of platforms. Our codes are highly competitive with other state-of-art codes for some problems.

Jacobi equations constitute a set of nonlinear partial differential equations which arise from the implementation in an arbitrary system of coordinates of a Poisson structure defined on a finite-dimensional smooth manifold. Certain skew-symmetric solutions of such equations are investigated in this dissertation. This is done from a twofold perspective including both the determination of new solution families as well as the construction of new global Darboux analyses of Poisson structures. The most general results investigated refer to the case of solutions of arbitrary dimension. The perspective thus obtained is of interest in view of the relatively modest number of solution families of this kind reported in the literature. In addition, the global Darboux analysis of structure matrices deals, in first place, with the global determination of complete sets of functionally independent distinguished invariants, thus providing a global description of the symplectic structure of phase space of any associated Poisson system; and secondly, with the constructive and global determination of the Darboux canonical form. Such kind of analysis is of interest because the construction of the Darboux coordinates is a task only known for a limited sample of Poisson structures and, in addition, the fact of globally performing such reduction improves the scope of Darboux' theorem, which only guarantees in principle the local existence of the Darboux coordinates. In this work, such reductions sometimes make use of time reparametrizations, thus in agreement with the usual definitions of system equivalence. In fact, time reparametrizations play a significant role in the understanding of the conditions under which the Darboux canonical form can be globally implemented, a question also investigated in detail in this dissertation. The implications of such results in connection with integrability issues are also considered in this context. The dissertation is structured as follows. Chapter 1 is devoted to the revision of diverse classical and well-known results that describe the basic framework of the investigation. The original contributions of the thesis are included in Chapters 2 to 4. Finally, the work ends in Chapter 5 with the presentation of some conclusions.