text:
# Electron-Electron Relaxation Effect on Auger Recombination in Direct Band Semiconductors

## Abstract

Influence of electron-electron relaxation processes on Auger recombination rate in direct band semiconductors is investigated. Comparison between carrier-carrier and carrier-phonon relaxation processes is provided. It is shown that relaxation processes are essential if the free path length of carriers doesn’t exceed a certain critical value, which exponentially increases with temperature. For illustration of obtained results a typical InGaAsP compound is used.

It is well known that the intraband relaxation of carriers plays an important role in recombination processes 7 ; 4 . In particular, relaxation was shown to cause broadening of gain and emission spectra in semiconductor lasers 7 . Influence of relaxation processes on Auger recombination (AR) in bulk semiconductors is more fundamental. Both for the CHCC and for the CHHS processes AR coefficient calculated in the first order of perturbation theory in electron-electron interaction is of the threshold type, being an exponential function of temperature 1 ; 2 . Relaxation eliminates the threshold conditions enhancing AR. Phonon and impurity assisted Auger processes in AIIIBV homogeneous semiconductors were studied in Tak1 ; Tak2 ; Yevick . As shown in 7 , it is the electron (hole)-electron (hole) relaxation mechanism which gives the main contribution to broadening of the light emission spectra in semiconductors with high carrier density. However, influence of this relaxation mechanism on AR has not been studied yet. Since AR dominates over other recombination processes at high densities of electrons and holes and the role of the carrier-carrier scattering also increases with carrier concentration, the corresponding mechanism of relaxation might be expected to be of primary importance in calculating AR rate.

In this paper we study temperature and carrier-density dependences of Auger coefficient with and without regard to electron (hole)-electron (hole) relaxation processes. General Green function approach is used for calculation of AR coefficient. Wave functions and energy spectra of electrons and holes are found from the conventional $`8\times 8`$ $`\mathrm{𝐤𝐩}`$-model. Comparison of the direct AR, phonon-assisted AR, and AR with carrier-carrier relaxation is provided both for the CHCC and CHHS processes.

Finite temperature Green function techniques for calculating AR rate was developed in Tak1 ; Tak2 . The formalism used in those papers is based on linear response and mean-field approximations. It was shown that the relaxation processes eliminate the threshold appearing in the first order of perturbation theory on Coulomb interaction and enhance AR rate. In Tak1 ; Tak2 , there were studied Auger processes with relaxation on phonons and impurities. However, wave functions and overlap integrals were phenomenologically assumed than calculated, which drastically affected the results. The most accurate calculation of the phonon-assisted AR was performed in Yevick . But the heavy hole wave functions were not derived there consistently with those of electrons.

In direct band AIIIBV semiconductors the electron effective mass is usually much less then that of heavy holes 4 . This allows us to neglect by electron scattering processes, compared with those of holes 7 , and to use free particle propagators for the former. By the same reason we also neglect by the momenta and energies of the electrons in the initial state 2 .

Following the approach developed in Tak1 ; Tak2  and using wave functions derived in $`8\times 8`$ model prb  we obtain Auger coefficient for the CHCC process:

$`C`$ $``$ $`{\displaystyle \frac{32\sqrt{2\pi ^5}e^4\mathrm{}^2E_c}{9m_h^{3/2}T^{3/2}E_gϵ_{\mathrm{}}^2}}{\displaystyle \frac{3E_g+2\mathrm{\Delta }_{so}}{E_g+\mathrm{\Delta }_{so}}}{\displaystyle \underset{\mathrm{}}{\overset{\mathrm{}}{}}}{\displaystyle \frac{d}{k_c^2(+E_g)}}{\displaystyle \frac{dk_c}{d}}\mathrm{exp}\left({\displaystyle \frac{}{T}}\right)D(k_c(+E_g),)`$ (1)
Here $`E_c`$ is the mean electron energy equal to $`\frac{3}{2}T`$ if they have Boltzmann distribution, $`m_h`$ is the heavy-hole effective mass, $`T`$ is the temperature in energy units, $`E_g`$ and $`\mathrm{\Delta }_{so}`$ are the band gap and spin-orbital splitting respectively, $`k_c(E)`$ is the wave vector versus energy in the conduction band, $`E_h(k)`$ is the dispersion of the heavy holes, $`D(k,E)`$ is the spectral function related to the imaginary part of the heavy-hole proper self-energy $`\mathrm{\Gamma }(k,E)`$ by

$$D(k,E)=\frac{1}{\pi }\frac{\mathrm{\Gamma }(k,E)}{\left(\mathrm{\Gamma }(k,E)\right)^2+(EE_h(k))^2}.$$
(2)
In (1) we used Boltzmann distribution of heavy holes, which is usually the case due to large value of their effective mass. Generalization of this expression to the case of Fermi statistics is straightforward. The high frequency dielectric constant $`ϵ_{\mathrm{}}`$ is taken away from the integrand because the free-carrier screening effects are weak and unimportant for Auger process 3c . We neglected by the real part of the proper self energy in (2), since its only effect is the slight renormalization of the heavy hole mass. It should be noted, that $`\mathrm{\Gamma }`$ strongly damps in the band gap $`<0`$ and the main contribution to the integral comes from the positive values of the hole energy.

Neglecting by relaxation processes leads to a well known expression for the Auger coefficient 2 ; 3c :

$`C{\displaystyle \frac{8\sqrt{2\pi ^5}e^4\mathrm{}^3E_c}{3m_h^{3/2}m_c^{1/2}T^{3/2}E_g^{5/2}ϵ_{\mathrm{}}^2}}\mathrm{exp}\left({\displaystyle \frac{E_{th}}{T}}\right)F\left({\displaystyle \frac{\mathrm{\Delta }_{so}}{E_g}}\right),`$ (3)
where $`F(x)`$ is a multiplier of the order of $`1`$ 2 :

$$F(\alpha )=\left(\frac{1+\alpha }{1+2\alpha /3}\right)^{3/2}\left(\frac{1+\alpha /3}{1+\alpha /2}\right)^{1/2},$$

$`E_{th}2m_c/m_hE_g`$ is the threshold energy.

Similarly can be obtained the expression for the CHHS Auger process:

$`C={\displaystyle \frac{16\pi ^2e^4\mathrm{}^5}{3ϵ_{\mathrm{}}^2m_h^3T^3}}{\displaystyle \frac{E_c}{E_g}}{\displaystyle \frac{3E_g+2\mathrm{\Delta }_{so}}{3(E_g+\mathrm{\Delta }_{so})}}{\displaystyle \underset{0}{\overset{\mathrm{}}{}}}{\displaystyle \underset{0}{\overset{\mathrm{}}{}}}dk_1dk_2{\displaystyle \underset{1}{\overset{1}{}}}d\mathrm{cos}\vartheta \times `$
$`{\displaystyle \frac{(1+\lambda _{so})^2}{1+2\lambda _{so}^2+\frac{\mathrm{\Delta }_{so}}{E_gE_{so}}\frac{2\lambda _{so}^2+\lambda _{so}1}{3\lambda _{so}}}}{\displaystyle \frac{\mathrm{cos}^2(\vartheta )k_1^2}{(𝐤_1+𝐤_2)^2}}[1+{\displaystyle \frac{k_2}{2k_1}}\mathrm{sin}\vartheta ]\times `$
$`{\displaystyle \underset{\mathrm{}}{\overset{\mathrm{}}{}}}𝑑ED(k_1,E)D(k_2,E_{so}E_gE)\mathrm{exp}\left({\displaystyle \frac{EgE_{so}}{T}}\right),`$ (4)
where $`E_{so}E_{so}(|𝐤_1+𝐤_2|)`$ is the energy of the split-off hole, $`\vartheta `$ is the angle between the wavevectors $`𝐤_1`$ and $`𝐤_2`$,

$$\lambda _{so}=\frac{\mathrm{\Delta }_{so}}{3\left(E_{so}+4/3\mathrm{\Delta }_{so}+\frac{\mathrm{}^2k_{so}^2(E_{so})}{2m_h}\right)}.$$

