Los sistemas de ecuaciones lineales o problemas de mínimos cuadrados aparecen en un amplio abanico de aplicaciones científico-técnicas. En ocasiones la matriz ligada al problema presenta una estructura banda o bien es una matriz dispersa que puede ser convertida en una matriz banda; en estos casos explotar la estructura banda de la matriz puede reducir considerablemente el coste computacional y de almacenamiento de resolución del problema. El objetivo principal de la presente tesis es el diseño, desarrollo y evaluación de una biblioteca de rutinas para la resolución de sistemas de ecuaciones lineales y problemas de mínimos cuadrados con estructura banda sobre arquitecturas de altas prestaciones. Tras evaluar la eficiencia y funcionalidad de las bibliotecas LAPACK y BLAS para operar con matrices banda, se han propuesto nuevas implementaciones más eficientes para las operaciones contempladas en estas bibliotecas, así como nuevas rutinas que implementan operaciones que amplian su funcionalidad, como por ejemplo una rutina para el cálculo de la factorización QR de una matriz banda. Los nuevos códigos se han aplicado a problemas de resolución de modelos, demostrando su eficiencia y escalabilidad.

The aim of this thesis is to study the hyperinvariant and characteristic subspaces of a matrix, or equivalently, of an endomorphism of a finite dimensional vector space. We restrict ourselves to the case of matrices A with an splitting characteristic polynomial, leaving for future work the generalization for any characteristic polynomial. The subspaces A-hyperinvariant and A-characteristic are subclasses of A-invariant subspaces (those containing its image for A), a key concept in the theory of matrices. Specifically, the subspaces A-hiperinvariant are those that are also invariant for all matrices that commute with A, while the A characteristic are required that are only invariant for invertible matrices that commute with A. Both concepts first appeared in the mid-30s within the context of group theory. But it was not until the 70s that appears a characterization of the A-hiperinvariant subspaces and their lattice was described in the context of matrix theory. In 2009 appears an article of Astuti and Wimmer which shows that A-hyperinvariant and A-caracteristic subspaces are the same except in the field GF(2) . In this case, Shoda theorem gives necessary and sufficient conditions for the existence of characteristic non-hiperinvariant subspaces. But the description of these subspaces was an open problem which is solved in this thesis. Our first objective, therefore, is to analyze the behavior of the centralizer of a matrix (i.e., the set of matrices commuting with it), we will assume canonical form ( Jordan or Weyr). Specifically, we calculate the determinant of the matrices in the centralizer, which in particular allows to characterize the nonsingular. Furthermore, we determined the images of a given subspace respect to the set of all matrices of these centralizers, a result that will be key for further study of hiperinvariant subspaces. We begin this study, giving conditions for the existence of one-dimensional hiperinvariant subspaces. More generally, using the results mentioned in the preceding paragraph, characterized the d-dimensional hyperinvariant subspaces associating to it a trivial Weyr partitions, which in turn allows for easy proof for the associated with certain known Segre partitions (call " hipertuplas''). These characterizations will allow us to explicitly the hiperinvariant subspaces of a given dimension, corresponding to hipertuplas with some fixed coefficient, the latter will be used in the last chapter. In the last part of the thesis, we address to study characteristic non hyperinvariant subspaces, when exist (results of Astuti-Wimmer and Shoda already mentioned). Specifically we give an explicit construction from a type of tuples associated with certain subpartitions of Segre characteristic that call "chartuplas '': to associate each two kinds of subspaces, such that the subspaces are characteristic non-hyperinvariant are precisely direct sums of two of them, one for each class. Finally, from this construction we develop an algorithm to count the number of characteristic non hiperinvariant subspaces. / El objetivo principal de esta tesis es estudiar en profundidad los subespacios hiperinvariantes y característicos de una matriz, o equivalentemente, de un endomorfismo de un espacio vectorial de dimensión finita. Nos restringimos al caso de matrices A con polinomio característico totalmente descomponible, dejando para futuros trabajos la generalización para cualquier polinomio característico. Los subespacios A-hiperinvariantes y A-característicos son subclases de los subespacios A-invariantes (aquellos que contienen su imágen por A), concepto clave en la teoría de matrices. Concretamente, los subespacios A-hiperinvariantes son aquellos que también son invariantes para toda matriz que conmuta con A, mientras que a los A-característicos se les exige sólo que lo sean para las matrices inversibles que conmutan con A. Ambos conceptos aparecen por primera vez a mediados de los años 30 dentro del contexto de la teoría de grupos. Pero no es hasta los años 70 en que se da una caracterización de los subespacios A-hiperinvariantes y se describe su retículo dentro de la teoría de matrices. En el año 2009 aparece un artículo de Astuti y Wimmer donde se demuestra que en el caso de matrices A con polinomio característico totalmente descomponible, los subespacios característicos coinciden con los hiperinvariantes excepto si los coeficientes de A pertenecen a GF(2). En este casos, el Teorema de Shoda da condiciones necesarias y suficientes para la existencia de subespacios característicos no hiperinvariantes. Pero la descripción de este tipo de subespacios era un problema abierto que resolvemos en esta tesis. Nuestro primer objetivo, por tanto, será analizar el comportamiento del centralizador de una matriz, (esto es, el conjunto de matrices que conmutan con ella), que supondremos en forma canónica (de Jordan o de Weyr). Concretamente, calculamos el determinante de las matrices de dichos centralizadores, lo que en particular, permite caracterizar las no singulares. Por otra parte, determinamos las imágenes de un subespacio vectorial dado respecto al conjunto de todas las matrices de dichos centralizadores, resultado que será clave para el posterior estudio de los subespacios hiperinvariantes. Empezaremos dicho estudio, determinando condiciones para la existencia de subespacios hiperinvariantes 1-dimensionales . Más en general, usando los resultados mencionados en el párrafo anterior, caracterizamos los subespacios hiperinvariantes d-dimensionales asociándolos a las particiones triviales de la de Weyr, lo cual a su vez, permite una fácil demostración de la ya conocida asociada a ciertas particiones compatibles con la de Segre (que llamaremos "hipertuplas''). Estas caracterizaciones nos van a permitir contar explícitamente los subespacios hiperinvariantes de una dimensión dada, o los correspondientes a hipertuplas con algunos coeficientes prefijados, los cuales serán utilizados en el último capítulo. En la última parte de la tesis, abordamos el problema abierto de estudiar los subespacios característicos que no son hiperinvariantes, cuando existen (resultados de Astuti-Wimmer y Shoda ya mencionados). Concretamente damos una construcción explícita a partir de un tipo de tuplas asociadas a ciertas subparticiones de la característica de Segre, que llamaremos "chartuplas'': a cada una de ellas asociamos dos clases de subespacios, de forma que los subespacios característicos no hiperinvariantes son precisamente las sumas directas de dos de ellos, uno de cada clase. Finalmente, a partir de esta construcción desarrollamos un algoritmo que permite contar explicitamente el número de subespacios característicos no hiperinvariantes.

Cotutela Universitat Politècnica de Catalunya i Université Mohammed V-Agdal / Information is such a valuable good of our time. Given that the transmission of information has always been subject to precision problems, knowing the obstacles existing between the transmitter and the receiver, eventual disruptions can happen anywhere in between, the physical means, channels involved with the exchange are never perfect and they are subject to errors that might result in loss of important data. Error correcting codes are a key element in the transmission and storage of digital information. In this thesis we study the possibility to redefine and improve properties of convolutional codes in terms of coding and decoding, with the help of the systems and control theory. For that matter, in chapter 1, we recall notions on coding theory, more specifically, on linear codes, both block and convolutional, redefining the convolutional codes as submodules of the F^n_{q} which is our main workspace. And we go through the prerequisites involved in the process of encoding and decoding, both for block and convolutional codes. And in order to approach them with tools of the systems theory, in chapter 2, we give the equivalence of the generating matrix in the form of a realization (A,B,C,D) of an input-output system. Then, we studied the concatenation because it has been proved to improve the transmission. In this work, we consider two big families of concatenation: serial concatenation, and parallel concatenation and two other models of concatenation called systematic serial concatenation and parallel interleaver concatenation. In chapter 3, we study control properties for each case. Nevertheless, we focus on the property of output-observability, and conditions to obtain it, particularly an easy iterative test is presented in order to discuss whether a code is output-observable. This test consists in calculating certain ranks of block matrices constructed from the matrices A, B, C, D. The output-observability property is very beneficial for the decoding as discussed in the next chapter. Moreover, in chapter 4, we assess two methods for a complete decoding operating on an iterative fashion, then suggest conditions for a step by step decoding in a case of concatenation, in order to recover exactly each and every original sequence after operation of every implied code. Following this concept, we study the convolutional decoding in general, and in particular the one of concatenated models in serial, in parallel, in systematic serial and finally in interleaver parallel implementation. In chapter 5, we suggest an application in steganography, in which we implement a steganographic scheme, inspired by the linear system representation of convolutional codes. Having the output-observability matrix being the backbone behind the construction of our decoding algorithms, coupled with the syndrome method, we formed some embedding/retrieval algorithms inspired by that construction. Those methods display the protection of communication within time-related transfer of information, with interesting possibilities and results. Finally, a chapter summarizing all our achievements and a short list of possible future lines of work upon aspects that we would like to continue studying in order to achieve new related goals. / La información es un valioso bien de nuestro tiempo. Dado que la transmisión de la información siempre ha estado sujeta a problemas de precisión, conociendo los obstáculos existentes entre el transmisor y el receptor, las interrupciones eventuales pueden ocurrir en cualquier lugar en el medio, el medio físico, canal involucrado con el cambio nunca es perfecto y está sujeto a errores que podrán dar como resultado una pérdida de datos importantes. Dado que los códigos correctores de errores son un elemento clave en la transmisión y almacenamiento de información digital, por eso un más fácil y mejor uso abre interesantes oportunidades en la regulación de la transmisión de la información, el cual es una ventaja que ofrece la teoría de sistemas lineales y el álgebra lineal a la definición de los códigos de convolución. Esta es la razón por la que en esta tesis, seguimos esa perspectiva para estudiar la posibilidad de redefinir y mejorar las propiedades de los códigos de convolución en base a la codificación y descodificación, con la ayuda de los sistemas y la teoría de control. En este sentido, en el capítulo 1, recordamos nociones sobre la teoría de códigos, más específicamente, sobre los códigos lineales, tanto de bloques como de convolución, se redefinen los códigos convolucionales como submódulos de Fnq que es nuestro espacio principal de trabajo. Y damos un repaso a los requisitos previos necesarios en el proceso de codificación y descodificación, tanto para los códigos de bloque como los códigos convolucionales. Y con el fin de aproximarnos a los códigos convolucionales con las herramientas de la teoría de sistemas, en el capítulo 2, damos la equivalencia de la matriz generatriz en función de una realización (A;B;C;D) de un sistema de entrada-salida. A continuación, se estudia la concatenación porque es conocido que mejora la transmisión. En este trabajo, se consideran dos grandes familias de concatenación: la concatenación en serie, y la concatenación en paralelo así como otros dos modelos de concatenación llamados concatenación en serie sistemática y la concatenación en paralelo con intercalador. En el capítulo 3, estudiamos propiedades de control para cada caso. Sin embargo, nos hemos centrado en la propiedad de “funcional output-controlabilidad" que en lenguaje de teoría de códigos es conocido como “output-observabilidad", y en obtener condiciones que aseguren dicha condición, en particular se presenta un fácil test iterativo, que permite discutir cuando un código de convolución es output-observable. Este test consiste en calcular los rangos de ciertas matrices por bloques construidas a partir de las matrices A, B, C, D. La propiedad de output-observabilidad es muy útil para la descodificación que se estudia en el próximo capítulo. Por otra parte, en el capítulo 4, se presentan dos métodos para una completa descodificación operando de forma iterativa, a partir de ahí, se sugieren condiciones para paso a paso descodificar la concatenación, a fin de recuperar exactamente todos y cada uno de los códigos implicados en la operación. Siguiendo esta idea, se estudia la descodificación de los códigos convolucionales en general, y en particular la de los modelos concatenados en serie, en paralelo, en serie sistemática y finalmente la concatenación en paralelo con intercalador. En el capítulo 5, se presenta una aplicación a la esteganografía, en el que se implementa un esquema esteganográfico, inspirado en la representación del sistema lineal de códigos convolucionales. La matriz de output-observabilidad es la columna vertebral que está detrás de la construcción de nuestros algoritmos de descodificación que junto con el método de síndrome, formamos algunos algoritmos Inclusión/recuperación inspirados en esa construcción. Estos métodos muestran la protección de la comunicación dentro de la transferencia relacionada con el tiempo que dura la información, con interesantes posibilidades y resultados. Por último, un capítulo que resume todos nuestros logros, en este caso el desarrollo de un nuevo algoritmo para escribir una realización, los métodos algoritmos para resolver la descodificación de códigos convolucionales. Esta aplicación a los códigos convolucionales de la teoría de sistemas lineales muestra un abanico de oportunidades para explorar, ya que como una aplicación adicional, hemos desarrollado algunos nuevos modelos esteganográficos, basados en la representación de los códigos convolucionales usando la teoría de sistemas lineal, y una corta lista de posibles futuras líneas de trabajo en los aspectos que nos gustaría seguir estudiando para alcanzar nuevas metas relacionadas seguir estudiando para alcanzar nuevas metas relacionadas con este tema. / L'information est un bien de notre époque dont l'importance n'est plus à démontrer. Etant donné que la transmission de l'information a toujours été soumise à des problèmes de précisions, dûs aux obstacles existant entre le transmetteur and le récepteur, d'éventuelles perturbations peuvent arriver n'importe où, entre les canaux physiques, faisant partie du processus d'échange qui n'est jamais parfait et ils peuvent toujours être affectés par des erreurs créant d'importantes pertes d'information. Les codes correcteurs d'erreurs sont un élément clé dans la transmission et la conservation de l'information numérique. Etant donné que les codes correcteurs d'erreurs sont un élément clé dans la transmission et la conservation de l'information digitale, ainsi un meilleur et plus simple usage ouvre des opportunités plus intéressantes dans la régulation de la transmission de l'information, qui est l'avantage que la définition des codes convolutifs suivant la théorie des systèmes linéaires apporte, avec le matériel de l'algèbre linéaire. C'est pour cette raison que dans cette thèse, nous suivons cette perspective pour étudier la perspective d'étudier la possibilité de redéfinir et d'améliorer les propriétés des codes convolutifs en termes de codage et de décodage, grâce aux outils de la théorie des systèmes et de contrôle. A cet effet, dans le chapitre 1, nous rappelons des notions sur la théorie des codes linéaires, les codes en bloc ainsi que les codes convolutifs, redéfinissant les codes convolutifs comme des sous-modules de Fnq qui est notre principal espace de travail. Et c'est ainsi que nous invoquons tous les prérequis nécessaires pour le processus de codage et de décodage, pour ce qui est des codes en bloc, et des codes convolutifs. Et dans le but d'approcher ces derniers grâce aux outils de la théorie des systèmes, dans le chapitre 2, nous donnons l'équivalence de la matrice génératrice sous la forme d'une réalisation (A;B;C;D) d'un un système inputoutput. Ensuite, nous étudions la concaténation parce qu'elle a été prouvée d'améliorer la transmission. Pour cette partie, nous considérons deux grandes familles de concaténation: concaténation en série et en parallèle, ainsi que deux autres modèles de concaténation appelés: concaténation systématique en série et concaténation en parallèle avec interleaver. Dans le chapitre 3, nous étudions les propriétés de contrôle pour chacun des cas. Néanmoins, nous nous concentrons sur la propriété de "functional output controllability" que dans le langage de théorie est appelé "outputobservability", et sur les conditions pour l'obtenir, en particulier un test itératif relativement facile a été présente en vue de discerner les codes output-observables de ceux qui ne le sont pas. Ce test permet de calculer certains rangs de blocs de matrices construits à partir des matrices A, B, C, D. La propriété d'output-observabilité est très bénéfique pour le décodage comme explicite dans le prochain chapitre. De plus, dans le chapitre 4, nous évaluons deux méthodes pour un décodage complet opérant de manière itérative, ensuite suggérons des conditions pour un décodage étape par étape dans un cas de concaténation, en vue de récupérer exactement chacune des séquences d'origine après opération de chacun des codes impliqués. Suivant ce concept, nous _étudions le décodage convolutif en général et en particulier celui des modèles de concaténation en série, en parallèle, en série systématique et finalement en parallèle avec interleaver. Dans le chapitre 5, nous suggérons une application en sténographie, dans laquelle nous implémentons un schéma sténographique, inspiré par la représentation en termes de systèmes linéaires des codes convolutifs. Ayant la matrice d'output-observabilité étant la matrice de référence pour la construction de nos algorithmes de décodage, couplée avec la méthode du syndrome, nous avons proposé quelques algorithmes d'encapsulation et de recouvrement inspirés par cette construction. Ces méthodes montrent la protection de la communication lors des transferts d'information dépendant du temps, avec d'intéressantes possibilités ainsi que des résultats encourageants. Finalement, un chapitre résumant tout ce que nous avons accompli, en l'occurrence la mise sur pied d'un nouvel algorithme pour écrire une réalisation, méthodes et algorithmes pour résoudre le décodage des codes convolutifs. Cette application des systèmes linéaires sur la théorie des codes convolutifs montre un ensemble de possibilités pour nous à explorer, puisque nous avons développé une application de plus, nous avons développé quelques modèles sténographiques, basés sur la représentation des codes convolutifs grâce à la théorie des systèmes linéaires, et une courte liste des futurs possibles axes de travail sur des aspects que nous souhaiterions étudier pour parachever nos buts traitant de problématiques similaires

This thesis presents some contributions in additive combinatorics and arithmetic Ramsey theory. More specifically, it deals with the interaction between combinatorics, number theory and additive combinatorics. This area saw a great improvement with the Szemerédi Regularity Lemma and some of the results that followed. The Regularity Lemma and its consequences have become a widely used tool in graph theory, combinatorics and number theory. Furthermore, its language and point of view has deeply changed the face of additive number theory, a fact universally acknowledged by the Abel award given to Szemerédi in 2012. One of the main reasons for the prize has been Szemerédi's theorem, a result regarding the existence of arbitrarily long arithmetic progressions in dense sets of the integers, the proof of which uses the Regularity Lemma in a key step. One of the earlier consequences of the Regularity Lemma was the Removal Lemma for graphs that was used by Ruzsa and Szemerédi to show Roth theorem, regarding the existence of 3-term arithmetic progressions in dense sets of the integers, in a combinatorial way. The Removal Lemma states that in any graph K with few copies of a subgraph, say a triangle, we can remove few edges from K so that the result contains no copy of the subgraph. This has become a key tool in the applications of the so-called Regularity Method, which has extensive literature in combinatorics, graph theory, number theory and computer science. In 2005 Green introduced a regularity lemma for Abelian groups as well as an algebraic removal lemma. The removal lemma for groups states that, for a given finite Abelian group G, if there are o(|G|^3) solution to x+y+z+t=0 with the variables taking values in S, a subset of G, then we can remove o(|G|) elements from S to make the set S solution-free. The main contributions of this work corresponds to extensions of the removal lemma for groups to either more general contexts, like non-necessary Abelian finite groups, or to linear systems of equations for finite Abelian groups. The main goal is to give a comprehensive and more general framework for many results in additive number theory like Szemerédi Theorem. In particular, we show that the removal lemma for groups by Green can be extended to non-necessary Abelian finite groups. Moreover, we prove a removal lemma for linear systems on finite fields: for every e>0 there exists a d>0 such that if A is a (k x m) linear system of equations with coefficients in a finite field F and the number of solutions to Ax=b, where each variable takes values from a subset Si in F is less than d times |F| raised to m-k, then by removing less than e|F| elements in each Si we can make the resulting sets solution-free, thus solving a conjecture by Green to that respect. Even more, if A is an integer linear system, G is a finite Abelian group, and the determinantal of A and |G| are coprime, then a similar statement holds. Let us mention that the last result allows us to characterize those linear systems where any set S with size proportional to G has a nontrivial solution in S, provided |G| is large enough. This extends the validity of Szmerédi's theorem to finite Abelian groups. These extensions of the removal lemma have been used in arithmetic Ramsey theory to obtain counting results for the number of monochromatic solutions of linear systems. The main result from a work by Frankl, Graham and Rödl in '88 states that the number of monochromatic solutions of regular systems in integer intervals is in fact a positive proportion of the total number of solutions. We give analogous results for solutions in Abelian groups with bounded exponent, for which the main tool in the torsion-free case cannot be applied. Density versions of these counting results are also obtained, in this case with a full characterization.

The present thesis deals with primitives related to the eld of distributed cryptography. First, we study signcryption schemes, which provide at the same time the functionalities of encryption and signature, where the unsigncryption operation is distributed. We consider this primitive from a theoretical point of view and set a security framework for it. Then, we present two signcryption schemes with threshold unsigncryption, with di erent properties. Furthermore, we use their authenticity property to apply them in the development of a di erent primitive: digital signatures with distributed veri cation. The second block of the thesis deals with the primitive of multi-secret sharing schemes. After stating some e ciency limitations of multi-secret sharing schemes in an information-theoretic scenario, we present several multi-secret sharing schemes with provable computational security. Finally, we use the results in multi-secret sharing schemes to generalize the traditional framework of distributed cryptography (with a single policy of authorized subsets) into a multipolicy setting, and we present both a multi-policy distributed decryption scheme and a multi-policy distributed signature scheme. Additionally, we give a short outlook on how to apply the presented multi-secret sharing schemes in the design of other multi-policy cryptosystems, like the signcryption schemes considered in this thesis. For all the schemes proposed throughout the thesis, we follow the same formal structure. After de ning the protocols of the primitive and the corresponding security model, we propose the new scheme and formally prove its security, by showing a reduction to some computationally hard mathematical problem. / Avui en dia les persones estan implicades cada dia més en diferents activitats digitals tant en la seva vida professional com en el seu temps lliure. Molts articles de paper, com diners i tiquets, estan sent reemplaçats més i més per objectes digitals. La criptografia juga un paper crucial en aquesta transformació, perquè proporciona seguretat en la comunicació entre els diferents participants que utilitzen un canal digital. Depenent de la situació específica, alguns requisits de seguretat en la comunicació poden incloure privacitat (o confidencialitat), autenticitat, integritat o no-repudi. En algunes situacions, repartir l'operació secreta entre un grup de participants fa el procés més segur i fiable que quan la informació secreta està centralitzada en un únic participant; la criptografia distribuïda és l’àrea de la criptografia que estudia aquestes situacions. Aquesta tesi tracta de primitives relacionades amb el camp de la criptografia distribuïda. Primer, estudiem esquemes “signcryption”, que ofereixen a la vegada les funcionalitats de xifrat i signatura, on l'operació de “unsigncryption” està distribuïda. Considerem aquesta primitiva des d’un punt de vista teòric i establim un marc de seguretat per ella. Llavors, presentem dos esquemes “signcryption” amb operació de “unsigncryption” determinada per una estructura llindar, cada un amb diferents propietats. A més, utilitzem la seva propietat d’autenticitat per desenvolupar una nova primitiva: signatures digitals amb verificació distribuïda. El segon bloc de la tesi tracta la primitiva dels esquemes de compartició de multi-secrets. Després de demostrar algunes limitacions en l’eficiència dels esquemes de compartició de multi-secrets en un escenari de teoria de la informació, presentem diversos esquemes de compartició de multi-secrets amb seguretat computacional demostrable. Finalment, utilitzem els resultats obtinguts en els esquemes de compartició de multi-secrets per generalitzar el paradigma tradicional de la criptografia distribuïda (amb una única política de subconjunts autoritzats) a un marc multi-política, i presentem un esquema de desxifrat distribuït amb multi-política i un esquema de signatura distribuïda amb multi-política. A més, donem indicacions de com es poden aplicar els nostres esquemes de compartició de multi-secrets en el disseny d’altres criptosistemes amb multi-política, com per exemple els esquemes “signcryption” considerats en aquesta tesi. Per tots els esquemes proposats al llarg d’aquesta tesi, seguim la mateixa estructura formal. Després de definir els protocols de la primitiva primitius i el model de seguretat corresponent, proposem el nou esquema i demostrem formalment la seva seguretat, mitjançant una reducció a algun problema matemàtic computacionalment difícil.

L’àlgebra de Rees R(I) d’un ideal I d’un anell Noetherià local R juga un paper molt important en àlgebra commutativa i geometria algebraica, perquè Proj(R(I)) és l’explosió (blowup) de l’esquema afí Spec(R) al llarg del subesquema Spec(R/I). Fins avui dia, el problema de descriure les equacions de l’àlgebra de Rees d’ideals, així com altres àlgebres relacionades, com ara l’anell graduat associat G(I) o el con de la fibra F(I), s’ha mostrat molt rellevant per tal de comprendre els fenòmens que envolten aquestes àlgebres. Les equacions de l’àlgebra de Rees R(I) són definibles com els elements del nucli Q d’una presentació polinòmica de R(I). Malgrat que aquest nucli pot dependre de la presentació escollida, no és difícil veure que els graus d’un sistema minimal de generadors homogenis de Q no depenen de la presentació. El màxim entre els graus dels generadors homogenis minimals de qualsevol presentació polinòmica, conegut com a tipus de relació, denotat rt(I), dóna una mesura senzilla – i tanmateix útil en molts contextos – de la complexitat de l’àlgebra de Rees. Els ideals tals que rt(I)=1, anomenats ideals de tipus lineal, han sigut intensament estudiats en les darreres dècades i encara avui dia romanen una font de problemes i exemples interessants. En aquest treball encarem el problema de descriure les equacions de R(I) quan l’ideal I és de la forma I=(J,y), on J és un ideal de tipus lineal: d’aquests ideals objecte del nostre estudi en direm ideals de tipus quasi-lineal. Els resultats principals d’aquest treball rauen en dues aproximacions diferents vers el problema. Per una banda, donem una descripció explícita de les equacions dels ideals I de la forma I=(J,y) quan els generadors de J satisfan l’anul·lació d’un cert grup d’homologia de Koszul. Si bé l’anul·lació d’aquesta homologia no implica automàticament que J sigui de tipus lineal, sí n’és una condició molt propera i també ens permet contemplar altres classes d’ideals. El nostre Teorema A ens permet recuperar, unificar i estendre resultats ja coneguts en el context d’ideals de tipus quasi-lineal deguts a Vasconcelos, Huckaba, Trung, Heinzer i Kim. Sigui α: S(I) → R(I) el morfisme graduat canònic des de l’àlgebra simètrica de I vers l’àlgebra de Rees de I. El segon resultat principal d’aquest treball demostra que l’injectivitat d’una sola component graduada de α és condició suficient per a garantir l’injectivitat de la resta de les components graduades inferiors si I és un ideal de tipus quasi-lineal. En particular, el nostre resultat respon afirmativament i de manera parcial a una pregunta formulada per Tchernev. Val a dir que el nostre resultat funciona per a tots els ideals de tipus quasi-lineal i encara per a ideals una mica més generals. Finalment, donem exemples que il·lustren l’abast i les aplicacions de la col·lecció de resultants presentats. L’autor també dóna una col·lecció de càlculs i exemples que motiven presents i futures activitats de recerca. / The Rees algebra R(I) = R[It] of an ideal I of a Noetherian local ring R plays a major role in commutative algebra and in algebraic geometry, since Proj(R(I)) is the blowup of the affine scheme Spec(R) along the closed subscheme Spec(R/I). So far, the problem of describing the equations of Rees algebras of ideals, as well as other related algebras, has shown to be relevant in order to further understand these major algebraic objects. The equations of R(I) arise as the elements in the kernel Q of a symmetric presentation of R(I). While this kernel may differ from one presentation to another, the degrees of a minimal generating set of homogeneous elements are known to be independent from the chosen presentation. The top degree among such generating sets, known as the relation type and denoted by rt(I), is a coarse measurement of the complexity of the underlying Rees algebra which is nonetheless a useful numerical invariant. The ideals I such that rt(I) = 1, known as ideals of linear type, have been intensely studied so far. In this dissertation, we tackle the problem of describing the equations of R(I) for I =(J, y), with J being of linear type, i.e., for ideals of linear type up to one minimal generator. Throughout, such ideals will be referred to as ideals of almost-linear type. The main results of this work stem from two different approaches towards the problem. In Theorem A, we give a full description of the equations of Rees algebras of ideals of the form I = (J,y), with J satisfying an homological vanishing condition. Theorem A permits us to recover and extend well-known results about families of ideals fulfilling the almost-linear type condition due to Vasconelos, Huckaba, Trung, Heinzer and Kim, among others. Let α: S(I)→R(I) be the canonical morphism from the symmetric algebra of I to the Rees algebra of I. In Theorem B, we prove that the injectivity of a single component of α: S(I)→R(I) propagates downwards, provided I is of almost-linear type. In particular, this result gives a partial answer to a question posed by Tchernev. Finally, packs of examples are introduced, which illustrate the scope and applications of each of the results presented. The author also gives a collection of computations and examples which motivate ongoing and future research.

This dissertation formalizes the construction of multi-view 2D shape models from 3D data. We propose several extensions of the well-known Procrustes Analysis (PA) algorithm that allow modeling rigid and non-rigid transformations in an efficient manner. The proposed strategies are successfully tested on faces and human bodies datasets. In human perception applications one can set physical restrictions, such as defining faces and human skeletons as sets of anatomical landmarks or articulated bodies. However, the high variation of facial expressions and human postures from different viewpoints makes problems like face tracking or human pose estimation extremely challenging. The common approach to handle large viewpoint variations is training the models with several labeled images from different viewpoints. However, this approach has several important drawbacks: (1) it is not clear how much it is necessary to enhance the dataset with images from different viewpoints in order to build unbiased 2D models; (2) extending the training set without this evaluation would unnecessarily increase memory and computation requirements to train the models; and (3) obtaining new labeled images from different viewpoints can be a difficult task because of the expensive labeling cost; finally, (4) a non-uniform coverage of the different viewpoints of a person leads to biased 2D models. In this dissertation we propose successive extensions of PA to address these issues. First of all, we introduce Projected Procrustes Analysis (PPA) as a formalization for building multi-view 2D rigid models from 3D datasets. PPA rotates and projects every 3D training shape and builds a multi-view 2D model from this enhanced training set. We also introduce common parameterizations of rotations, as well as mechanisms to uniformly sample the rotation space. We show that uniformly distributed rotations generate unbiased 2D models, while non-uniform rotations lead to models representing some viewpoints better than others. Although PPA has been successful in building multi-view 2D models, it requires an enhanced dataset that increases the computational requirements in space and time. In order to address these PA and PPA drawbacks, we propose Continuous Procrustes Analysis (CPA). CPA extends PPA within a functional analysis framework and constructs multi-view 2D rigid models in an efficient way through integrating all possible rotations in a given domain. We show that CPA models are inherently unbiased because of their integral formulation. However, CPA is not able to capture non-rigid deformations from the dataset. Next, in order to efficiently compute multi-view 2D deformable models from 3D data, we introduce Subspace Procrustes Analysis (SPA). By adding a subspace in the PA formulation, SPA is able to model non-rigid deformations, as well as rigid 3D transformations of the training set. We developed a discrete (DSPA) and continuous (CSPA) formulation to provide a better understanding of the problem, where DSPA samples and CSPA integrates the 3D rotation space. Finally, we illustrate the benefits of our multi-view 2D deformable models in the task of human pose estimation. We first reformulate the problem as feature selection by subspace matching, and propose an efficient approach for this task. Our method is much more efficient than the state-of-the-art feature selection by subspace matching approaches, and it is able to handle larger number of outliers. Next, we show that our multi-view 2D deformable models, combined with the subspace matching method, outperform state-of-the-art methods of human pose estimation. Our approach is more accurate in the joint positions and limb lengths because we use unbiased 2D models trained on 3D Motion Capture datasets. Our models are not biased to any particular point of view and they can successfully reconstruct different non-rigid deformations and viewpoints. Moreover, they are efficient in both learning and test times. / En esta tesis se formaliza la construcción de modelos multivista 2D a partir de datos 3D, a través de varias extensiones del conocido método Procrustes Analysis (PA). Las extensiones propuestas permiten modelar transformaciones rígidas y no rígidas eficientemente, y se han puesto a prueba en bases de datos de caras y cuerpos humanos. Las aplicaciones donde se perciben humanos permiten establecer restricciones físicas, tales como definir caras y esqueletos como conjuntos de puntos anatómicos. Sin embargo, la gran variación que sufren las expresiones faciales y las posturas humanas desde distintos puntos de vista convierten problemas como el seguimiento de caras o la estimación de la postura humana en retos extremadamente complejos. El planteamiento habitual para gestionar grandes variaciones de punto de vista consiste en entrenar los modelos con imágenes etiquetadas tomadas con distintas orientaciones. Sin embargo, este enfoque sufre importantes inconvenientes: (1) no queda claro cuántas imágenes adicionales con distintas orientaciones son necesarias con tal de construir modelos 2D no sesgados por ningún punto de vista; (2) extender el conjunto de datos de entrenamiento sin esta evaluación incrementaría innecesariamente el coste computacional en tiempo y en memoria; (3) obtener nuevas imágenes etiquetadas con distintas orientaciones puede tratarse de una tarea compleja debido al elevado coste del etiquetado manual; finalmente, (4) no cubrir uniformemente los distintos puntos de vista de una persona conduce a modelos sesgados. En esta tesis se proponen sucesivas extensiones de PA para hacer frente a estos problemas. Primero, proponemos Projected Procrustes Analysis (PPA) para formalizar la construcción de modelos rígidos multivista 2D a partir de conjuntos de datos 3D. PPA rota y proyecta cada objeto 3D y construye un modelo 2D a partir de este conjunto de datos enriquecido. También mostramos como rotaciones uniformemente distribuidas generan modelos 2D no sesgados, mientras rotaciones no uniformes conducen a modelos que representan algunos puntos de vista mejor que otros. Aunque PPA construye modelos multivista 2D, necesita un conjunto de entrenamiento enriquecido que incrementa los requisitos computacionales. Para solventar este problema de PA y PPA, proponemos Continuous Procrustes Analysis (CPA). CPA extiende PPA en un marco de análisis funcional y construye modelos rígidos multivista 2D de un modo eficiente, integrando todas las posibles rotaciones en un dominio dado. Mostramos como los modelos generados con CPA son inherentemente no sesgados debido a la formulación integral. Sin embargo, CPA no captura las deformaciones no rígidas de los datos. En consecuencia, proponemos Subspace Procrustes Analysis (SPA) con el objetivo de construir modelos deformables multivista 2D de un modo eficiente a partir de datos 3D. Añadiendo un subespacio a la formulación de PA, SPA es capaz de modelar deformaciones no rígidas, así como transformaciones 3D de los datos. Desarrollamos una formulación discreta (DSPA) y otra continua (CSPA), donde DSPA muestrea y CSPA integra el espacio de rotaciones 3D. Finalmente, ilustramos las ventajas de nuestros modelos deformables multivista 2D en la tarea de estimar la postura humana. Primero reformulamos el problema como una selección de características por subespacio coincidente y proponemos un método para resolver esta tarea eficientemente. Después, mostramos como nuestros modelos multivista 2D, combinados con la selección de características por subespacio coincidente, mejoran el estado del arte de estimación de la pose humana. Nuestro método es más preciso en la posición de las articulaciones y la longitud de las extremidades por el uso de modelos multivista 2D entrenados en bases de datos de captura de movimiento 3D. Nuestros modelos no están sesgados por punto de vista y pueden reconstruir deformaciones rígidas y no rígidas. Además, estos modelos son eficientes tanto en su construcción como en su uso

La simulació numèrica directa (DNS) de fluxos complexes és actualment una utopia per la majoria d'aplicacions industrials ja que els requeriments computacionals son massa elevats. Donat un flux, la diferència entre els recursos computacionals necessaris i els disponibles és cobreix mitjançant la modelització/simplificació d'alguns termes de les equacions originals que regeixen el seu comportament. El creixement continuat dels recursos computacionals disponibles, principalment en forma de super-ordinadors, contribueix a reduir la part del flux que és necessari aproximar. De totes maneres, obtenir la eficiència esperada dels nous super-ordinadors no és una tasca senzilla i, per aquest motiu, part de la recerca en el camp de la Mecànica de Fluids Computacional es centra en aquest objectiu. En aquest sentit, algunes contribucions s'han presentat en el marc d'aquesta tesis. El primer objectiu va ser el desenvolupament d'un codi de CFD de propòsit general i paral·lel, basat en la metodologia de volums finits en malles no estructurades, per resoldre problemes de multi-física. Aquest codi, anomenat TermoFluids (TF), té un disseny orientat a objectes i pensat per ser usat de forma altament eficient en els super-ordinadors actuals. Amb el temps, ha esdevingut pel grup una eina fonamental en projectes tant de recerca bàsica com d'interès industrial. En el context d'aquesta tesis, el treball s'ha focalitzat en el desenvolupament de dos de les llibreries més bàsiques de TermoFluids: i) La Basics Objects Library (BOL), que es una plataforma de software sobre la qual estan programades la resta de llibreries del codi, i que conté els mètodes algebraics i geomètrics fonamentals per la implementació paral·lela dels algoritmes de discretització, ii) la Linear Solvers Library (LSL), que conté un gran nombre de mètodes per resoldre els sistemes d'equacions lineals derivats de les discretitzacions. El primer capítol d'aquesta tesi conté les principals idees subjacents al disseny i la implementació de la BOL i la LSL, juntament amb alguns exemples i algunes aplicacions industrials. En els capítols posteriors hi ha una explicació detallada de solvers específics per algunes aplicacions concretes. En el segon capítol, es presenta un solver paral·lel i directe per la resolució de l'equació de Poisson per casos en els quals una de les direccions del domini té condicions d'homogeneïtat. En la simulació de fluxos incompressibles, l'equació de Poisson es resol almenys una vegada en cada pas de temps, convertint-se en una de les parts més costoses i difícils de paral·lelitzar del codi. El mètode que proposem és una combinació d'una descomposició directa de Schur (DDS) i una diagonalització de Fourier. La darrera descompon el sistema original en un conjunt de sub-sistemes 2D independents que es resolen mitjançant l'algorisme DDS. Atès que no s'imposen restriccions a les direccions no periòdiques del domini, aquest mètode és aplicable a la resolució de problemes discretitzats mitjançat l'extrusió de malles 2D no estructurades. L'escalabilitat d'aquest mètode ha estat provada amb èxit amb un màxim de 8192 CPU per malles de fins a ~10⁹ volums de control. En el darrer capitol capítol, es presenta un mètode de resolució per l'equació de Transport de Boltzmann (BTE). La estratègia emprada es basa en el mètode d'Ordenades Discretes i pot ser aplicat en discretitzacions no estructurades. El flux per a cada ordenada angular es resol amb un mètode de substitució equivalent a la resolució d'un sistema lineal triangular. La naturalesa seqüencial d'aquest procés fa de la paral·lelització de l'algoritme el principal repte. Diversos algorismes de substitució han estat analitzats, esdevenint una de les heurístiques proposades la millor opció en totes les situacions analitzades, amb excel·lents resultats. Els testos d'eficiència paral·lela s'han realitzat usant fins a 2560 CPU. / Direct Numerical Simulation (DNS) of complex flows is currently an utopia for most of industrial applications because computational requirements are too high. For a given flow, the gap between the required and the available computing resources is covered by modeling/simplifying of some terms of the original equations. On the other hand, the continuous growth of the computing power of modern supercomputers contributes to reduce this gap, reducing hence the unresolved physics that need to be attempted with approximated models. This growth, widely relies on parallel computing technologies. However, getting the expected performance from new complex computing systems is becoming more and more difficult, and therefore part of the CFD research is focused on this goal. Regarding to it, some contributions are presented in this thesis. The first objective was to contribute to the development of a general purpose multi-physics CFD code. referred to as TermoFluids (TF). TF is programmed following the object oriented paradigm and designed to run in modern parallel computing systems. It is also intensively involved in many different projects ranging from basic research to industry applications. Besides, one of the strengths of TF is its good parallel performance demonstrated in several supercomputers. In the context of this thesis, the work was focused on the development of two of the most basic libraries that compose TF: I) the Basic Objects Library (BOL), which is a parallel unstructured CFD application programming interface, on the top of which the rest of libraries that compose TF are written, ii) the Linear Solvers Library (LSL) containing many different algorithms to solve the linear systems arising from the discretization of the equations. The first chapter of this thesis contains the main ideas underlying the design and the implementation of the BOL and LSL libraries, together with some examples and some industrial applications. A detailed description of some application-specific linear solvers included in the LSL is carried out in the following chapters. In the second chapter, a parallel direct Poisson solver restricted to problems with one uniform periodic direction is presented. The Poisson equation is solved, at least, once per time-step when modeling incompressible flows, becoming one of the most time consuming and difficult to parallelize parts of the code. The solver here proposed is a combination of a direct Schur-complement based decomposition (DSD) and a Fourier diagonalization. The latter decomposes the original system into a set of mutually independent 2D sub-systems which are solved by means of the DSD algorithm. Since no restrictions are imposed in the non-periodic directions, the overall algorithm is well-suited for solving problems discretized on extruded 2D unstructured meshes. The scalability of the solver has been successfully tested using up to 8192 CPU cores for meshes with up to 10 9 grid points. In the last chapter, a solver for the Boltzmann Transport Equation (BTE) is presented. It can be used to solve radiation phenomena interacting with flows. The solver is based on the Discrete Ordinates Method and can be applied to unstructured discretizations. The flux for each angular ordinate is swept across the computational grid, within a source iteration loop that accounts for the coupling between the different ordinates. The sequential nature of the sweep process makes the parallelization of the overall algorithm the most challenging aspect. Several parallel sweep algorithms, which represent different options of interleaving communications and calculations, are analyzed. One of the heuristics proposed consistently stands out as the best option in all the situations analyzed. With this algorithm, good scalability results have been achieved regarding both weak and strong speedup tests with up to 2560 CPUs.

