Grigori Litvinov

The concept of a universal algorithm is discussed. Examples of this kind of algorithms are presented. Software implementations of such algorithms in C++ type languages are discussed together with means that provide for computations with an arbitrary accuracy. Particular emphasis is placed on universal algorithms of linear algebra over semirings.

A brief introduction into Idempotent Mathematics and an idempotent version of Interval Analysis are presented. Some applications are discussed.

A unifying approach to software and hardware design generated by ideas of Idempotent Mathematics is discussed. The so-called idempotent correspondence principle for algorithms, programs and hardware units is described. A software project based on this approach is presented. Key words: universal algorithms, idempotent calculus, software design, hardware design, object oriented programming

We study idempotent analogs of topological tensor products in the sense of A. Grothendieck. The basic concepts and results are simulated on the algebraic level. This is one of a series of papers on idempotent functional analysis.

Many problems in optimization theory are strongly nonlinear in the traditional sense but possess a hidden linear structure over suitable idempotent semirings. After an overview of `Idempotent Mathematics' with an emphasis on matrix theory, interval analysis over idempotent semirings is developed. The theory is applied to construction of exact interval solutions to the interval discrete stationary Bellman equation. Solution of an interval system is typically NP-hard in the traditional interval linear algebra; in the idempotent case it is polynomial. A generalization to the case of positive semirings is outlined.

A unifying approach to software and hardware design generated by ideas of Idempotent Mathematics is discussed. The so-called idempotent correspondence principle for algorithms, programs and hardware units is described. A software project based on this approach is presented.

This paper is devoted to heuristic aspects of the so-called idempotent calculus. There is a correspondence between important, useful and interesting constructions and results over the field of real (or complex) numbers and similar constructions and results over idempotent semirings in the spirit of N. Bohr's correspondence principle in Quantum Mechanics. Some problems nonlinear in the traditional sense (for example, the Bellman equation and its generalizations) turn out to be linear over a suitable semiring; this linearity considerably simplifies the explicit construction of solutions. The theory is well advanced and includes, in particular, new integration theory, new linear algebra, spectral theory and functional analysis. It has a wide range of applications. Besides a survey of the subject, in this paper the correspondence principle is used to develop an approach to object-oriented software and hardware design for algorithms of idempotent calculus.