1,720,958 research outputs found
Algorithmes de mise à l'échelle et méthodes tropicales en analyse numérique matricielle
No full textTropical algebra, which can be considered as a relatively new field in Mathematics, emerged in several branches of science such as optimization, synchronization of production and transportation, discrete event systems, optimal control, operations research, etc. The first part of this manuscript is devoted to the study of the numerical applications of tropical algebra. We start by considering the classical problem of estimating the roots of a univariate complex polynomial. We prove several new bounds for the modulus of the roots of a polynomial exploiting tropical methods. These results are specially useful when considering polynomials whose coefficients have different orders of magnitude. We next consider the problem of computing the eigenvalues of a matrix polynomial. Here, we introduce a general scaling technique, based on tropical algebra, which applies in particular to the companion form. This scaling is based on the construction of an auxiliary tropical polynomial function, depending only on the norms of the matrices. The roots (non-differentiability points) of this tropical polynomial provide a priori estimates of the modulus of the eigenvalues. This is justified in particular by a new location result, showing that under assumption involving condition numbers, there is one group of large eigenvalues, which have a maximal order of magnitude, given by the largest root of the auxiliary tropical polynomial. A similar result holds for a group of small eigenvalues. We show experimentally that this scaling improves the backward stability of the computations, particularly in situations when the data have various orders of magnitude. We also study the problem of computing the tropical eigenvalues (non-differentiability points of the characteristic polynomial) of a tropical matrix polynomial. From the combinatorial perspective, this problem can be interpreted as finding the maximum weighted matching function in a bipartite graph whose arcs are valued by convex piecewise linear functions. We developed an algorithm which computes the tropical eigenvalues in polynomial time. In the second part of this thesis, we consider the problem of solving very large instances of the optimal assignment problems (so that standard sequential algorithms cannot be used). We propose a new approach exploiting the connection between the optimal assignment problem and the entropy maximization problem. This approach leads to a preprocessing algorithm for the optimal assignment problem which is based on an iterative method that eliminates the entries not belonging to an optimal assignment. We consider two variants of the preprocessing algorithm, one by using the Sinkhorn iteration and the other by using Newton iteration. This preprocessing algorithm can reduce the initial problem to a much smaller problem in terms of memory requirements. We also introduce a new iterative method based on a modification of the Sinkhorn scaling algorithm, in which a deformation parameter is slowly increased We prove that this iterative method, referred to as the deformed-Sinkhorn iteration, converges to a matrix whose nonzero entries are exactly those belonging to the optimal permutations. An estimation of the rate of convergence is also presented.L'Algèbre tropicale peut être considérée comme un domaine relativement nouveau en mathématiques. Elle apparait dans plusieurs domaines telles que l'optimisation, la synchronisation de la production et du transport, les systèmes à événements discrets, le contrôle optimal, la recherche opérationnelle, etc. La première partie de ce manuscrit est consacrée a l'étude des applications de l'algèbre tropicale à l'analyse numérique matricielle. Nous considérons tout d'abord le problème classique de l'estimation des racines d'un polynôme univarié. Nous prouvons plusieurs nouvelles bornes pour la valeur absolue des racines d'un polynôme en exploitant les méthodes tropicales. Ces résultats sont particulièrement utiles lorsque l'on considère des polynômes dont les coefficients ont des ordres de grandeur différents. Nous examinons ensuite le problème du calcul des valeurs propres d'une matrice polynomiale. Ici, nous introduisons une technique de mise à l'échelle générale, basée sur l'algèbre tropicale, qui s'applique en particulier à la forme compagnon. Cette mise à l'échelle est basée sur la construction d'une fonction polynomiale tropicale auxiliaire, ne dépendant que de la norme des matrices. Les raciness (les points de non-différentiabilité) de ce polynôme tropical fournissent une pré-estimation de la valeur absolue des valeurs propres. Ceci se justifie en particulier par un nouveau résultat montrant que sous certaines hypothèses faites sur le conditionnement, il existe un groupe de valeurs propres bornées en norme. L'ordre de grandeur de ces bornes est fourni par la plus grande racine du polynôme tropical auxiliaire. Un résultat similaire est valable pour un groupe de petites valeurs propres. Nous montrons expérimentalement que cette mise à l'échelle améliore la stabilité numérique, en particulier dans des situations où les données ont des ordres de grandeur différents. Nous étudions également le problème du calcul des valeurs propres tropicales (les points de non-différentiabilité du polynôme caractéristique) d'une matrice polynômiale tropicale. Du point de vue combinatoire, ce problème est équivalent à trouver une fonction de couplage: la valeur d'un couplage de poids maximum dans un graphe biparti dont les arcs sont valués par des fonctions convexes et linéaires par morceaux. Nous avons développé un algorithme qui calcule ces valeurs propres tropicales en temps polynomial. Dans la deuxième partie de cette thèse, nous nous intéressons à la résolution de problèmes d'affectation optimale de très grande taille, pour lesquels les algorithms séquentiels classiques ne sont pas efficaces. Nous proposons une nouvelle approche qui exploite le lien entre le problème d'affectation optimale et le problème de maximisation d'entropie. Cette approche conduit à un algorithme de prétraitement pour le problème d'affectation optimale qui est basé sur une méthode itérative qui élimine les entrées n'appartenant pas à une affectation optimale. Nous considérons deux variantes itératives de l'algorithme de prétraitement, l'une utilise la méthode Sinkhorn et l'autre utilise la méthode de Newton. Cet algorithme de prétraitement ramène le problème initial à un problème beaucoup plus petit en termes de besoins en mémoire. Nous introduisons également une nouvelle méthode itérative basée sur une modification de l'algorithme Sinkhorn, dans lequel un paramètre de déformation est lentement augmenté. Nous prouvons que cette méthode itérative(itération de Sinkhorn déformée) converge vers une matrice dont les entrées non nulles sont exactement celles qui appartiennent aux permutations optimales. Une estimation du taux de convergence est également présentée
Algorithmes de mise à l'échelle et méthodes tropicales en analyse numérique matricielle
No full textL'Algèbre tropicale peut être considérée comme un domaine relativement nouveau en mathématiques. Elle apparait dans plusieurs domaines telles que l'optimisation, la synchronisation de la production et du transport, les systèmes à événements discrets, le contrôle optimal, la recherche opérationnelle, etc. La première partie de ce manuscrit est consacrée a l'étude des applications de l'algèbre tropicale à l'analyse numérique matricielle. Nous considérons tout d'abord le problème classique de l'estimation des racines d'un polynôme univarié. Nous prouvons plusieurs nouvelles bornes pour la valeur absolue des racines d'un polynôme en exploitant les méthodes tropicales. Ces résultats sont particulièrement utiles lorsque l'on considère des polynômes dont les coefficients ont des ordres de grandeur différents. Nous examinons ensuite le problème du calcul des valeurs propres d'une matrice polynomiale. Ici, nous introduisons une technique de mise à l'échelle générale, basée sur l'algèbre tropicale, qui s'applique en particulier à la forme compagnon. Cette mise à l'échelle est basée sur la construction d'une fonction polynomiale tropicale auxiliaire, ne dépendant que de la norme des matrices. Les raciness (les points de non-différentiabilité) de ce polynôme tropical fournissent une pré-estimation de la valeur absolue des valeurs propres. Ceci se justifie en particulier par un nouveau résultat montrant que sous certaines hypothèses faites sur le conditionnement, il existe un groupe de valeurs propres bornées en norme. L'ordre de grandeur de ces bornes est fourni par la plus grande racine du polynôme tropical auxiliaire. Un résultat similaire est valable pour un groupe de petites valeurs propres. Nous montrons expérimentalement que cette mise à l'échelle améliore la stabilité numérique, en particulier dans des situations où les données ont des ordres de grandeur différents. Nous étudions également le problème du calcul des valeurs propres tropicales (les points de non-différentiabilité du polynôme caractéristique) d'une matrice polynômiale tropicale. Du point de vue combinatoire, ce problème est équivalent à trouver une fonction de couplage: la valeur d'un couplage de poids maximum dans un graphe biparti dont les arcs sont valués par des fonctions convexes et linéaires par morceaux. Nous avons développé un algorithme qui calcule ces valeurs propres tropicales en temps polynomial. Dans la deuxième partie de cette thèse, nous nous intéressons à la résolution de problèmes d'affectation optimale de très grande taille, pour lesquels les algorithms séquentiels classiques ne sont pas efficaces. Nous proposons une nouvelle approche qui exploite le lien entre le problème d'affectation optimale et le problème de maximisation d'entropie. Cette approche conduit à un algorithme de prétraitement pour le problème d'affectation optimale qui est basé sur une méthode itérative qui élimine les entrées n'appartenant pas à une affectation optimale. Nous considérons deux variantes itératives de l'algorithme de prétraitement, l'une utilise la méthode Sinkhorn et l'autre utilise la méthode de Newton. Cet algorithme de prétraitement ramène le problème initial à un problème beaucoup plus petit en termes de besoins en mémoire. Nous introduisons également une nouvelle méthode itérative basée sur une modification de l'algorithme Sinkhorn, dans lequel un paramètre de déformation est lentement augmenté. Nous prouvons que cette méthode itérative(itération de Sinkhorn déformée) converge vers une matrice dont les entrées non nulles sont exactement celles qui appartiennent aux permutations optimales. Une estimation du taux de convergence est également présentéeTropical algebra, which can be considered as a relatively new field in Mathematics, emerged in several branches of science such as optimization, synchronization of production and transportation, discrete event systems, optimal control, operations research, etc. The first part of this manuscript is devoted to the study of the numerical applications of tropical algebra. We start by considering the classical problem of estimating the roots of a univariate complex polynomial. We prove several new bounds for the modulus of the roots of a polynomial exploiting tropical methods. These results are specially useful when considering polynomials whose coefficients have different orders of magnitude. We next consider the problem of computing the eigenvalues of a matrix polynomial. Here, we introduce a general scaling technique, based on tropical algebra, which applies in particular to the companion form. This scaling is based on the construction of an auxiliary tropical polynomial function, depending only on the norms of the matrices. The roots (non-differentiability points) of this tropical polynomial provide a priori estimates of the modulus of the eigenvalues. This is justified in particular by a new location result, showing that under assumption involving condition numbers, there is one group of large eigenvalues, which have a maximal order of magnitude, given by the largest root of the auxiliary tropical polynomial. A similar result holds for a group of small eigenvalues. We show experimentally that this scaling improves the backward stability of the computations, particularly in situations when the data have various orders of magnitude. We also study the problem of computing the tropical eigenvalues (non-differentiability points of the characteristic polynomial) of a tropical matrix polynomial. From the combinatorial perspective, this problem can be interpreted as finding the maximum weighted matching function in a bipartite graph whose arcs are valued by convex piecewise linear functions. We developed an algorithm which computes the tropical eigenvalues in polynomial time. In the second part of this thesis, we consider the problem of solving very large instances of the optimal assignment problems (so that standard sequential algorithms cannot be used). We propose a new approach exploiting the connection between the optimal assignment problem and the entropy maximization problem. This approach leads to a preprocessing algorithm for the optimal assignment problem which is based on an iterative method that eliminates the entries not belonging to an optimal assignment. We consider two variants of the preprocessing algorithm, one by using the Sinkhorn iteration and the other by using Newton iteration. This preprocessing algorithm can reduce the initial problem to a much smaller problem in terms of memory requirements. We also introduce a new iterative method based on a modification of the Sinkhorn scaling algorithm, in which a deformation parameter is slowly increased We prove that this iterative method, referred to as the deformed-Sinkhorn iteration, converges to a matrix whose nonzero entries are exactly those belonging to the optimal permutations. An estimation of the rate of convergence is also presentedPALAISEAU-Polytechnique (914772301) / SudocSudocFranceF
Effect of tropical scaling on linearizations of matrix polynomials: backward error and conditioning
No full textThe \textit{tropical scaling} algorithm
has experimentally shown to generate
accurate results in computing the eigenpairs of a
matrix polynomial P(\l)=\sum_{k=1}^\d \l^k A_k.
This algorithm scales P(\l) by using certain quantities
known as \textit{tropical roots}, then, for each tropical roots,
it constructs a linearization
of the tropically scaled polynomial,
computes its eigenpairs and extracts eigenpairs of P(\l)
from those of the linearizations.
In this work we analyse this algorithm in
terms of backward error and conditioning.
We show that when the tropical roots are well separated,
for an eigenpair,
the backward error of the scale matrix polynomial
is bounded by the backward error of its linearization
times the condition number of certain coefficients of P(\l).
These coefficients determine the abscissae of the nodes of the
{\it Newton polygon} associated with the matrix polynomial.
Similar results show
that for an eigenvalue,
the condition number of the linearization of a scaled matrix polynomial
is bounded by the condition number of the
scaled matrix polynomial times
the condition number of these coefficients.
Our results show that when these coefficients
are well conditioned the eigenpairs can be computed without any numerical difficulty.
These analysis is supported by the experiments which are provided at the end of
the paper
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Get PDFWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Dispelling the Myths Behind First-author Citation Counts
Get PDFWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
- …