Aquesta tesi doctoral tracta de l’estructura algebraica anomenada braça no commutativa per l’esquerra, i de les seves aplicacions a les solucions conjuntistes no degenerades de l’equació de Yang-Baxter. Concretament, estudiem els següents problemes: (1) Construïm totes les solucions conjuntistes no-degenerades associades a una braça per l’esquerra no commutativa donada. A més, demostrem que totes les solucions no-degenerades involutives es poden construir a partir de braces per l’esquerra amb una construcció similar. Aquests resultats estan continguts als Capítols 2 i 3. Això redueix el problema de la classificació de solucions conjuntistes no-degenerades de l’equació de Yang-Baxter a la classificació de braces per l’esquerra no commutatives, un problema que tractem d’estudiar a la resta de la tesi. (2) A la Secció 4.1, presentem dos mètodes nous per a construir braces per l’esquerra: extensions de braces per l’esquerra per ideals trivials, i matched product de braces. Aquestes construccions estan basades en les construccions anàlogues en grups. (3) Motivats per les extensions de braces, a la Secció 4.2 construïm la primera família de braces per l’esquerra simples no trivials. Per a aconseguir-ho, fem servir la construcció de matched products que havíem definit prèviament. (4) Responent a una pregunta de Cedó, Jespers i del Río, trobem el primer exemple de p-grup finit que no és grup multiplicatiu d’una braça per l’esquerra. Això demostra que no tot grup finit resoluble és grup multiplicatiu d’una braça per l’esquerra. Aquest resultat es troba a la Secció 4.3. (5) Finalment, classifiquem totes les braces per l’esquerra d’ordre p, p^2 i p^3, on p és un primer. Aquest resultat es troba contingut a la Secció 4.4 i al Capítol 5. / This PhD thesis deals with the algebraic structure called non-commutative left brace, and with its applications for the non-degenerate set-theoretic solutions of the Yang-Baxter equation. Concretely, we study the following problems: (1) We construct all the non-degenerate set-theoretic solutions of the Yang-Baxter equation associated with a fixed non-commutative left brace. Moreover, we prove all the non-degenerate involutive solutions can be obtained from left braces with an analogous construction. These results are contained in Chapters 2 and 3. This reduces the problem of classification of non-degenerate set-theoretic solutions of the Yang-Baxter equation to the classification of non-commutative left braces, a problem that we study for the rest of the memoir. (2) In Section 4.1, we present two new methods to construct new left braces: extensions of left braces by trivial ideals, and matched product of left braces. These constructions are based on the analogous constructions of group theory. (3) Motivated by the extensions of left braces, in Section 4.2 we construct the first family of non-trivial simple left braces. We use the matched product method that we have defined previously to obtain this family. (4) Answering a question of Cedó, Jespers and del Río, we find the first exemple of finite p-group which is not the multiplicative group of any left brace. This proves that not all finite solvable groups are multiplicative groups of left braces. This results is contained in Section 4.3. (5) Finally, we classify all the left braces of order p, p^2 and p^3, where p is a prime. This result is contained in Section 4.4 and Chapter 5.

No description available.