Idempotent algorithm

An algorithm based on the concept of idempotent semi-ring (i.e. a semi-ring with idempotent addition). Let $A$ be an idempotent semi-ring with operations $\oplus$ (addition) and $\odot$ (multiplication) and neutral elements $\mathbf{0}$ and $\mathbf{1}$. It is well-known that discrete versions of the Bellman equation can be treated as linear over idempotent semi-rings. The so-called (finite-dimensional) generalized stationary Bellman equation has the form $$ X = H \odot X \oplus F $$

where $X$, $H$ and $F$ are matrices with elements from $A$ and the corresponding matrix operations are component-wise induced by the operations in $A$; the matrices $H$ and $F$ are given (specified) and it is required to determine $X$ from the equation. For example, standard dynamic programming problems and the well-known shortest path problem correspond to the case $A = \mathbf{R}_{\max} = \mathbf{R} \cup \{-\infty\}$ with the operations $\oplus = {\max}$ (maximum) and $\odot = {+}$ (usual addition), $\mathbf{0} = -\infty$, $\mathbf{1} = 0$ or $A = \mathbf{R}_{\min} = \mathbf{R} \cup \{+\infty\}$ with the operations $\oplus = {\min}$ (minimum) and $\odot = {+}$ (usual addition), $\mathbf{0} = \infty$, $\mathbf{1} = 0$. The well-known maximal width path problem corresponds to the case $A = \mathbf{R} \cup \{-\infty,+\infty\}$ with $\oplus = {\max}$, $\odot = {\min}$, $\mathbf{0} = -\infty$, $\mathbf{1} = +\infty$. The relation closure problem for finite sets corresponds to the Boolean algebra (which is an idempotent semi-ring), etc., see, e.g., [a1]–[a10]. A version of the Gauss elimination method for solving (a1) was presented by S.C. Kleene [a11] in the case of the semi-ring of all languages over a finite alphabet. B.A. Carré [a1] used semi-rings to show that many important problems for graphs can be formulated in a unified manner and can be reduced to solving systems of the type (a1). For example, Bellman's method of solving shortest path problems corresponds to a version of the Jacobi method for solving (a1), whereas Ford's algorithm corresponds to a version of the Gauss–Seidel method. This can be treated as an aspect of the idempotent correspondence principle. For algorithms, this heuristic principle means that "if one has an important and interesting numerical algorithm, then there is a good chance that its semi-ring analogues are important and interesting as well" , [a9], [a10].

In particular, analogues of algorithms from linear algebra are especially important. Note that numerical algorithms for standard infinite-dimensional linear problems over semi-rings (i.e., for problems related to integration, integral operators and transformations, the Hamilton–Jacobi and generalized Bellman equations, cf. Idempotent analysis) deal with the corresponding finite-dimensional (or finite) "linear approximations" . Non-linear algorithms can often be approximated by linear ones. It is well-known that algorithms from linear algebra are convenient for parallel computations (see, e.g. [a12], [a13], [a14]); so, their idempotent analogues accept a parallelization. This is a regular way to use parallel computations for many problems, including basic optimization problems.

A systematic application of the idempotent correspondence principle to computer calculations leads to a unifying approach to software and hardware design [a9], [a10].

The most important and standard numerical algorithms have many hardware realizations in the form of technical devices or special processors. These devices can often be used as prototypes for new hardware units generated by substitution of the usual arithmetic operations by semi-ring analogues. Good and efficient technical ideas and decisions can be transposed from prototypes into new hardware units. The so-called systolic processors are especially convenient for this purpose, see e.g. [a12], [a13], [a14].

Software implementations for universal semi-ring algorithms are more flexible. Program modules can deal with abstract (and variable) operations and data types. Concrete values for these operations and data types can be defined by input data types. For programs written in this manner it is convenient to use special techniques from so-called object-oriented design, see e.g. [a15].

References

[a1]	B.A. Carré, "An algebra for network routing problems" J. Inst. Math. Appl. , 7 (1971) pp. 273–294 DOI 10.1093/imamat/7.3.273 Zbl 0219.90020
[a2]	B.A. Carré, "Graphs and networks" , Clarendon Press and Oxford Univ. Press (1979)
[a3]	M. Gondran, M. Minoux, "Graphes et algorithms" , Ed. Eyrolles (1979; 1988)
[a4]	A.V. Aho, J.E. Hopcroft, J.D. Ullman, "The design and analysis of computer algorithms" , Addison-Wesley (1976)
[a5]	U. Zimmermann, "Linear and combinatorial optimization in ordered algebraic structures" Ann. Discrete Math. , 10 (1981) pp. 1–380
[a6]	R.A. Cuninghame-Green, "Minimax algebra and its applications" Fuzzy Sets and Systems , 41 (1991) pp. 251–267
[a7]	F.L. Baccelli, G. Cohen, G.J. Olsder, J.-P. Quadrat, "Synchronization and linearity: an algebra for discrete event systems" , Wiley (1992)
[a8]	V.N. Kolokoltsov, V.P. Maslov, "Idempotent analysis and applications" , Kluwer Acad. Publ. (1996) (In Russian)
[a9]	G.L. Litvinov, V.P. Maslov, "Correspondence principle for idempotent calculus and some computer applications", Idempotency, J. Gunawardena (ed.), Publ. Isaac Newton Institute 11, Cambridge Univ. Press (1998) ISBN 0-521-55344-X pp.420-443 Zbl 0897.68050
[a10]	G.L. Litvinov, V.P. Maslov, "Idempotent mathematics: correspondence principle and applications" Russian J. Math. Phys. , 4 : 4 (1996) (In Russian)
[a11]	S.C. Kleene, "Representation of events in nerve nets and finite automata" J. McCarthy (ed.) C. Shannon (ed.) , Automata Studies , Princeton Univ. Press (1956) pp. 3–40
[a12]	H.T. Kung, "VLSI algorithms and architectures" , Lecture Notes in Computer Science , 227 , Springer (1986)
[a13]	G. Rote, "A systolic array algorithm for the algebraic path problem" Computing , 34 (1985) pp. 191–219
[a14]	S.G. Sedukhin, "Design and analysis of systolic algorithms for the algebraic path problem" Computers and Artificial Intelligence , 11 (1992) pp. 269–292
[a15]	M. Lorenz, "Object oriented software development: a practical guide" , Prentice-Hall (1993)