Optimization of computational algorithms

The choice of an optimal computational algorithm in the solution of applied problems or in the elaboration of systems of standard programs. When solving a concrete problem, the optimal tactic can be not to optimize the solution method, but to opt for a standard program or to use the simplest method for which the composition of a program is reasonably straightforward.

The theoretical formulation of the question of optimization of computational algorithms is based on the following principles. When choosing a method for solving a problem, the researcher concentrates on certain properties, and his choice of the algorithm depends on these, while the algorithm will also be used to solve other problems possessing these properties. For this reason, in the theoretical study of algorithms one introduces a class of problems $ P $ which possess specific properties. When choosing a solution method, the researcher has a set $ M $ of solution methods at his disposal. When using a method $ m $ to solve a problem $ p $, the solution obtained will have a certain error $ \epsilon ( p, m) $. The quantity

$$ E( P, m) = \sup _ {p \in P } | \epsilon ( p, m) | $$

is called the error of the method $ m $ in the class $ P $, while

$$ E( P, M) = \inf _ {m \in M } E( P, m) $$

is called the optimal estimate of the error in $ P $ for the methods from $ M $. If a method exists such that

$$ E( P, m _ {0} ) = E( P, M), $$

then this method is said to be optimal. A scheme of studying the problem of optimization of computational algorithms, dating back to A.N. Kolmogorov [2], considers the set of problems of computing the integral

$$ I( f) = \int\limits _ { 0 } ^ { 1 } f( x) dx $$

given the condition $ | f ^ { ( n) } | \leq A $, and where $ M $ is the set of all possible quadratures

$$ I( f ) \approx \sum_{j=1}^ { N } C _ {j} f( x _ {j} ) . $$

Each quadrature is defined by the totality of $ 2N $ numbers $ C _ {j} $ and $ x _ {j} $. The problem of the minimum quantity of information (see [2], [3]) needed to recover a function from a given class with required accuracy can also be included in this scheme. A more complex formulation of the problem is examined in [4], in which the amount of work involved in realizing the algorithm in a specific sense is commensurate with the amount of memory used. Optimal algorithms exist for only an insignificant number of type of problems [1]. However, for a large number of computational problems, methods have been created which are almost optimal in their asymptotic characteristics (see [5]–[8]).

Research into the characteristics of computational algorithms which are optimal in their class (see [5], [7]) comprises two parts: creating concrete solution methods with the best possible characteristics, and obtaining estimates from below of the characteristics of computational algorithms (see [2]–[4], [9]). In essence, the first part of the question is a basic problem of the theory of numerical methods and in most cases it is studied independently of the optimization problem. Obtaining estimates from below usually reduces to an estimation from below of the $ \epsilon $- entropy or of the width of the corresponding spaces; this is sometimes carried out independently, using the same techniques as are used in obtaining the estimates mentioned.

Computational algorithms may be divided into passive ones and active ones. A passive algorithm for solving a problem does not depend on the information obtained in solving the problem, whereas an active algorithm does. When computing an integral, the information used about the function is usually information on its values at $ N $ points. For a passive algorithm, the integral is computed using the formula

$$ I( f) \approx \sum_{j=1}^ { N } C _ {j} f( P _ {j} ), $$

where the weights $ C _ {j} $ and $ P _ {j} $ from the domain $ \Omega $ of definition of $ f $ are previously defined. Active algorithms for computing the integral are included in the following scheme: A point $ P _ {1} \in \Omega $ and the functions

$$ Q _ {q} = \Phi _ {q} ( Q _ {1} \dots Q _ {q-1} ; y _ {1} \dots y _ {q-1} ),\ \ q = 2 \dots N, $$

$$ S _ {N} ( Q _ {1} \dots Q _ {N} ; y _ {1} \dots y _ {N} ) $$

are given, where $ y _ {j} $, $ S _ {N} $ are numbers, $ Q _ {j} \in \Omega $. The following quantities are successively computed:

$$ f( P _ {1} ), P _ {2} = \Phi _ {2} ( P _ {1} ; f( P _ {1} )), f( P _ {2} ), $$

$$ P _ {3} = \Phi _ {3} ( P _ {1} , P _ {2} ; f( P _ {1} ), f( P _ {2} )) \dots f( P _ {N} ), $$

and it is supposed that

$$ I( f) \approx S _ {N} ( P _ {1} \dots P _ {N} ; f( P _ {1} ) \dots f( P _ {N} )). $$

In convex classes of integrands which are centrally symmetric with respect to the function $ f \equiv 0 $, the optimal estimate in the class of passive algorithms coincides with the optimal estimate in the class of active algorithms (see [10], [11]).