The presence of the multiplier $`(1+\lambda _{so})^2`$ in the integrand ensures that near the $`\mathrm{\Gamma }`$-point (at the center of Brillouin zone), where $`E_{so}\mathrm{\Delta }_{so}`$ and $`\lambda _{so}1`$, the overlapping between heavy holes and split-off holes vanishes 8 . Note that the exchange interaction term doesn’t vanish for the CHHS process as it does in the case of the CHCC one. Namely, this interaction is responsible for the second term in the square brackets in the integrand of (4). If the spectral functions are substituted by $`\delta `$-functions, (4) turns to the expression derived by Ge’lmont et.al. 8 .

Let us now consider the relaxation processes in detail. In this paper we will study two basic scattering mechanisms in undoped semiconductors: (i) on polar optical phonons and (ii) on electron hole plasma. The imaginary part of the proper self energy for the first mechanism with account of the complex valence band structure is as follows:

$`\mathrm{\Gamma }_{ph}(k,E)={\displaystyle \frac{m_he^2\omega _{lo}}{4\mathrm{}\overline{ϵ}k}}[{\displaystyle \frac{1}{\mathrm{exp}\frac{\mathrm{}\omega _{lo}}{T}1}}\times `$
$`{\displaystyle \underset{(1\mathrm{\Delta }_1)^2}{\overset{(1+\mathrm{\Delta }_1)^2}{}}}{\displaystyle \frac{3(\mathrm{\Delta }_1^2+1\xi )^2+4\mathrm{\Delta }_1^2}{16\mathrm{\Delta }_1^2\xi }}d\xi +{\displaystyle \frac{\mathrm{exp}\frac{\mathrm{}\omega _{lo}}{T}}{\mathrm{exp}\frac{\mathrm{}\omega _{lo}}{T}1}}\times `$
$`{\displaystyle \underset{(1\mathrm{\Delta }_2)^2}{\overset{(1+\mathrm{\Delta }_2)^2}{}}}{\displaystyle \frac{3(\mathrm{\Delta }_2^2+1\xi )^2+4\mathrm{\Delta }_2^2}{16\mathrm{\Delta }_2^2\xi }}d\xi ],`$ (5)
$`\omega _{lo}`$ is the phonon frequency assumed to be independent of the wavevector,

