Dans cette thèse, nous étudions des algorithmes pour un problème de recherche de relations à une ou plusieurs variables. Il généralise celui de calculer une solution à un système d’équations linéaires modulaires sur un anneau de polynômes, et inclut par exemple le calcul d’approximants de Hermite-Padé ou d’interpolants bivariés. Plutôt qu’une seule solution, nous nous attacherons à calculer un ensemble de générateurs possédant de bonnes propriétés. Précisément, l’entrée de notre problème consiste en un module de dimension finie spécifié par l’action des variables sur ses éléments, et en un certain nombre d’éléments de ce module ; il s’agit de calculer une base de Gröbner du modules des relations entre ces éléments. En termes d’algèbre linéaire, l’entrée décrit une matrice avec une structure de type Krylov, et il s’agit de calculer sous forme compacte une base du noyau de cette matrice. Nous proposons plusieurs algorithmes en fonction de la forme des matrices de multiplication qui représentent l’action des variables. Dans le cas d’une matrice de Jordan,nous accélérons le calcul d’interpolants multivariés sous certaines contraintes de degré ; nos résultats pour une forme de Frobenius permettent d’accélérer le calcul de formes normales de matrices polynomiales univariées. Enfin, dans le cas de plusieurs matrices denses, nous accélérons le changement d’ordre pour des bases de Gröbner d’idéaux multivariés zéro-dimensionnels. / In this thesis, we study algorithms for a problem of finding relations in one or several variables. It generalizes that of computing a solution to a system of linear modular equations over a polynomial ring, including in particular the computation of Hermite- Padéapproximants and bivariate interpolants. Rather than a single solution, we aim at computing generators of the solution set which have good properties. Precisely, the input of our problem consists of a finite-dimensional module given by the action of the variables on its elements, and of some elements of this module; the goal is to compute a Gröbner basis of the module of syzygies between these elements. In terms of linear algebra, the input describes a matrix with a type of Krylov structure, and the goal is to compute a compact representation of a basis of the nullspace of this matrix. We propose several algorithms in accordance with the structure of the multiplication matrices which specify the action of the variables. In the case of a Jordan matrix, we accelerate the computation of multivariate interpolants under degree constraints; our result for a Frobenius matrix leads to a faster algorithm for computing normal forms of univariate polynomial matrices. In the case of several dense matrices, we accelerate the change of monomial order for Gröbner bases of multivariate zero-dimensional ideals.

The main objective of this dissertation is to present an algebraic method capable of determining a solution, if any, of a non linear polynomial equation systems using Gröbner basis. In order to accomplish that, we first present some concepts and theorems linked to polynomial rings with several undetermined and monomial ideals where we highlight the division extended algorithm, the Hilbert Basis and the Buchberger´s algorithm. Beyond that, using basics of Elimination and Extension Theorems, we present an algebraic solution to the map coloring that use 3 colors as well as a general solution to the Sudoku puzzle. / O objetivo principal desse trabalho é, usando bases de Gröbner, apresentar um método algébrico capaz de determinar a solução, quando existir, de sistemas de equações polinomiais não necessariamente lineares. Para tanto, necessitamos inicialmente apresentar alguns conceitos e teoremas ligados a anéis de polinômios com várias indeterminadas e de ideais monomiais, dentre os quais destacamos o algoritmo extendido da divisão, o teorema da Base de Hilbert e o algoritmo de Buchberger. Além disso, usando noções básicas da Teoria de eliminação e extensão, apresentamos uma solução algébrica para o problema da coloração de mapas usando três cores, bem como um solução geral para o puzzle Sudoku.

本論文は,様々なネットワーク最適化問題の数学的構造について様々な観点から調べたものである.主たる結果はネットワーク最適化問題の代表例である最大流問題に,関するいくつかの結果と,Min-Plus代数に値をもつ行列の固有値と固有ベクトルに関する特徴づけに関する結果からなっている. / 博士(理学) / Doctor of Philosophy in Science / 同志社大学 / Doshisha University