In the practice of numerical integration, active algorithms of the type of integration algorithms with automatic choice of steps (see [10]) have shown their superiority over passive algorithms. This supports the generally held point of view that a formal scheme of optimization of computational algorithms does not often include specific real problems. When solving optimization problems (especially minimization problems), passive algorithms are hardly used (see [12], [13]). As an upper bound for the amount of work involved in calculating one value of a function from some class $ F $ one implicitly takes the unit of amount of work of the algorithm. There are other possible approaches to estimating the optimality of the characteristics of an algorithm. For example, the amount of work involved in computing a functional $ l( f ) $ from a set of functionals $ L( f ) $ can be taken as the unit of amount of work. In this case, a lower bound for the amount of work involved in realizing the algorithms is obtained using the theory of widths (see [14], [15]). The amount of work comprises not only the amount of work involved in obtaining information on initial data, but also the amount of work involved in processing the information. At the present time, it appears that one cannot cite examples of classes of real computational problems in which lower bounds for the amount of work involved in realizing the algorithms can be obtained which differ from the bounds on the information of the type under consideration. However, for a number of non-computational problems of this type, bounds are known (see Algorithm, computational complexity of an and Algorithm, complexity of description of an).

When research into problems of optimization of computational algorithms aims to solve problems on a computer, the problem has extra nuances related to the stability of the algorithm in relation to the error of computation, and to the restriction on the volume of the different forms of memory used (see Computational algorithm). The problem of optimizing computational algorithms has been treated above as a problem of optimization of computational algorithms in a class of problems. In practice, the problem of optimization of computational algorithms for a concrete problem is of vital interest (see [10], [16]). The formulation of one problem of optimization (see [16]) is as follows. A differential equation is integrated using the Runge–Kutta method with a variable step. An estimate is made of the principal term of the estimation error. This estimate is then optimized through a distribution of the points of integration (in general, for a given number of points). This approach to the problem of optimization has a crucial bearing on the development of the theory and on the practice of active algorithms of numerical integration.

References

[1]	S.M. Nikol'skii, "Quadrature formulae" , H.M. Stationary Office , London (1966) (Translated from Russian)
[2]	A.N. Kolmogorov, "On certain asymptotic characteristics of totally bounded metric spaces" Dokl. Akad. Nauk. SSSR , 108 : 3 (1956) pp. 385–388 (In Russian)
[3]	A.N. Kolmogorov, V.M. Tikhomirov, "-entropy and -capacity of sets in function spaces" Uspekhi Mat. Nauk. , 14 : 2 (1959) pp. 3–86 (In Russian)
[4]	A.G. Vitushkin, "Estimation of the complexity of the tabulation problem" , Moscow (1959) (In Russian)
[5]	I. Babushka, S.L. Sobolev, "Optimization of numerical processes" Aplikace Mat. , 10 (1965) pp. 96–129 (In Russian)
[6]	N.S. Bakhvalov, "Optimal methods for solving problems" Aplikace Mat. , 13 (1968) pp. 27–38 (In Russian)
[7]	N.S. Bakhvalov, "About optimisation of numerical methods" , Proc. Internat. Congress Mathematicians Nice, 1970 , 3 , Gauthier-Villars (1972) pp. 289–295
[8]	N.S. Bakhvalov, "On optimal convergence estimates for quadrature processes and integration methods of Monte-Carlo type on function classes" , Numerical Methods for Solving Differential and Integral Equations and Quadrature Formulas , Moscow (1964) pp. 5–63 (In Russian)
[9]	N.S. Bakhvalov, "A lower bound for the asymptotic characteristics of classes of functions with dominating mixed derivative" Math. Notes , 12 : 6 (1972) pp. 833–838 Mat. Zametki , 12 : 6 (1972) pp. 655–664
[10]	N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)
[11]	N.S. Bakhvalov, "On the optimality of linear methods for operator approximation in convex classes of functions" USSR Math. Math. Phys. , 11 : 4 (1971) pp. 244–249 Zh. Vychisl. Mat. i Mat. Fiz. , 11 : 4 (1971) pp. 1010–1018
[12]	D.J. Wilde, "Optimum seeking methods" , Prentice-Hall (1964)
[13]	F.P. Vasil'ev, "Numerical methods for solving extremal problems" , Moscow (1980) (In Russian)
[14]	L.A. Oganesyan, LA. Rukhovets, "Variational-difference methods for solving elliptic equations" , Erevan (1979) (In Russian)
[15]	V.M. Tikhomirov, "Some problems in approximation theory" , Moscow (1976) (In Russian)
[16]	A.N. Tikhonov, A.D. Gorbunov, "Estimates of the error of a Runge–Kutta method and the choice of optimal meshes" USSR Comp. Math. Math. Phys. , 4 : 2 (1964) pp. 30–42 Zh. Vychisl. Mat. i Mat. Fiz. , 4 : 2 (1964) pp. 232–241