$$\mathrm{\Delta }_{1,2}\mathrm{\Delta }_{1,2}(k,E)=\{\begin{array}{cc}\sqrt{\frac{2m_h(E\mathrm{}\omega _{lo})}{\mathrm{}^2k^2}}& \text{if}E>\pm \mathrm{}\omega _{lo}\hfill \\ 0& \text{otherwise}\hfill \end{array},$$

with indices $`1,2`$ corresponding to upper, lower sign respectively,

$$\frac{1}{\overline{ϵ}}=\frac{1}{ϵ_{\mathrm{}}}\frac{1}{ϵ_0},$$

$`ϵ_0`$ is the low-frequency dielectric constant. The first and the second terms in (5) correspond to phonon absorption and phonon emission, respectively. If screening effects are taken into account than in both terms of (5) $`\xi ^1`$ should be substituted by $`\xi /(\xi +\lambda _{TF}^2/k^2)^2`$ with $`\lambda _{TF}`$ being Thomas-Fermi screening momentum. Integration in (5) can be conducted explicitly however the resulting expression is quite cumbersome. A similar to (5) formula was derived in Yevick , but there is some discrepancy due to more accurate consideration of the heavy-hole spectrum in this paper.

Let us consider the relaxation due to hole scattering on equilibrium electron-hole plasma. Using RPA approach for calculating the imaginary part of the self energy $`\mathrm{\Gamma }_e`$ due to carrier-carrier scattering Fetter  we obtain:

$`\mathrm{\Gamma }_e(k,E)=`$ $`{\displaystyle \frac{me^2}{ϵ_0\pi k}}{\displaystyle \underset{0}{\overset{\mathrm{}}{}}}d{\displaystyle \underset{q_{min}}{\overset{q_{max}}{}}}{\displaystyle \frac{dq}{q}}({\displaystyle \frac{1}{\mathrm{exp}\left(\frac{\mu _v}{T}\right)+1}}+{\displaystyle \frac{1}{\mathrm{exp}\left(\frac{E}{T}\right)1}})\times `$ (6)
$`{\displaystyle \frac{\delta ϵ^{\prime \prime }(q,E)}{(1+\delta ϵ^{}(q,E))^2+\left(\delta ϵ^{\prime \prime }(q,E)\right)^2}}\left[1{\displaystyle \frac{3}{4}}{\displaystyle \frac{(E_h(q)E_h(q_{min}))(E_h(q_{max})E)}{4E_h(k)}}\right],`$
$$q_{min}=\left|\sqrt{\frac{2m_h}{\mathrm{}^2}}k\right|,q_{max}=\sqrt{\frac{2m_h}{\mathrm{}^2}}+k.$$

Here $`\delta ϵ`$ is the contribution to the dielectric constant from free carriers, double prime refers to the imaginary part and single prime does to the real part of $`\delta ϵ`$. The last multiplier in (6) comes from the complex structure of the valence band,

$`\delta ϵ^{\prime \prime }(k,E)={\displaystyle \frac{2m_h^2e^2}{ϵ_0^2k^3}}{\displaystyle \underset{\frac{(E_h(k)E)^2}{4E_h(k)}}{\overset{\mathrm{}}{}}}𝑑E_q(f_h(E_q)f_h(E_q+E))\left[1{\displaystyle \frac{3E_h(k)}{4E_q}}{\displaystyle \frac{E_q\frac{(E_h(k)E)^2}{4E_h(k)}}{E_q+E}}\right],`$ (7)
where

$$f_h(E)=\frac{1}{\mathrm{exp}\left(\frac{E\mu _h}{T}\right)+1}$$

is the heavy hole distribution function. The expression for the real part of $`\delta ϵ`$ is quite complicated 3c . However, as numerical computation shows, Thomas-Fermi approximation gives very reasonable results. So $`\delta ϵ^{\prime \prime }`$ in denominator of (6) can be set zero and

$$\delta ϵ^{}=\lambda _{TF}^2/q^2,$$
(8)
where $`\lambda _{TF}`$ is the inverse Thomas-Fermi screening length Tak1 :

$$\lambda _{TF}=\sqrt{\frac{4\sqrt{2}e^2\sqrt{T}}{\pi \mathrm{}^3ϵ_0}\left(m_h^{3/2}S\left(\frac{\mu _h}{T}\right)+m_c^{3/2}S\left(\frac{\mu _c}{T}\right)\right)},$$
(9)
where

$$S(x)=\underset{0}{\overset{\mathrm{}}{}}𝑑y\frac{1}{\mathrm{exp}(y^2x)+1}.$$

Substituting (7) and (8) into (6) gives the final expression for the lifetime of holes in the case of carrier-carrier scattering.

Imaginary part of the proper self energy $`\mathrm{\Gamma }_e(k,E)`$ strongly depends on both arguments having a steep maximum at $`E_h(k)=E`$ and rapidly decreasing when the latter inequality is broken. There are two main reasons for reducing $`\mathrm{\Gamma }_e`$ when $`E_h(k)E`$: (i) Coulomb interaction is relatively weak at large transferred momenta, (ii) there is an exponentially small number of carriers with large momenta in equilibrium electron-hole plasma. On the other hand, scattering on phonons is almost independent of the transferred momentum and therefore $`\mathrm{\Gamma }_{ph}`$ is a smooth function of its arguments. Figure 1 shows dependences $`\mathrm{\Gamma }_e(k)`$ and $`\mathrm{\Gamma }_{ph}(k)`$ at a fixed value of $`E=0`$. While the value $`\mathrm{\Gamma }_e`$ is larger then that of $`\mathrm{\Gamma }_{ph}`$ at small values of $`k`$ and relatively high carrier densities, the inverse relation could be observed at large $`k`$ or small densities. The role of carrier-carrier scattering obviously increases with carrier density and temperature. In AR, large transferred momenta play a crucial role 2 ; 3c . Therefore the carrier-carrier scattering mechanism is less important here than in radiative recombination. Nevertheless this relaxation process remains effective at high temperatures and carrier densities (Figs. 2-4). Parameters of a typical InGaAsP compound lattice matched to InP were used for the illustration of obtained results.

The threshold energy for the CHCC AR is considerably larger than that for the CHHS process, therefore relaxation processes are important for the former up to very high temperature (Fig. 2), while for the latter they usually give a considerable effect only when $`T`$ is small (Fig. 3). At $`T`$ close to zero phonon-assisted AR predominates, while the role pf AR with carrier-carrier relaxation increases at higher $`T`$ (Fig. 2). The carrier-carrier relaxation mechanism is also responsible for a stronger dependence of AR coefficient on the carrier density (Fig. 4).

In conclusion we note that owing to relaxation processes AR becomes thresholdless, because the restrictions imposed by the energy-momentum conservation are lifted. From (1) we can estimate the characteristic scattering length $`a_c`$ for the CHCC process

$$a_c=\lambda _{Eg}\left(\frac{T}{E_{th}}\right)\mathrm{exp}\left(\frac{E_{th}}{T}\right),$$
(10)
where $`\lambda _{E_g}=2\pi /k_c(E_g)`$. If the free path length $`\lambda `$ exceeds $`a_c`$ the relaxation is not important, otherwise they should be taken into account. Note that the similar result was derived in prb  for the case of a quantum well. The role of the momentum relaxation mechanism there was played by scattering on heterobarriers. The characteristic quantum well width above which the bulk approximation for the AR is valid was found to be:

$$\stackrel{~}{a}_c=\lambda _{Eg}\left(\frac{T}{E_{th}}\right)^{3/2}\mathrm{exp}\left(\frac{E_{th}}{T}\right),$$
(11)
that is almost equal to (10). The unessential difference in the exponent of $`T/E_{th}`$ is attributed to $`1D`$ scattering in the case of a quantum well.


format: text

text:
# Correspondence principle for idempotent calculus and some computer applications11footnote 1Institut des Hautes Etudes Scientifiques, IHES/M/95/33 Avril 1995 Also published in: Idempotency / J. Gunawardena (editor), Cambridge University Press, Cambridge, 1998, p. 420–443.

## 1 Introduction

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. Idempotent analogs for some basic ideas, constructions and results in Functional Analysis and Mathematical Physics are discussed from this point of view. Thus the correspondence principle is a powerful heuristic tool to apply unexpected analogies and ideas borrowed from different areas of Mathematics and Theoretical Physics.

It is very important that some problems nonlinear in the traditional sense (for example, the Bellman equation and its generalizations and the Hamilton–Jacobi equation) turn out to be linear over a suitable semiring; this linearity considerably simplifies the explicit construction of solutions. In this case we have a natural analog of the so-called superposition principle in Quantum Mechanics (see ).

The theory is well advanced and includes, in particular, new integration theory, new linear algebra, spectral theory and functional analysis. Applications include various optimization problems such as multicriteria decision making, optimization on graphs, discrete optimization with a large parameter (asymptotic problems), optimal design of computer systems and computer media, optimal organization of parallel data processing, dynamic programming, discrete event systems, computer science, discrete mathematics, mathematical logic and so on. See, for example, . Let us indicate some applications of these ideas in mathematical physics and biophysics .

In this paper the correspondence principle is used to develop an approach to object-oriented software and hardware design for algorithms of idempotent calculus and scientific calculations. In particular, there is a regular method for constructing back-end processors and technical devices intended for an implementation of basic algorithms of idempotent calculus and mathematics of semirings. These hardware facilities increase the speed of data processing. Moreover this approach is useful for software and hardware design in the general case of algorithms which are not “idempotent” .

The paper contains a brief survey of the subject but our list of references is not complete. Additional references could be found in , , , , , , , , , ; the corresponding lists of references are not complete too but very useful.

The authors are grateful to I. Andreeva, B. Doubrov, M. Gromov, J. Gunawardena, G. Henkin, V. Kolokoltsov, G. Mascari, P. Del Moral, A. Rodionov, S. Samborski, G. Shpiz, A. Tarashchan for discussions and support.

The work was supported by the Russian Fundation for Basic Research (RFBR), Project 96–01–01544.

## 2 Idempotent quantization and <br>dequantization

Let  be the field of real numbers, $`\text{}_+`$ the subset of all non-negative numbers. Consider the following change of variables:

$$uw=h\mathrm{ln}u,$$
(1)
where $`u\text{}_+`$, $`h>0`$; thus $`u=e^{w/h}`$, $`w\text{}`$. We have got a natural map

$$D_h:\text{}_+A=\text{}\{\mathrm{}\}$$
(2)
defined by the formula (2.1). Denote by 0     the “additional” element $`\mathrm{}`$ and by 1I the zero element of $`A`$ (that is $`\text{1I}=0`$); of course $`\text{0}\text{ }\text{ }=D_h(0)`$ and $`\text{1I}=D_h(1)`$. Denote by $`A_h`$ the set $`A`$ equipped with the two operations $``$ (generalized addition) and $``$ (generalized multiplication) borrowed from the usual addition and multiplication in $`\text{}_+`$ by the map $`D_h`$; thus $`w_1w_2=w_1+w_2`$ and $`w_1w_2=h\mathrm{ln}(e^{w_1/h}+e^{w_2/h})`$. Of course, $`D_h(u_1+u_2)=D_h(u_1)D_h(u_2)`$ and $`D_h(u_1u_2)=D_h(u_1)D_h(u_2)`$. It is easy to prove that $`w_1w_2=h\mathrm{ln}(e^{w_1/h}+e^{w_2/h})\mathrm{max}\{w_1,w_2\}`$ as $`h0`$.

Let us denote by $`\text{}_{\mathrm{max}}`$ the set $`A=\text{}\{\mathrm{}\}`$ equipped with operations $`=\mathrm{max}`$ and $`=+`$; set $`\text{0}\text{ }\text{ }=\mathrm{}`$, $`\text{1I}=0`$. Algebraic structures in $`\text{}_+`$ and $`A_h`$ are isomorphic, so $`\text{}_{\mathrm{max}}`$ is a result of a deformation of the structure in $`\text{}_+`$. There is an analogy to the quantization procedure, and $`h`$ is an analog for the Planck constant. Thus $`\text{}_+`$ (or ) can be treated as a “quantum object” with respect to $`\text{}_{\mathrm{max}}`$ and $`\text{}_{\mathrm{max}}`$ can be treated as a “classical” or “semiclassical” object and as a result of a “dequantization” of this quantum object.

Similarly denote by $`\text{}_{\mathrm{min}}`$ the set $`\text{}\{+\mathrm{}\}`$ equipped with operations $`=\mathrm{min}`$ and $`=+`$; in this case $`\text{0}\text{ }\text{ }=+\mathrm{}`$ and $`\text{1I}=0`$. Of course, the change of variables $`uw=h\mathrm{ln}u`$ generates the corresponding dequantization procedure for this case.

The set $`\text{}\{+\mathrm{}\}\{\mathrm{}\}`$ equipped with the operations $`=\mathrm{min}`$ and $`=\mathrm{max}`$ can be obtained as a result of a “second dequantization” with respect to  (or $`\text{}_+)`$. In this case $`\text{0}\text{ }\text{ }=\mathrm{}`$, $`\text{1I}=\mathrm{}`$ and the dequantization procedure can be applied to the subset of negative elements of $`\text{}_{\mathrm{max}}`$ and the corresponding change of variables is $`wv=h\mathrm{ln}(w)`$.

## 3 Semirings

It is easy to check that for these constructed operations $``$ and $``$ the following basic properties are valid for all elements $`a`$, $`b`$, $`c`$:

$$(ab)c=a(bc);(ab)c=a(bc);$$
(3)
$$\text{0}\text{ }\text{ }a=a\text{0}\text{ }\text{ }=a;\text{1I}a=a\text{1I}=a;$$
(4)
$$\text{0}\text{ }\text{ }a=a\text{0}\text{ }\text{ }=\text{0}\text{ }\text{ };$$
(5)
$$a(bc)=(ab)(ac);(bc)a=(ba)(ca);$$
(6)
$$ab=ba;$$
(7)
$$aa=a;$$
(8)
$$ab=ba.$$
(9)
A set $`A`$ equipped with binary operations $``$ and $``$ and having distinguished elements 0     and 1I is called a semiring, if the properties (axioms) (3.1), (3.2), (3.3), (3.4) and (3.5) are fulfilled. We shall suppose that $`\text{0}\text{ }\text{ }\text{1I}`$.

This semiring is idempotent if (3.6) is valid. Idempotent semirings are often called dioids. A semiring (maybe non-idempotent) is called commutative, if (3.7) is valid. Note that different versions of this axiomatics are used, see, for example, , , , ,  and some literature indicated in .

Example 3.1. The set $`\text{}_+`$ of all nonnegative real numbers endowed with the usual addition and multiplication is a commutative (but not idempotent) semiring. Of course, the field  of all real numbers is also a commutative semiring.

Example 3.2. $`\text{}_{\mathrm{max}}`$ and $`\text{}_{\mathrm{min}}`$ are isomorphic commutative idempotent semirings.

Example 3.3. $`A=\text{}_+`$ with the operations $`=\mathrm{max}`$ and $`=`$ (the usual multiplication); $`\text{0}\text{ }\text{ }=0`$, $`\text{1I}=1`$. This idempotent semiring is isomorphic to $`\text{}_{\mathrm{max}}`$ by the mapping $`x\mathrm{ln}(x)`$.

Example 3.4. $`A=[a,b]=\{x\text{}|axb\}`$ with the operations $`=\mathrm{max}`$, $`=\mathrm{min}`$ and the neutral elements $`\text{0}\text{ }\text{ }=a`$ and $`\text{1I}=b`$ (the cases $`a=\mathrm{}`$, $`b=+\mathrm{}`$ are possible). $``$

Semirings similar to these examples are the most close to the initial “quantum” object $`\text{}_+`$ and can be obtained by dequantization procedures. However there are many important idempotent semirings which are unobtainable by means of these procedures. Note that there exist important quantum mechanical systems which cannot be obtained from classical systems by quantization (for example, particles with spin and systems consisting of identical particles). Thus the situation is natural enough for our analogy.

Example 3.5. Let $`\text{Mat}_n(A)`$ be the set of $`n\times n`$ matrices with entries belonging to an idempotent semiring $`A`$. This set forms a noncommutative idempotent semiring with respect to matrix addition $``$ and matrix multiplication $``$, that is

$$(XY)_{ij}=X_{ij}Y_{ij}\text{and}(XY)_{ij}=_{k=1}^nX_{ik}Y_{kj}.$$

Of course, $`(\text{0}\text{ }\text{ })_{ij}=\text{0}\text{ }\text{ }A`$, and $`(\text{1I})_{ij}=\text{0}\text{ }\text{ }A`$ if $`ij`$, and $`(\text{1I})_{ii}=\text{1I}A`$.

Example 3.6. $`A=\{0,1\}`$ with the operations $`=\mathrm{max}`$, $`=\mathrm{min}`$, $`\text{0}\text{ }\text{ }=0`$, $`\text{1I}=1`$. This is the well-known Boolean semiring (or Boolean algebra). $``$

Note that every bounded distributive lattice is an idempotent semiring.

Example 3.7. $`A=\{\text{0}\text{ }\text{ },\text{1I},a\}`$, where $`\{\text{0}\text{ }\text{ },\text{1I}\}`$ is a Boolean semiring, $`\text{0}\text{ }\text{ }a=a`$, $`\text{0}\text{ }\text{ }a=\text{0}\text{ }\text{ }`$, $`\text{1I}a=a`$, $`\text{1I}a=\text{1I}`$, $`aa=a`$, $`aa=a`$. This example can be treated as a three-valued logic. $``$

There are many finite idempotent semirings; a classification of commutative idempotent semirings consisting of two, or three, or four elements is presented in .

Example 3.8. Let $`A`$ be the set of all compact convex subsets of $`\text{}^n`$ (or of any closed convex cone in $`\text{}^n`$); this set is an idempotent semiring with respect to the following operations:

$`\alpha \beta `$ $`=`$ $`\text{convex}\text{hull}\text{of }\alpha \text{ and }\beta ;`$
$`\alpha \beta `$ $`=`$ $`\{a+ba\alpha ,b\beta \}`$
for all $`\alpha ,\beta A`$; $`\text{0}\text{ }\text{ }=`$, $`\text{1I}=\{0\}`$. This idempotent semiring is used in mathematical economics and in the multicriterial optimization problem (evolution of the so-called Paretó sets; see, for example , ).

Example 3.9. If $`A_1`$ and $`A_2`$ are idempotent semirings, then $`A=A_1\times A_2`$ is also an idempotent semiring with respect to the natural component-wise operations of the direct product; in this case $`(\text{0}\text{ }\text{ },\text{0}\text{ }\text{ })`$ and $`(\text{1I},\text{1I})`$ are the corresponding neutral elements. A similar (and natural, see ) construction turns $`(A_1\backslash \{\text{0}\text{ }\text{ }\})\times (A_2\backslash \{\text{0}\text{ }\text{ }\})\text{0}\text{ }\text{ }`$ into an idempotent semiring. $``$

Probably the first interesting and nontrivial idempotent semiring of all languages over a finite alphabet was examined by S. Kleene  in 1956. This noncommutative semiring was used for applications to compiling and syntax analysis, see also , . There are many other interesting examples of idempotent semirings (including the so-called “tropical” semirings, see, for example, , , , , ) with applications to theoretical computer science (linguistic problems, finite automata, discrete event systems and Petri nets, stochastic systems, computational problems etc.), algebra (semigroups of matrices over semirings), logic, optimization etc.; in particular, see also , , , , , , , , , , , .

There is a naturally defined partial order (i.e. partial ordering relation) on any idempotent semiring (as well as on any idempotent semigroup); by definition, $`\alpha b`$ if and only if $`ab=b`$. For this relation the reflexivity is equivalent to the idempotency of the (generalized) addition, whereas the transitivity and the antisymmetricity follow, respectively, from the associativity and from the commutativity of this operation. This ordering relation on $`\text{}_{\mathrm{max}}`$ (as well as on semirings described in the examples 3.3 and 3.4) coincides with the natural one but for $`\text{}_{\mathrm{min}}`$ it is opposite to the natural ordering relation on the real axis.

Every element $`a`$ of an idempotent semiring $`A`$ is “nonnegative”: $`\text{0}\text{ }\text{ }a`$; indeed, $`\text{0}\text{ }\text{ }a=a`$ because of (3.2). Similarly, for all $`a,b,cA`$ we have $`acbc`$, and $`acbc`$ if $`ab`$.

Using this standard partial order it is possible to define in the usual way the notions of upper and lower bounds, bounded sets, $`supM`$ and $`infN`$ for upper/lower bounded sets $`M`$ and $`N`$ etc. On the basis of these concepts an algebraic approach to the subject is developed, see, for example, , , , , , , , .

An idempotent semiring can be a metric or topological space with natural correlations between topological and algebraic properties. For example, for $`\text{}_{\mathrm{min}}`$ there is a natural metric $`\rho (x,y)=|e^xe^y|`$, and for the semiring from Example 3.4 it is convenient to use the metric $`\rho (x,y)=|\mathrm{arctan}x\mathrm{arctan}y|`$ if $`a=\mathrm{}`$, $`b=+\mathrm{}`$. The corresponding “topological” approach was developed, e.g. in , , , , , , .

## 4 Semirings with special properties

It is convenient to treat some special classes of semirings for which some additional conditions are fulfilled. Let us discuss some conditions of this type.

Suppose $`A`$ is an arbitrary semiring. The so-called cancellation condition is fulfilled for $`A`$ if $`b=c`$ whenever $`ab=ac`$ and $`a\text{0}\text{ }\text{ }`$. If the multiplication in $`A`$ is invertible on $`A\backslash \{\text{0}\text{ }\text{ }\}`$, then $`A`$ is called a semifield. Of course, the cancellation condition is fulfilled for all semifields. For example, $`\text{}_{\mathrm{max}}`$ is a semifield. Idempotent semirings with the cancellation condition or with an idempotent multiplication are especially interesting.

For arbitrary commutative idempotent semirings with the cancellation condition the following version of Newton’s binomial formula is valid:

$$(ab)^n=a^nb^n,$$
(10)
see , . However, this formula is valid also for semirings from Example 3.4 which have no the cancellation condition. It is easily proved (by induction) that for arbitrary commutative idempotent semirings this binomial formula has the form

$$(ab)^n=\underset{i=0}{\overset{n}{}}a^{ni}b^i.$$
(11)
Suppose $`A`$ is an arbitrary idempotent semiring. Applying (4.2) to the semiring generated by elements $`\text{1I},aA`$, we deduce the following formula:

$$(\text{1I}a)^n=\text{1I}aa^2\mathrm{}a^n.$$
(12)
Now let $`A`$ be an arbitrary semiring (maybe non-idempotent) and suppose that the following infinite sum

$$a^{}=\underset{i=0}{\overset{\mathrm{}}{}}a^i=\text{1I}aa^2\mathrm{}a^n\mathrm{}$$
(13)
is well-defined for an element $`aA`$. For concrete semirings $`a^{}`$ may be defined, e.g. as $`\underset{n}{sup}\{(\text{1I}+a)^n\}`$ or $`\underset{n\mathrm{}}{lim}(\text{1I}a)^n`$. This important star operation $`aa^{}`$ was introduced by S. Kleene ; the element $`a^{}`$ is called a closure of $`a`$.

It is natural to set $`a^{}=(\text{1I}a)^1`$ if $`A`$ is a field and $`a\text{1I}`$. It is easy to prove that $`a^{}=\text{1I}`$, if $`A`$ is an idempotent semiring and $`a\text{1I}`$. For $`\text{}_{\mathrm{max}}`$ the closure $`a^{}`$ is not defined if $`\text{1I}a`$. The situation can be corrected if we add an element $`\mathrm{}`$ such that $`a\mathrm{}=\mathrm{}`$ for all $`\text{}_{\mathrm{max}}`$, $`\text{0}\text{ }\text{ }\mathrm{}=\text{0}\text{ }\text{ }`$, $`a\mathrm{}=\mathrm{}`$ for all $`a\text{0}\text{ }\text{ }`$. For this new semiring $`\overline{\text{}}_{\mathrm{max}}=\text{}_{\mathrm{max}}\{\mathrm{}\}`$ we have $`a^{}=\mathrm{}`$ if $`\text{1I}a`$, see e.g. , . For all semirings described in the examples 3.4, 3.6 and 3.7 we have $`a^{}=\text{1I}`$ for any element $`a`$.

An idempotent semiring $`A`$ is algebraically closed (with respect to the operation $``$) if the equation $`x^n=a`$ (where $`x^n=x\mathrm{}x`$) has a solution $`xA`$ for any $`aA`$ and any positive integer $`n`$, see , . It is remarkable and important that the semiring $`\text{}_{\mathrm{max}}`$ is algebraically closed in this sense. However, the equation $`x^2\text{1I}=\text{0}\text{ }\text{ }`$ has no solutions.

## 5 Correspondence principle

The analogy with Quantum Mechanics discussed in section 2 leads to the following correspondence principle in idempotent calculus:

There is a (heuristic) correspondence between important, useful and interesting constructions and results over the field of real (or complex) numbers (or the semiring of all nonnegative numbers) and similar constructions and results over idempotent semirings in the spirit of the correspondence principle in Quantum Mechanics.

Example 5.1. Semimodules (see e.g. , , , , , , ). A set $`V`$ is called a semimodule over a semiring $`A`$ (or an $`A`$-semimodule), if there is a commutative associative addition operation $``$ in $`V`$ with neutral element 0    , and a multiplication $``$ of elements from $`V`$ by elements of $`A`$ is defined, and the following properties are fulfilled:

$`(\lambda \mu )v=\lambda (\mu v)`$ $`\text{ for all}\lambda ,\mu A,vV;`$
$`\lambda (v_1v_2)=\lambda v_1\lambda v_2`$ $`\text{ for all}\lambda A,v_1,v_2V;`$
$`\text{0}\text{ }\text{ }v=\lambda \text{0}\text{ }\text{ }=\text{0}\text{ }`$ $`\text{ for all}\lambda A,vV.`$
The addition $``$ in $`V`$ is assumed to be idempotent if $`A`$ is an idempotent semiring (i.e. $`vv=v`$ for all $`vV`$). Then we assume that

$$\underset{\alpha }{sup}\{\lambda _\alpha \}v=\underset{\alpha }{sup}\{\lambda _\alpha v\},\text{ if}vV\text{and}\underset{\alpha }{sup}\{\lambda _\alpha \}A.$$

Roughly speaking, semimodules are “linear spaces” over semirings. The simplest $`A`$-semimodule is the direct sum (product) $`A^n=\{(a_1,a_2,\mathrm{},a_n):a_jA\}`$. The set of all endomorphisms $`A^nA^n`$ coincides with the semiring $`\text{Mat}_n(A)`$ of all $`A`$-valued matrices (see Example 3.5 in Section 3).

The theory of $`A`$-valued matrices is an analog of the well-known O. Perron–G. Frobenius theory of nonnegative matrices, see e.g. . For example, let $`A`$ be an algebraically closed commutative idempotent semiring with the cancellation condition and the sequence $`a^nb`$ stabilizes for any $`a\text{1I}`$ and $`b\text{0}\text{ }\text{ }`$, $`a,bA`$. Then for every endomorphism $`K`$ of $`A^n`$ ($`n1`$) there exists a nontrivial subsemimodule $`SA^n`$ (an “eigenspace”) and $`\lambda A`$ (an “eigenvalue”) such that $`Kv=\lambda v`$ for all $`vS`$; this element $`\lambda `$ is unique if $`K`$ is irreducible, see , . In particular, this result is valid if $`A=\text{}_{\mathrm{max}}`$ (or $`\text{}_{\mathrm{min}}`$). Similar results can be proved for semimodules of bounded functions and continuous functions, see , , . $``$

Idempotent analysis deals with functions taking values in idempotent semirings and with the corresponding function spaces (semimodules). Let $`X`$ be a set and $`A`$ an idempotent semiring. Let us denote by $`B(X,A)`$ the set of all bounded mappings (functions) $`XA`$ (i.e. mappings with order-bounded images) equipped with a natural structure of an $`A`$-semimodule. If $`X`$ is finite, $`X=\{x_1,\mathrm{},x_n\}`$, then $`B(X,A)`$ can be identified with the semimodule $`A^n`$ (see Example 5.1 above). Actually $`B(X,A)`$ is an idempotent semiring with respect to the corresponding pointwise operations.

Let $`A`$ be a metric semiring; then there is the corresponding uniform metric on $`B(X,A)`$. Suppose that $`X`$ is a topological space and then denote by $`C(X,A)`$ the subsemimodule of continuous functions in $`B(X,A)`$.

Suppose now that the space $`X`$ is locally compact and then denote by $`C_{0\text{ }\text{ }}(X,A)`$ the $`A`$-semimodule of continuous $`A`$-valued functions with compact supports endowed with a natural topology (see  for details).

These spaces (and some other spaces of this type) are examples of “idempotent” function spaces. Many basic ideas, constructions and results can be borrowed to idempotent analysis from usual analysis and functional analysis.

Example 5.2. Idempotent integration and measures. For the sake of simplicity set $`A=\text{}_{\mathrm{max}}`$ and let $`X`$ be a locally compact space. An idempotent analog of the usual integration can be defined by the formula

$$_X^{}\phi (x)𝑑x=\underset{xX}{sup}\phi (x),$$
(14)
if $`\phi `$ is continuous or upper semicontinuous function on $`X`$. The set function

$$m_\phi (B)=\underset{xB}{sup}\phi (x),$$
(15)
where $`BX`$ is called an $`A`$-measure on $`X`$ and $`m_\phi (B_\alpha )=\underset{\alpha }{}m_\phi (B_\alpha )=\underset{\alpha }{sup}m_\phi (B_\alpha )`$, so the function (5.2) is completely additive. An idempotent integral with respect to this $`A`$-measure is defined by the formula

$$_X^{}\psi (x)𝑑m_\phi =_X^{}\psi (x)\phi (x)𝑑x=\underset{xX}{sup}\psi (x)\phi (x).$$
(16)
It is obvious that this integration is “linear” over $`A`$ and it is easy to see that (5.1) and (5.3) can be treated as limits of Riemann’s and Lebesgue’s sums. Of course, if $`=\mathrm{min}`$ for the corresponding semiring $`A`$, then (5.3) turns into the formula

$$_X^{}\psi (x)𝑑m_\phi =_X^{}\psi (x)\phi (x)𝑑x=\underset{xX}{inf}\psi (x)\phi (x).$$
(17)
In this case, $``$ may coincide e.g. with max, or the usual addition or multiplication. See , ,  for details. $``$

Note that in (5.4) we mean $`inf`$ (i.e. the greatest lower bound) with respect to the usual ordering of numbers. But if $`=\mathrm{min}`$, then this order is opposite to the standard partial order defined for any idempotent semiring (see Section 3 above). It is clear that (5.3) and (5.4) coincide from this point of view. In general case $`A`$–measure and idempotent integral can be defined by (5.2) and (5.3), e.g. if the corresponding functions are bounded and $`A`$ is boundedly complete, i.e. every bounded subset $`BA`$ has the least upper bound $`supB.`$

There is a natural analogy between idempotent and probability measures. This analogy leads to a parallelism between probability theory and stochastic processes on the one hand, and optimization theory and decision processes on the other hand. That is why it is possible to develop optimization theory at the same level of generality as probability and stochastic processes theory. In particular, the Markov causality principle corresponds to the Bellman optimality principle; so the Bellman principle is an $`\text{}_{\mathrm{max}}`$–version of the Chapman–Kolmogorov equation for Markov stochastic processes, see e.g. , , , , , . Applications to the filtering theory can be found in , .

Example 5.3. Group idempotent (convolution) semirings. Let $`G`$ be a group, $`A`$ an idempotent semiring; assume that $`A`$ is boundedly complete. Then the space $`B(G,A)`$ of all bounded functions $`GA`$ (see above) is an idempotent semiring with respect to the following idempotent analog of convolution:
$`(\phi \text{}\psi )(g)={\displaystyle _G^{}}\phi (x)\psi (x^1g)𝑑x.`$ (5.5)$``$ Of course, it is possible to consider other “function spaces” instead of $`B(G,A).`$ In ,  semirings of this type are referred to as convolution semirings.

Example 5.4. Fourier–Legendre transform, see , , . Let $`A=\text{}_{\mathrm{max}},G=\text{}^n`$ and $`G`$ is treated as a group. The usual Fourier–Laplace transform is defined by the formula

$$\phi (x)\stackrel{~}{\phi }(\xi )=_Ge^{i\xi x}\phi (x)𝑑x,$$
(6)
where $`e^{i\xi x}`$ is a character of the group $`G`$, that is a solution of the following functional equation:

$$f(x+y)=f(x)f(y).$$

The corresponding idempotent analog ( for the case $`A=\text{}_{\mathrm{max}}`$) has the form

$$f(x+y)=f(x)f(y)=f(x)+f(y),$$

so “idempotent characters” are linear functionals $`x\xi x=\xi _1x_1+\mathrm{}+\xi _nx_n.`$ Thus (5.6) turns into the following transform:

$$\phi (x)\stackrel{~}{\phi }(\xi )=_G^{}\xi x\phi (x)𝑑x=\underset{xG}{sup}(\xi x+\phi (x)).$$
(7)
This is the famous Legendre transform. Thus this transform is an $`\text{}_{\mathrm{max}}`$–version of the Fourier–Laplace transform.$``$

Of course, this construction can be generalized to different classes of groups and semirings. Transformations of this type convert the generalized convolution to pointwise multiplication and possesses analogs of some important properties of the usual Fourier transform. For the case of semirings of Pareto sets the corresponding version of the Fourier transform reduces the multicriterial optimization problem to a family of singlecriterial problems .

The examples 5.3 and 5.4 can be treated as fragments of an idempotent version of the representation theory. In particular, idempotent representations of groups can be examined as representations of the corresponding convolution semirings (i.e. idempotent group semirings) in semimodules.

According to the correspondence principle, many important concepts, ideas and results can be converted from usual functional analysis to idempotent analysis. For example, idempotent scalar product can be defined by the formula:

$$(\phi ,\psi )=_X^{}\phi (x)\psi (x)𝑑x,$$
(8)
where $`\phi ,\psi `$ are $`A`$–valued functions belonging to a certain idempotent function space. There are many interesting spaces of this type including $`B(X,A)`$, $`C(X,A)`$, $`C_{0\text{ }\text{ }}(X,A)`$, analogs of the Sobolev spaces and so on. There are analogs for the well-known theorems of Riesz, Hahn–Banach and Banach–Steinhaus; it is possible to treat dual spaces and operators, an idempotent version of the theory of distributions (generalized functions) etc.; see , , , , ,  for details.

Example 5.5. Integral operators. It is natural to construct idempotent analogs of integral operators in the form

$$K:\phi (y)(K\phi )(x)=_Y^{}K(x,y)\phi (y)𝑑y,$$
(9)
where $`\phi (y)`$ is an element of a space of functions defined on a set $`Y`$ and taking their values in an idempotent semiring $`A`$, $`(K\phi )(x)`$ is an $`A`$–valued function on a set $`X`$ and $`K(x,y)`$ is an $`A`$–valued function on $`X\times Y`$. If $`A=\text{}_{\mathrm{max}},`$ then (5.9) turns into the formula

$$(K\phi )(x)=\underset{yY}{sup}\{K(x,y)+\phi (y)\}.$$
(10)
Formulas of this type are standard for optimization problems, see e.g. . $``$

It is easy to see that the operator defined by (5.9) is linear over $`A`$, i.e. $`K`$ is an $`A`$–endomorphism of the corresponding semimodule (function space). Actually every linear operator acting in an idempotent function space and satisfying some natural continuity–type conditions can be presented in the form (5.9). This is an analog of the well–known L. Schwartz kernel theorem. The topological version of this result in spaces of continuous functions was established in , ; see also , . The algebraic version of the kernel theorem for the space of bounded functions see in ,  and (in a final form) in .

## 6 Superposition principle

In Quantum Mechanics the correspondence principle means that the Schrödinger equation (which is basic for the theory) is linear. Similarly in idempotent calculus the correspondence principle means that some important and basic problems and equations (e.g. optimization problems, the Bellman equation and its generalizations, the Hamilton–Jacobi equation) nonlinear in the usual sense can be treated as linear over appropriate idempotent semirings, see , .

Example 6.1. Idempotent dequantization for the heat equation. Let us start with the heat equation

$$\frac{u}{t}=\frac{h}{2}\frac{^2u}{x^2},$$
(11)
where $`x\text{},t>0,`$ and $`h`$ is a positive parameter.

Consider the following change of variables:

$`uw=h\mathrm{ln}u;`$

it converts (6.1) to the following (integrated) version of the Burgers equation:

$$\frac{w}{t}+\frac{1}{2}\left(\frac{w}{x}\right)^2\frac{h}{2}\frac{^2w}{x^2}=0.$$
(12)
This equation is nonlinear but it can be treated as linear over the following generalized addition $``$ and multiplication $``$ (borrowed from the usual addition and multiplication by the change of variables):

$$w_1w_2=h\mathrm{ln}(e^{w_1/h}+e^{w_2/h}),$$
(13)
$$w_1w_2=w_1+w_2.$$
(14)
So if $`w_1`$ and $`w_2`$ are solutions for (6.2), then their linear combination with respect to the operations (6.3) and (6.4) is also a solution for this equation. For $`h0`$ (6.2) turns into a special case of the Hamilton–Jacobi equation:

$$\frac{w}{t}+\frac{1}{2}\left(\frac{w}{x}\right)^2=0.$$
(15)
This is the dequantization procedure described in Section 2 above. So it is clear that (6.3) and (6.4) turn into addition $`=\mathrm{min}`$ and multiplication $`=+`$ in the idempotent semiring $`\text{}_{\mathrm{min}}`$ and the equation (6.5) is linear over $`\text{}_{\mathrm{min}}`$; thus the set of solutions for (6.5) is an $`\text{}_{\mathrm{min}}`$–semimodule. This example was the starting point for the well–known Hopf method of vanishing viscosity.$``$

In general case the Hamilton–Jacobi equation has the following form:

$$\frac{S(x,t)}{t}+H(\frac{S}{x},x,t)=0,$$
(16)
where $`H`$ is a smooth function on $`\text{}^{2n}\times [0,T]`$. Consider the Cauchy problem for (6.6): $`S(x,0)=S_0(x),\mathrm{\hspace{0.17em}0}tT,x\text{}^n`$. Denote by $`U_t`$ the resolving operator, i.e. the map that assigns to each given $`S_0(x)`$ the solution $`S(x,t)`$ of this problem at the moment of time $`t`$. Then the map $`U_t`$ for each $`t`$ is a linear (over $`\text{}_{\mathrm{min}}`$) integral operator in the corresponding $`\text{}_{\mathrm{min}}`$–semimodule.

The situation is similar for the Cauchy problem for the homogeneous Bellman equation

$$\frac{S}{t}+H\left(\frac{S}{x}\right)=0,S|_{t=0}=S_0(x),$$

where $`H:\text{}^n\text{}`$ is a convex (not strictly) first order homogeneous function

$$H(p)=\underset{(f,g)V}{sup}(fp+g),f\text{}^n,g\text{},$$

and $`V`$ is a compact set in $`\text{}^{n+1}.`$ See , , ,  for details.

It is well–known that discrete version of the Bellman equation can be treated as linear over idempotent semirings. The so-called generalized stationary (finite dimensional) Bellman equation has the form

$$S=HSF,$$
(17)
where $`S,H,F`$ are matrices with elements from an idempotent semiring $`A`$ and the corresponding matrix operations are described in Example 3.5 above (for the sake of simplicity we write $`HS`$ instead of $`HS`$); the matrices $`H`$ and $`F`$ are given (specified) and it is necessary to determine $`S`$ from the equation.

The equation (6.7) has the following solution:

$$S=H^{}F,$$
(18)
where $`H^{}`$ is the closure of $`H\text{Mat}_n(A)`$, see Section 4 and Example 3.5 above. Recall that

$$H^{}=\text{1I}HH^2\mathrm{}H^k\mathrm{},$$
(19)
if the right-hand side of (6.9) is well-defined. In this case $`H^{}=\text{1I}HH^{}`$, so $`H^{}F=FHH^{}F`$; thus (6.8) is a solution of (6.7). For example, if the sequence $`H^{(N)}=_{k=0}^NH^k`$ stabilizes (i.e. there exists $`N_0`$ such that $`H^{(N)}=H^{(N_0)}`$ for all $`NN_0`$), then (6.9) is well-defined and can be calculated by means of a finite set of operations (steps).

This consideration and a version of the Gauss elimination method for solving (6.7) were presented by S. Kleene  in the case of the semiring of all languages over a finite alphabet. B. A. Carre  used semirings to show that many important problems for graphs can be formulated in a unified manner and are reduced to solving systems of algebraic equations. For example, Bellman’s method of solving shortest path problems corresponds to a version of the Jacobi method for solving (6.7), whereas Ford’s algorithm corresponds to a version of the Gauss-Seidel method. The further development of this subject see in , , , , .

Let $`A`$ be a semiring (maybe non-idempotent). For each square $`n\times n`$ matrix $`H=(h_{ij})\text{Mat}_n(A)`$ there is a standard way to construct a geometrical object called a weighted directed graph. This object consists of a set $`X`$ of $`n`$ elements $`x_1,x_2,\mathrm{},x_n`$ together with the subset $`\mathrm{\Gamma }`$ of all ordered pairs $`(x_i,x_j)X\times X`$ such that $`h_{ij}\text{0}\text{ }\text{ }`$ and the mapping $`h:\mathrm{\Gamma }A\backslash \{\text{0}\text{ }\text{ }\}`$ given by the correspondence $`(x_i,x_j)h_{ij}`$. The elements of $`X`$ are called nodes, and the members of $`\mathrm{\Gamma }`$ are called arcs; $`h_{ij}`$ are arc weights.

In other terms the quadruple $`M(X,\mathrm{\Gamma },h,A)`$ can be treated as a discrete medium with the points $`x_i`$, the set $`\mathrm{\Gamma }`$ of links and the so-called link characteristics $`h`$. This concept is convenient for analysis of parallel computations and for synthesis of computing media. Mathematical aspects of these problems are examined in ; the further development of the subject is presented e.g. in , ; see also , , , , . For example, the operating period evaluation problem for parallel algorithms and digital circuits leads to shortest path problems for $`M(X,\mathrm{\Gamma },h,A)`$, where $`A=\text{}_{\mathrm{max}}`$.

Recall that a sequence of nodes and arcs of the form

$$p=(y_0,a_1,y_1,a_2,y_2,\mathrm{},a_k,y_k),$$
(20)
where $`k0`$, $`y_i`$ are nodes of the graph, and $`a_i`$ are arcs satisfying $`a_i=(y_{i1},y_i)`$, is called a path (of order $`k`$) from the node $`y_0`$ to the node $`y_k`$ in $`M(X,\mathrm{\Gamma },h,A)`$. The weight $`h(p)`$ of the path (6.10) is a product of the weights of its arcs:

$$h(p)=h(a_1)h(a_2)\mathrm{}h(a_k).$$
(21)
The so-called Algebraic Path Problem is to find the following matrix $`D=(d_{ij})`$:

$$d_{ij}\stackrel{\mathrm{def}}{=}_ph(p),$$
(22)
where $`i,j=1,2,\mathrm{},n`$, and $`p`$ runs through all paths from $`x_i`$ to $`x_j`$. A solution to this problem does not need to exist (the set of weights in (6.12) may be infinite). However, if there exists a closure $`H^{}`$ of the matrix $`H=(h_{ij})`$, then the matrix

$$D=(d_{ij})=H^{}=\text{1I}HH^2\mathrm{}H^k\mathrm{}$$
(23)
can be treated as a solution of this problem. Moreover, $`H^k`$ corresponds to the value $`_ph(p)`$, where $`p`$ contains exactly $`k`$ arcs. For example, $`h_{ij}^{(2)}=_{k=1}^nh_{ik}h_{kj}`$ are elements (coefficients) of $`H^2`$, and each coefficient $`h_{ij}^{(2)}`$ corresponds to $`_ph(p)`$, where p runs through paths from $`x_i`$ to $`x_j`$ with exactly two arcs; similarly, $`H^3=H^2H`$, etc.

Example 6.2. The shortest path problem. Let $`A=\text{}_{\mathrm{min}}`$, so $`h_{ij}`$ are real numbers. In this case

$$d_{ij}=_ph(p)=\underset{p}{\mathrm{min}}h(p),$$

where (6.11) has the form

$$h(p)=h(a_1)+h(a_2)+\mathrm{}+h(a_k).$$

Example 6.3. The relation closure problem. Let $`A`$ be the Boolean semiring (see Example 3.6 in Section 3 above). In this case $`H`$ corresponds to a relation $`RX\times X`$, $`h_{ij}`$ being 1I if and only if the relation holds between $`x_i`$ and $`x_j`$. Then the transitive and reflective closure $`R^{}`$ of the relation $`R`$ corresponds to the matrix $`D=H^{}`$.

Example 6.4. The maximal (minimal) width path problem. Let $`A`$ be a semiring $`\text{}\{\mathrm{}\}\{\mathrm{}\}`$ with the operations $`=\mathrm{max}`$ and $`=\mathrm{min}`$ (see Example 3.4). Then

$$d_{ij}=_ph(p)=\underset{p}{\mathrm{max}}h(p),$$

where $`h(p)=\mathrm{min}\{h(a_1),h(a_2),\mathrm{},h(a_k)\}`$. If $`h(a_i)`$ is the width (or channel capacity) of $`a_i`$, then $`h(p)`$ is the possible width (or channel capacity) of $`p`$.

Example 6.5. The matrix inversion problem. Let $`A`$ be the field  of real numbers (which is not an idempotent semiring). In this case

$$D=H^{}=\text{1I}+H+H^2\mathrm{}=(1H)^1,$$

if the series $`_{k=0}^{\mathrm{}}H^k`$ converges; if the matrix $`\text{1I}H`$ is invertible, then $`(\text{1I}H)^1`$ can be treated as a “regularized” sum of this series; here $`H^0=\text{1I}`$ is the identity matrix.

Example 6.6. A simple dynamic programming problem. Let $`A=\text{}_{\mathrm{max}}`$, so $`h_{ij}`$ are real numbers. Let us consider $`h_{ij}`$ as a profit of moving from $`x_i`$ to $`x_j`$, and suppose $`f_i`$ is a terminal prize for the node $`x_i`$ ($`f_i\text{}`$). Assume that $`p`$ is a path of the form (6.10) and $`y_0=x_i`$. Let $`M`$ be a total profit for $`p`$, that is

$$M=h(a_1)+h(a_2)+\mathrm{}+h(a_k)+f(y_k).$$

It is easy to see that $`\mathrm{max}M=(H^kf)_i`$, where $`f`$ is a vector $`\{f_i\}`$, $`H,H^k\text{Mat}_n(A)`$. So, the maximal value of the total profit for $`k`$ steps is $`(H^kf)_i`$. It is clear that the maximal value of the total profit for paths of arbitrary order is $`\mathrm{max}M=(H^{}f)_i`$.$``$

See many other examples and details (including semiring versions of linear programming) in , , , , , , , . The book  of F. L. Baccelli, G. Cohen, G. J. Olsder and J.-P. Quadrat is particularly useful.

## 7 Correspondence principle for algorithms

Of course, the correspondence principle is valid for algorithms (as well as for their software and hardware implementations). Thus:

If we have an important and interesting numerical algorithm, then we have a good chance that its semiring analogs are important and interesting as well.

In particular, according to the superposition principle, analogs of linear algebra algorithms are especially important. Note that numerical algorithms for standard infinite-dimensional linear problems over semirings (i.e. for problems related to integration, integral operators and transformations, the Hamilton–Jacobi and generalized Bellman equations) deal with the corresponding finite-dimensional (or finite) “linear approximations”. Nonlinear algorithms often can be approximated by linear ones. Recall that usually different natural algorithms for the same optimization problem correspond to different standard methods for solving systems of linear equations (like Gauss elimination method, iterative methods etc.).

It is well-known that algorithms of linear algebra are convenient for parallel computations (see, e.g. ); so, their idempotent analogs accept a parallelization. This is a regular way to use parallel computations for many problems including basic optimization problems.

Algorithms for the “scalar” (inner) product of two vectors, for matrix addition and multiplication do not depend on concrete semirings. Algorithms to construct the closure $`H^{}`$ of an “idempotent” matrix $`H`$ can be derived from standard methods for calculating $`(\text{1I}H)^1`$. For the Gauss–Jordan elimination method (via LU-decomposition) this trick was used in , and the corresponding algorithm is universal and can be applied both to the general algebraic path problem and to computing the inverse of a real (or complex) matrix $`(\text{1I}H)`$. Computation of $`H^1`$ can be derived from this universal algorithm with some obvious cosmetic transformations.

Note that numerical algorithms are combinations of basic operations. Usually these basic operations deal with “numbers”. Actually these “numbers” are thought as members of some numerical domains (real numbers, integers, and so on). But every computer calculation deals with concrete models (computer representations) of these numerical domains. For example, real numbers can be represented as ordinary floating point numbers, or as double precision floating point numbers, or as rational numbers etc. Differences between mathematical objects and their computer models lead to calculation errors. That is another reason to use universal algorithms which do not depend on a concrete semiring and its concrete computer model. Of course, one algorithm may be more universal than another algorithm of the same type. For example, numerical integration algorithms based on the Gauss–Jacobi quadrature formulas actually depend on computer models because they use finite precision constants. On the contrary, the rectangular formula and the trapezoid rule do not depend on models and in principle can be used even in the case of idempotent integration.

## 8 Correspondence principle for hardware <br>design

A systematic application of the correspondence principle to computer calculations leads to a unifying approach to software and hardware design.

The most important and standard numerical algorithms have many hardware realizations in the form of technical devices or special processors. These devices often can be used as prototypes for new hardware units generated by substitution of the usual arithmetic operations for its semiring analogs and by addition tools for performing neutral elements 0     and 1I (the latter usually is not difficult). Of course the case of numerical semirings consisting of real numbers (maybe except neutral elements) is the most simple and natural. Semirings of this type are presented in the examples 3.1–3.4. Semirings from the examples 3.6 and 3.7 can also be treated as numerical semirings. Note that for semifields (including $`\text{}_{\mathrm{max}}`$ and $`\text{}_{\mathrm{min}}`$) the operation of division is also defined.

Good and efficient technical ideas and decisions can be transposed from prototypes into new hardware units. Thus the correspondence principle generates a regular heuristic method for hardware design. Note that to get a patent it is necessary to present the so-called “invention formula”, that is to indicate a prototype for the suggested device and the difference between these devices. A survey of patents from the correspondence principle point of view is presented in .

Consider (as a typical example) the most popular and important algorithm of computing the scalar product of two vectors:

$$(x,y)=x_1y_1+x_2y_2+\mathrm{}+x_ny_n.$$
(24)
The universal version of (8.1) for any semiring $`A`$ is obvious:

$$(x,y)=(x_1y_1)(x_2y_2)\mathrm{}(x_ny_n).$$
(25)
In the case $`A=\text{}_{\mathrm{max}}`$ this formula turns into the following one:

$$(x,y)=\mathrm{max}\{x_1+y_1,x_2+y_2,\mathrm{},x_n+y_n\}.$$
(26)
This calculation is standard for many optimization algorithms (see Section 6), so it is useful to construct a hardware unit for computing (8.3). There are many different devices (and patents) for computing (8.1) and every such device can be used as a prototype to construct a new device for computing (8.3) and even (8.2). Many processors for matrix multiplication and for other algorithms of linear algebra are based on computing scalar products and on the corresponding “elementary” devices respectively, etc.

There are some methods to make these new devices more universal than their prototypes. There is a modest collection of possible operations for standard numerical semirings: $`\mathrm{max}`$, $`\mathrm{min}`$, and the usual arithmetic operations. So, it is easy to construct programmable hardware processors with variable basic operations. Using modern technologies it is possible to construct cheap special-purpose multi-processor chips implementing examined algorithms. The so-called systolic processors are especially convenient for this purpose. A systolic array is a “homogeneous” computing medium consisting of elementary processors, where the general scheme and processor connections are simple and regular. Every elementary processor pumps data in and out performing elementary operations in a such way that the corresponding data flow is kept up in the computing medium; there is an analogy with the blood circulation and this is a reason for the term “systolic”, see e.g. , .

Concrete systolic processors for the general algebraic path problem are presented in , . In particular, there is a systolic array of $`n(n+1)`$ elementary processors which performs computations of the Gauss–Jordan elimination algorithm and can solve the algebraic path problem within $`5n2`$ time steps. Of course, hardware implementations for important and popular basic algorithms increase the speed of data processing.

## 9 Correspondence principle for software <br>design

Software implementations for universal semiring algorithms are not so efficient as hardware ones (with respect to the computation speed) but are much 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. In this case concrete operations and data types are defined by means of additional program modules. For programs written in this manner it is convenient to use a special techniques of the so-called object-oriented design, see e.g. . Fortunately, powerful tools supporting the object-oriented software design have recently appeared including compilers for real and convenient programming languages (e.g. $`C^{++}`$).

There is a project to obtain an implementation of the correspondence principle approach to scientific calculations in the form of a powerful software system based on a unifying collection of universal algorithms. This approach ensures a working time reduction for programmers and users because of software unification. The arbitrary necessary accuracy and safety of numerical calculations can be ensured as well .

The system contains several levels (including the programmer and user levels) and many modules. Roughly speaking it is divided into three parts. The first part contains modules that implement finite representations of basic mathematical objects (arbitrary precision real and complex numbers, finite precision rational numbers, $`p`$-adic numbers, interval numbers, fuzzy numbers, basic semirings and rings etc.). The second part implements universal calculation algorithms (linear algebra, idempotent and usual analysis, optimization and optimal control, differential equations and so on). The third part contains modules implementing model dependent algorithms (e.g. graphics, Gauss–Jacobi type numerical integration, efficient approximation algorithms). The modules can be used in user programs written in $`C^{++}`$. See  for some details.

E-mail: litvinov@islc.msk.su

glitvinov@mail.ru