View source for Idempotent algorithm

An algorithm based on the concept of [[Idempotent semi-ring|idempotent semi-ring]] (i.e. a semi-ring with idempotent addition). Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i1100101.png" /> be an idempotent semi-ring with operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i1100102.png" /> (addition) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i1100103.png" /> (multiplication) and neutral elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i1100104.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i1100105.png" />. It is well-known that discrete versions of the [[Bellman equation|Bellman equation]] can be treated as linear over idempotent semi-rings. The so-called (finite-dimensional) generalized stationary Bellman equation has the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i1100106.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i1100107.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i1100108.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i1100109.png" /> are matrices with elements from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i11001010.png" /> and the corresponding matrix operations are component-wise induced by the operations in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i11001011.png" />; the matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i11001012.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i11001013.png" /> are given (specified) and it is necessary to determine <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i11001014.png" /> from the equation. For example, standard [[Dynamic programming|dynamic programming]] problems and the well-known shortest path problem correspond to the case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i11001015.png" /> with the operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i11001016.png" /> (maximum) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i11001017.png" /> (usual addition), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i11001018.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i11001019.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i11001020.png" /> with the operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i11001021.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i11001022.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i11001023.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i11001024.png" />. The well-known maximal width path problem corresponds to the case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i11001025.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i11001026.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i11001027.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i11001028.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110010/i11001029.png" />. The relation closure problem for finite sets corresponds to the [[Boolean algebra|Boolean algebra]] (which is an idempotent semi-ring), etc., see, e.g., [[#References|[a1]]]–[[#References|[a10]]]. A version of the Gauss elimination method for solving (a1) was presented by S.C. Kleene [[#References|[a11]]] in the case of the semi-ring of all languages over a finite alphabet. B.A. Carré [[#References|[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|Jacobi method]] for solving (a1), whereas Ford's algorithm corresponds to a version of the Gauss–Seidel method (cf. also [[Seidel method|Seidel method]]). This can be treated as an aspect of the [[Idempotent correspondence principle|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" , [[#References|[a9]]], [[#References|[a10]]].

In particular, analogues of algorithms from [[Linear-algebra(2)|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|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. [[#References|[a12]]], [[#References|[a13]]], [[#References|[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 [[#References|[a9]]], [[#References|[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. [[#References|[a12]]], [[#References|[a13]]], [[#References|[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. [[#References|[a15]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  B.A. Carré,   "An algebra for network routing problems"  ''J. Inst. Math. Appl.'' , '''7'''  (1971)  pp. 273–294</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  B.A. Carré,   "Graphs and networks" , Clarendon Press and Oxford Univ. Press  (1979)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  M. Gondran,   M. Minoux,   "Graphes et algorithms" , Ed. Eyrolles  (1979; 1988)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A.V. Aho,   J.E. Hopcroft,   J.D. Ullman,   "The design and analysis of computer algorithms" , Addison-Wesley  (1976)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  U. Zimmermann,   "Linear and combinatorial optimization in ordered algebraic structures"  ''Ann. Discrete Math.'' , '''10'''  (1981)  pp. 1–380</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  R.A. Cuningham-Green,   "Minimax algebra and its applications"  ''Fuzzy Sets and Systems'' , '''41'''  (1991)  pp. 251–267</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  F.L. Baccelli,   G. Cohen,   G.J. Olsder,   J.-P. Quadrat,   "Synchronization and linearity: an algebra for discrete event systems" , Wiley  (1992)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  V.N. Kolokoltsov,   V.P. Maslov,   "Idempotent analysis and applications" , Kluwer Acad. Publ.  (1996)  (In Russian)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  G.L. Litvinov,   V.P. Maslov,   "Correspondence principle for idempotent calculus and some computer applications"  J. Gunawardena (ed.) , ''Idempotency'' , ''Publ. I. Newton Institute'' , Cambridge Univ. Press  (to appear)</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  G.L. Litvinov,   V.P. Maslov,   "Idempotent mathematics: correspondence principle and applications"  ''Russian J. Math. Phys.'' , '''4''' :  4  (1996)  (In Russian)</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  H.T. Kung,   "VLSI algorithms and architectures" , ''Lecture Notes in Computer Science'' , '''227''' , Springer  (1986)</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  G. Rote,   "A systolic array algorithm for the algebraic path problem"  ''Computing'' , '''34'''  (1985)  pp. 191–219</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  S.G. Sedukhin,   "Design and analysis of systolic algorithms for the algebraic path problem"  ''Computers and Artificial Intelligence'' , '''11'''  (1992)  pp. 269–292</TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top">  M. Lorenz,   "Object oriented software development: a practical guide" , Prentice-Hall  (1993)</TD></TR></table>