Skip to Main content Skip to Navigation

Scaling Algorithms and Tropical Methods in Numerical Matrix Analysis: Application to the Optimal Assignment Problem and to the Accurate Computation of Eigenvalues

Abstract : Tropical 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.
Complete list of metadata

Cited literature [120 references]  Display  Hide  Download
Contributor : Meisam Sharify Connect in order to contact the contributor
Submitted on : Thursday, November 24, 2011 - 2:19:15 PM
Last modification on : Wednesday, March 27, 2019 - 4:08:30 PM
Long-term archiving on: : Saturday, February 25, 2012 - 2:21:22 AM


  • HAL Id : pastel-00643836, version 1



Meisam Sharify. Scaling Algorithms and Tropical Methods in Numerical Matrix Analysis: Application to the Optimal Assignment Problem and to the Accurate Computation of Eigenvalues. Numerical Analysis [math.NA]. Ecole Polytechnique X, 2011. English. ⟨pastel-00643836⟩



Record views


Files downloads