Idempotent and tropical mathematics. Complexity of algorithms and interval analysis
arXiv:1209.1721
Abstract
A very brief introduction to tropical and idempotent mathematics is presented. Tropical mathematics can be treated as a result of a dequantization of the traditional mathematics as the Planck constant tends to zero taking imaginary values. In the framework of idempotent mathematics usually constructions and algorithms are more simple with respect to their traditional analogs. We especially examine algorithms of tropical/idempotent mathematics generated by a collection of basic semiring (or semifield) operations and other "good" operations. Every algorithm of this type has an interval version. The complexity of this interval version coincides with the complexity of the initial algorithm. The interval version of an algorithm of this type gives exact interval estimates for the corresponding output data. Algorithms of linear algebra over idempotent and semirings are examined. In this case, basic algorithms are polynomial as well as their interval versions. This situation is very different from the traditional linear algebra, where basic algorithms are polynomial but the corresponding interval versions are NP-hard and interval estimates are not exact.
arXiv comment26 pages, submitted to the journal "Computers and Mathematics with Applications". arXiv admin note: substantial text overlap with arXiv:1001.4247, arXiv:1005.1247
References in corpus (16)
- Tropical Geometry and its applications
- Duality and separation theorems in idempotent semimodules
- Enumerative tropical algebraic geometry in R2
- Correspondence principle for idempotent calculus and some computer applications
- The Maslov dequantization, idempotent and tropical mathematics: A brief introduction
- Idempotent functional analysis: an algebraic approach
- Interval systems over idempotent semiring
- Exact interval solutions to the discrete Bellman equation and polynomial complexity of problems in interval idempotent linear algebra
- Linear functionals on idempotent spaces: an algebraic approach
- A unifying approach to software and hardware design for scientific calculations and idempotent mathematics
- Idempotent interval analysis and optimization problems
- Idempotent and tropical mathematics and problems of mathematical physics (Volume II)
- Universal algorithms, mathematics of semirings and parallel computations
- The complexity of tropical matrix factorization
- Congruence relations for Shimura varieties associated to some unitary groups
- Approximate rational arithmetics and arbitrary precision computations