Solving Polynomial Equations on an Analog Computer Using a Modified Monte Carlo Method
Abstract Generated abstract
This paper addresses the solution of polynomial equations on analog computers using Monte Carlo techniques, arguing that a direct transfer of the conventional digital Monte Carlo approach is inefficient for continuous analog computation. It formulates the complex polynomial root problem through real and imaginary components, reduces root finding to minimization of the sum of moduli of these components, and describes analog circuits for function formation, modulus selection, minimum holding, and recording. A modified method is proposed in which randomly generated line segments cover the complex plane and the analog computer continuously searches for minima along each segment. The author argues that this use of continuous analog motion substantially accelerates the search for polynomial roots and may also be applicable to other equation-solving problems.
Full Text
SOLVING POLYNOMIAL EQUATIONS ON ANALOG COMPUTERS USING A MODIFIED MONTE CARLO METHOD
I. G. Vintizenko
(Presented by the scientific seminar of the Department of Computer Engineering, TPI)
It is known that many problems can be solved on analog computing machines (ACMs) using the Monte Carlo method. However, the mechanical transfer of the Monte Carlo method, so convenient in solving problems on digital computing machines, to the domain of continuous solutions provided by ACMs is ineffective, since the method does not take into account the specifics of analog solutions.
Let us consider the application of the ordinary Monte Carlo method to finding, on an ACM, the roots of the polynomial
\[ f(x)=a_n x^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0=0. \tag{1} \]
The block diagram for solving this problem is shown in Fig. 1.
Fig. 1
Existing methods for finding roots (Mitrovich’s method [3], the steepest-descent method [1], etc.) are too cumbersome, require auxiliary transformations of equation (1), and so forth.
Assuming, in the general case, that \(x\) is a complex quantity, we write equation (1) in the form of two equations for the real and imaginary parts of equation (1):
\[ x=U_1+jV_1; \tag{2} \]
\[ x^2 = U_2 + jV_2, \tag{3} \]
where
\[ U_2 = U_1^2 - V_1^2, \tag{3a} \]
\[ V_2 = 2U_1V_1, \tag{3b} \]
\[ x^3 = U_3 + jV_3, \tag{4} \]
where
\[ U_3 = U_1U_2 - V_1V_2, \tag{4a} \]
\[ V_3 = U_1V_2 + V_1U_2 \tag{4b} \]
and so on, up to
\[ x^n = U_n + jV_n, \tag{5} \]
where
\[ U_n = U_1U_{n-1} - V_1V_{n-1}, \tag{5a} \]
\[ V_n = U_1V_{n-1} - V_1U_{n-1}. \tag{5b} \]
Then equation (1) will be represented in the form
\[ f(x) \equiv \sum_{k=1}^{n} a_k U_k + a_0 + j \sum_{k=1}^{n} a_k V_k = 0. \tag{6} \]
A root is found only in the case when both the real and the imaginary parts of \(f(x)\) are simultaneously equal to zero, i.e.,
\[ f(U) \equiv a_n U_n + a_{n-1}U_{n-1} + \ldots + a_1U_1 + a_0 = 0, \tag{7} \]
\[ f(V) \equiv a_n V_n + a_{n-1}V_{n-1} + \ldots + a_1V_1 = 0. \tag{8} \]
To simplify the solving circuits, one usually seeks the minimum of a single function that is positive definite and tends to zero when the functions \(f(U)\) and \(f(V)\) simultaneously tend to zero. This is either the quadratic form
\[ R = [f(U)]^2 + [f(V)]^2 \to 0, \tag{9} \]
or the sum of moduli
\[ S = |f(U)| + |f(V)| \to 0. \tag{10} \]
In analog technology it proves simpler and more accurate to obtain the sum of moduli; this method of obtaining the function to be minimized is adopted in the present work.
As formulas (3)—(5) show, the structure of the blocks for forming the functions \(f(U)\) and \(f(V)\) is uniform. It is most convenient for implementing these functions to use systems of multiplication blocks (for example, product blocks on electronic tracking systems of the SBPD section of the MN-14 analog computer). A universal circuit for obtaining the functions \(f(U)\) and \(f(V)\) for equations up to and including the 6th order is shown in Fig. 2.
Using the ordinary Monte Carlo method, the stated problem is solved as follows: the signals \(U_{cj}\) and \(V_{cj}\) from the outputs of the rectangular-pulse generators of random amplitude GISA-1 and GISA-2 [2] are fed to the inputs of the circuits forming \(f(U)\) and \(f(V)\); the obtained voltages \(f(U_{cj})\) and \(f(V_{cj})\) pass through the modulus-forming circuits MOD-1 and MOD-2 and through the minimum-selection circuit MIN;
Fig. 2
the relay of the MIN block \(P_1\) gives a signal to control printing by the TsPM digital printing machine of the ETsR electronic digital recorder only in the case when the sum of the moduli arriving at the \(j\)-th cycle is less than the minimum of the previously obtained sums of moduli
\[
S_1=|f(U_{c1})|+|f(V_{c1})|,\qquad
S_2=|f(U_{c2})|+|f(V_{c2})|,
\]
\[
\ldots\ S_{j-1}=|f(U_{c,j-1})|+|f(V_{c,j-1})|.
\]
Thus, at each \(j\)-th step, when the sum \(S_j\) is minimal in comparison with any preceding value, \(U_{cj}, V_{cj}, S_j\) are printed.
Let us consider the construction of the modulus-selection block MOD. The MOD block must not introduce its own noise into the solution process, especially since the final search for the root is carried out at a voltage level close to zero; the block must have a characteristic close to ideal at small voltages \(U_{\text{in}}\) and \(U_{\text{out}}\). These requirements are met by a modulus-forming circuit with an “ideal diode” [5]. The circuit was implemented on the MN-14 analog computer (Fig. 3).
Fig. 3
The most stringent requirements are imposed on the minimum circuit MIN. This circuit operates in two modes: tracking and holding. If the voltage at the input of the MIN circuit decreases, the circuit is in the “tracking” mode and its output voltage also decreases. When the input signal increases, the MIN circuit automatically switches to the mode of holding the minimum signal and remains in this state until the input signal becomes smaller than the recorded one. The circuit again switches to tracking mode and follows the decrease of \(S_j\) until the next increase of the input signal; then it again records the minimum, and so on, until \(S_k \to 0\). When the circuit switches to holding mode, relay \(P_1\) operates, and by its contacts turns on printing; in this case \(U_{cj}, V_{cj}, S_{cj}\) are printed.
After a sufficiently large number of trials \((k)\), the last printed \(S_k\), together with its \(U_{ck}, V_{ck}\), may be considered the root of the polynomial. In this case \(S_k\) will be sufficiently close to zero, while \(U_{ck}\) and \(V_{ck}\) will be close to the position of one of the roots.
After one of the roots has been found, the control circuit of the analog computer is switched to the “RETURN” mode; after pressing the “START” button, the next root is sought, and so on. It is evident that searching for all roots will require considerable time. In our case the maximum rate of generating pulses with random amplitude was limited by the speed of the printing device (0.5 sec per point; the test time of the \(j\)-th step is 2 sec).
The ability of the analog computer to produce continuous solutions makes it possible to modernize the method and speed it up considerably. We shall cover the plane \((U, jV)\) by a family of line segments whose endpoint coordinates are generated randomly. The covering of a region by a system of straight lines turns out to be
Fig. 4.
much denser and accelerates the process of solving a polynomial equation on an iterative analog computer by several dozen times.
With continuous motion along such a straight line, we find the minimum of the function \(S(U,V)\); in this case the instant at which the MIN circuit reaches the minimum is recorded, and the contacts of relay \(P_1\) not only control the MIN circuit, but at the same time control the auxiliary hold circuits F-1 and F-2, which store the voltages \(U_l\) and \(V_l\) at the moment when the function \(S_l(U,V)\) passes through the minimum. After each trial pass along the straight line, the values \(U_l\) and \(V_l\), stored by the hold circuits F-1 and F-2, and the minimum value of the function \(S_l^{\min}(U,V)\) on the \(l\)-th straight line are printed. After several trials, from consideration of all \(S_l^{\min}(U,V)\) it is easy to find the roots (or points in their nearest neighborhoods) \(U_l^{\text{root}}\), \(V_l^{\text{root}}\) for which \(S_l^{\min}(U,V) \approx 0\).
The block diagram for solving the problem by the modified Monte Carlo method is shown in Fig. 4. The circuit differs only slightly from the preceding one (Fig. 1). Additional hold circuits and blocks for forming line segments (BOLS) have been introduced. As the BOLS circuit, an integrator with a variable limit is used; the limiting level is equal to the magnitude of the input signal (Fig. 4). The results of the solution are printed by an electronic digital recorder, EDR.
Thus, the proposed solution method makes it possible to significantly accelerate the process of solving many types of equations on an analog computer (partial differential equations, polynomial equations, etc.) by the Monte Carlo method, which, in turn, proves to be simpler than many other solution methods and leads to the goal more rapidly.
REFERENCES
-
L. Levin, Methods for Solving Technical Problems on Analog Computers, Moscow, Mir, 1966.
-
N. I. Titov, S. S. Shishman. “Models of Stochastic Processes.” In: Computing Technology in Control. Moscow, Nauka, 1966, pp. 444–452.
-
D. M. Mitrovic, “Automatic plotting of characteristic curves and analog solution of algebraic equations,” Commun. and Electron., 1962, No. 58, pp. 701–703.
-
S. Fifer, Analogue Computation, Vol. II, McGraw Hill Book Co., N. Y., 1961.
-
W. Giloi, S. Lauber, Analogrechnen, Springer-Verlag, Berlin, 1963.