[ES] Uno de los elementos más importantes en el sistema de control de un robot es su Modelo Cinemático Inverso (IKM, por sus siglas en inglés), el cual calcula las referencias de posición y velocidad requeridas para que dicho robot pueda seguir una trayectoria. Los métodos más comúnmente empleados para la síntesis del IKM de sistemas robotizados de cadena cinemática abierta dependen fuertemente de la geometría del robot, por lo que no son procedimientos sistemáticos que puedan ser aplicados uniformemente en todas las situaciones. Este proyecto presenta el desarrollo de un procedimiento sistemático para la síntesis del IKM completo de sistemas robotizados no redundantes de cadena cinemática abierta usando la teoría de Bases de Groebner, el cual no depende de la geometría del robot. Las entradas del procedimiento desarrollado son los parámetros de Denavit-Hartenberg del robot y el rango de movimiento de sus actuadores, mientras que la salida es el IKM sintetizado, listo para ser usado en el sistema de control del robot o en una simulación de su funcionamiento. El desempeño del procedimiento desarrollado fue demostrado sintetizando los IKMs de un manipulador PUMA y un hexápodo caminante. Los tiempos de ejecución de ambos IKMs son comparables con los requeridos por los modelos cinemáticos calculados por procedimientos tradicionales, y los errores de las referencias que ofrecen como salida son totalmente despreciables. Los IKMs sintetizados son completos, porque no sólo ofrecen las referencias de posición para todos los actuadores del robot, sino que también calculan las correspondientes referencias de velocidades y aceleraciones de dichos actuadores, por lo que el procedimiento desarrollado puede ser empleado en una amplia variedad de sistemas robotizados. / [CA] Un dels elements més importants en el sistema de control d'un robot és el seu Model Cinemàtic Invers (IKM, per les seues sigles en anglés), el qual calcula les referències de posició i velocitat requerides perquè aquest robot puga seguir una trajectòria. Els mètodes més comunament emprats per a la síntesi del IKM de sistemes robotitzats de cadena cinemàtica oberta depenen fortament de la geometria del robot analitzat, per la qual cosa no són procediments sistemàtics que puguen ser aplicats uniformement en totes les situacions. Aquest projecte presenta el desenvolupament d'un procediment sistemàtic per a la síntesi del IKM complet de sistemes robotitzats no redundants de cadena cinemàtica oberta usant la teoria de Bases de Groebner, el qual no depén de la geometria del robot. Les entrades del procediment desenvolupat són els paràmetres de Denavit-Hartenberg del robot i el rang de moviment dels seus actuadors, mentre que l'eixida és el IKM sintetitzat, llest per a ser usat en el sistema de control del robot o en una simulació del seu funcionament. L'acompliment del procediment desenvolupat va ser demostrat sintetitzant els IKMs d'un manipulador PUMA i un robot caminante. Els temps d'execució de tots dos IKMs són comparables amb els requerits pels models cinemàtics calculats per procediments tradicionals, i els errors de les referències que ofereixen com a eixida són totalment menyspreables. Els IKMs sintetitzats són complets, perquè no sols ofereixen les referències de posició per a tots els actuadors del robot, sinó que també calculen les corresponents referències de velocitats i acceleracions d'aquests actuadors, per la qual cosa el procediment desenvolupat pot ser emprat en una àmplia varietat de sistemes robotitzats. / [EN] One of the most important elements of a robot's control system is its Inverse Kinematic Model (IKM), which calculates the position and velocity references required by the robot's actuators to follow a trajectory. The methods that are commonly used to synthesize the IKM of open-chain robotic systems strongly depend on the geometry of the analyzed robot, so they are not systematic procedures that can be applied equally in all situations. This project presents the development of a systematic procedure to synthesize the complete IKM of non-redundant open-chain robotic systems using Groebner Basis theory, which does not depend on the robot's geometry. The inputs to the developed procedure are the robot's Denavit-Hartenberg parameters and the movement range of its actuators, while the output is the IKM, ready to be used in the robot's control system or in a simulation of its behavior. This procedure's performance was proved synthesizing the IKMs of a PUMA manipulator and a walking hexapod robot. The computation times of both IKMs are comparable to those required by the kinematic models calculated by traditional methods, while the errors of their computed references were absolutely negligible. The synthesized IKMs are complete in the sense that they not only supply the position reference for all the robot's actuators, but also the corresponding references for their velocities and accelerations, so the developed procedure can be used in a wide range of robotic systems. / Guzmán Giménez, J. (2022). Synthesis of the Complete Inverse Kinematic Model of Non-Redundant Open-Chain Robotic Systems using Groebner Basis Theory [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/181632

No description available.