Minimization of the labour of calculation

minimization of the computational work

A branch of modern computational mathematics, devoted to the design and investigation of methods which allow one to find an approximate solution, with preassigned accuracy $ \epsilon > 0 $, of a problem $ P $ from a class $ \{ P \} $ with the least computational cost (least volume of calculation). This branch of computational mathematics can be related to the more general branch concerned with the problem of optimizing methods (see, for example, [1], [2]) in which alongside the problem of minimizing the computational work one considers the dual problem of finding, among the approximation methods requiring roughly the same amount of calculation, a method with maximal accuracy (least error). The latter problem is characteristic, for example, of problems in numerical integration in which the number of points of integration, which measures the computational work, is fixed.

Let $ \epsilon \geq 0 $( usually $ \epsilon > 0 $, for $ \epsilon = 0 $ a precise solution of $ P $ is sought) be the required accuracy for the solution of a problem $ P $ from a given class $ \{ P \} $ of related problems, and let $ m $ be an admissible method for finding the solution of any problem from $ \{ P \} $; the set of such methods will be denoted by $ \{ m \} $. Let a number $ W _ {m} ( P , \epsilon ) > 0 $ characterize the computational cost when by using the method $ m $ a solution of $ P $ is to be found with accuracy $ \epsilon $, and put

$$ W _ {m} ( \{ P \} , \epsilon ) = \ \sup _ {P \in \{ P \} } W _ {m} ( P , \epsilon ) . $$

Then the minimization problem is to find a method $ m _ {0} $ such that

$$ W _ {m _ {0} } ( \{ P \} , \epsilon ) = \ \inf _ {m \in \{ m \} } \ W _ {m} ( \{ P \} , \epsilon ) , $$

that is, in essence one seeks an optimal method for solving not just a fixed problem $ P $, but a whole class of problems (optimization for a class). Mostly the minimization of the computational work is done in the asymptotic sense as $ \epsilon \rightarrow 0 $, $ N \rightarrow \infty $, where $ N $ is a parameter defining the "dimension" of the problem to be solved.

A method $ m _ {0} $ is called order optimal if the computational cost in it is at most finitely many times a quantity $ \underline{W} ( \{ P \} , \epsilon ) $ which is a lower estimate of the computational cost in any possible method; a method $ m _ {0} $ is called logarithmically optimal if

$$ \mathop{\rm ln} W _ {m _ {0} } ( \{ P \} , \epsilon ) = \ ( 1 + o ( 1) ) \mathop{\rm ln} \underline{W} ( \{ P \} , \epsilon ) . $$

The computational work $ W _ {m} ( P , \epsilon ) $ itself is usually characterized by the number of arithmetic operations generated by the method $ m $ in attaining the accuracy $ \epsilon $ in its realization on a conventional computer. To some extent this simplification is justified, since in many methods logical operations on real computers are performed in at most finitely many arithmetic operations. For admissible methods, as a rule, their stability with respect to rounding errors is required. It is important that the asymptotic growth of the amount of machine memory used in these methods is not too large.

To make this problem of minimizing the computational work concrete, the description of the class $ \{ P \} $ must be made precise and the metric space $ H $ which is used to define the accuracy of a solution of the resulting problem must be stated.

The solution of many such concrete minimization problems is not only of theoretical interest, but has also a great applied significance, allowing one to solve problems on computers with comparatively small expense of machine time. This is particularly important both for problems which require a large amount of calculations, characteristic for example of multi-dimensional problems in mathematical physics (see [2]–[8]), and for problems similar to the problems of calculating elementary functions and finding discrete Fourier transforms (see [1], [9]), which are standard and repeatedly used for the solution of other, more complex, problems. The problem of minimization of the computational work is fairly complicated and in many cases only a partial solution has been obtained.

In practice, for the solution of a problem of relatively small dimension and with no great accuracy, sometimes methods with poor asymptotic characteristics may require less machine time. Often, if the computational cost is acceptable, then the choice of the method is guided first of all by considerations of simplicity and reliability.

Suppose that the original problem is finite dimensional and that there are methods which give a precise solution in a finite number of arithmetic operations, if these operations are performed without rounding errors. As examples one can take the problem of calculating the value of a polynomial $ p _ {N} ( x) $ of degree $ N $ for given values of $ x $ with $ | x | \leq 1 $, the multiplication of two square matrices of order $ N $, the solution of a given system of algebraic equations $ A x = b $ with a square matrix of order $ N $, and the problem of finding the discrete Fourier transform (see [1], [9]):

$$ \tag{1 } v _ {n} = \ \sum _ { k= } 0 ^ { N- } 1 u _ {k} e ^ {- 2 \pi n i / N } ,\ \ n = 0 \dots N - 1 , $$

where $ i $ is the imaginary unit, the vector $ u = ( u _ {0} \dots u _ {n-} 1 ) $ is given and a vector $ v \equiv ( v _ {0} \dots v _ {n-} 1 ) $, $ N = 2 ^ {r} $, $ r= 0 , 1 \dots $ is sought. No concrete restrictions are imposed on the form of $ p _ {N} ( x) $, $ x \in [ - 1 , 1 ] $, $ A , b $, the number $ r $, and the vector $ u $, and, therefore, in each of these problems the admissible class $ \{ P \} $ consists of all problems of such form. In similar problems $ N $ takes the role of a parameter and special consideration is given to the behaviour of the computational cost $ W _ {m} ( P , 0 ) \equiv W _ {m} ( P ) $ as $ N \rightarrow \infty $. For the first of these problems Horner's method, writing $ p _ {N} ( x) $ in the form

$$ a _ {0} + x ( \dots + x ( a _ {N-} 1 + x a _ {N} ) \dots ) , $$

allows one to calculate $ p _ {N} ( X) $ using $ N $ multiplications and $ N $ additions. It has been proved (see [9]) that this method is optimal: There is no method which would require fewer additions and subtractions or fewer multiplications and divisions; the stability is acceptable if $ \sum _ {i} | a _ {i} | $ is not large (see [1]).

For the second and third problems there are a number of methods giving solutions as $ N \rightarrow \infty $ in $ W ( N) \sim N ^ {3} $ arithmetic operations (see [1]) and they are actually applied in practice. The least computational cost among all methods known at present is attained in a method with estimate $ W ( N) \sim N ^ \alpha $, $ \alpha \approx 2.5 $( see [9], [10]). This method is rather complicated and for a number of reasons is at present interesting only from the theoretical point of view. It is not known (1989), whether there is even a logarithmically-optimal method. There is a conjecture that there exists a logarithmically-optimal method with $ W ( N) $ arithmetic operations, where

$$ \mathop{\rm ln} W ( N) = 2 \mathop{\rm ln} N + o ( \mathop{\rm ln} N ) . $$

For problem (1), the subject of harmonic analysis, the simplest methods require $ \sim N ^ {2} $ arithmetic operations with complex numbers. In 1965 a method was suggested which allows one to find the vector in $ W ( N) \sim N \mathop{\rm ln} N $ arithmetic operations (see [1], [9]); this method is called the method of the fast discrete Fourier transform. This method is logarithmically optimal; it is widely used in practice. There are a large number of similar minimization problems, solved and unsolved (see [9], [10]); order-optimal or logarithmically-optimal estimates of the computational cost for finding the solution of similar problems may be considered as an indicator of their complexity.

Minimization of the computational work for the solution of grid systems of equations, which arise either in difference methods or in projection-grid methods (finite-element methods) for the approximate solution of boundary value problems for equations and systems of equations of strongly-elliptic type, has a special theoretical and applied significance, and, usually, is accomplished asymptotically as $ N \rightarrow \infty $, where $ N $ is the number of unknowns in the system, and as $ \epsilon \rightarrow 0 $. For the solution of the simplest difference analogues of certain boundary value problems for the Poisson equation in a rectangle or a parallelopiped, certain direct methods have been applied successfully which are logarithmically optimal and require $ O ( N \mathop{\rm ln} N ) $ arithmetic operations (see [3], [5], [8], [11], [12]). In the case of a rectangle (see [13]) an order-optimal method is known which requires $ O ( N) $ operations. Using the same iteration method one can obtain a logarithmically-optimal estimate of the type

$$ W = O ( N \mathop{\rm ln} N | \mathop{\rm ln} \epsilon | ) , $$

where $ \epsilon $ is the accuracy of the solution of the system in some metric, for a fairly broad class of discrete boundary value problems in a parallelopipedal grid for linear and non-linear strongly-elliptic systems in certain ideal domains (see [2]–[8], [14]). (For example, in a plane $ Q $ they may be generated from a finite number of rectangles with sides parallel to the coordinate axes; and in a three-dimensional space $ Q $ they may be decomposed by a finite number of plane sections parallel to the given coordinate planes into parallelopipeds with boundaries parallel to the coordinate planes.) For more complicated domains $ Q $ the use of grids, topologically equivalent to the above grid domains $ Q $, and certain types of projection-grid methods often allows one to obtain systems of equations which are as effectively solvable as in the case of ideal domains (see [3], [8], [15], [16]). Here the right-hand sides of these systems can be arbitrary vectors; if it is taken into account that they arise in special form as functionals on sufficiently smooth functions, then methods have been constructed with computational cost $ O ( N \mathop{\rm log} N ) $ and even $ O ( N) $, under the condition that $ \epsilon \sim N ^ {- \alpha } $, $ \alpha > 0 $. Methods of the latter type, for the solution of a problem on a given grid, use a sequence of similar problems on sparser grids (see [8], [16]).

There are methods which allow one to find with accuracy $ \epsilon $ the minor eigen values and corresponding eigen functions for certain grid analogues of elliptic eigen value problems, at an expense of $ O ( N \mathop{\rm ln} N | \mathop{\rm ln} \epsilon | ) $, or even $ O ( N \mathop{\rm ln} N ) $( for $ \epsilon \sim N ^ {- \alpha } $, $ \alpha > 0 $), operations (see [8], [15], [16]).

Let the problem $ P $ be to solve a well-posed operator equation

$$ \tag{2 } L ( u) = f , $$

where the operator $ L $ acts from $ H $ to $ F $, and $ H $ and $ F $ are infinite-dimensional Banach spaces. Let $ \{ P \} $ be the class of such problems with different $ f $ for which the solution to (2) belongs to some compact set $ U $. Usually $ U $ is given by one condition:

$$ \tag{3 } \| u \| _ {H ^ \prime } \leq R , $$

where $ H ^ \prime $ is a Banach space imbedded in $ H $. If $ u \in U $ is sought with accuracy $ \epsilon > 0 $ in the norm of $ H $, then often information estimates, uniform with respect to all $ u \in U $, are known for the least dimension $ \underline{N} \equiv \underline{N} ( \epsilon ) $ of a vector $ v _ {\underline{N} } \equiv ( v _ {1} \dots v _ {\underline{N} } ) $, the assignment of which allows one to obtain an element

$$ \tag{4 } \widehat{v} _ {\underline{N} } \equiv \sum _ { i= } 1 ^ { {\underline{N} } } v _ {i} \psi _ {i} ( z) \in H \ \textrm{ with } \| u - \widehat{v} _ {\underline{N} } \| _ {H} \leq \epsilon $$

(see [1], [2], [8], [17], [18]). These lower estimates for $ N ( \epsilon ) $ give obvious lower estimates for the required computational cost in any admissible method. In a number of boundary value problems for strongly-elliptic systems variants of the projection-grid method have been constructed which lead to algebraic systems of equations

$$ \tag{5 } L _ {N} ( \overline{u}\; _ {N} ) = \overline{f}\; _ {N} $$

in $ N $ unknowns, for which, first, order-optimal iteration methods of approximate solution are known and, secondly, the corresponding functions $ \widehat{u} _ {N} $ of the vectors $ \overline{u}\; _ {N} $( see (4)) are $ \epsilon $- approximations in $ H $ of the solution of (2), where $ N \leq k \underline{N} ( \epsilon ) $ and $ k $ is a constant not depending on $ \epsilon $( see [7], [8], [16]). If the effort in forming (5) is not taken into account, these methods lead to order-minimal estimates for the computational cost. For example, for a second-order elliptic equation, where $ H = W _ {2} ^ {1} ( \Omega ) $, $ H ^ \prime = W _ {2} ^ {2} ( \Omega ) $( $ W _ {2} ^ {k} ( \Omega ) $ are the Sobolev spaces [19]), if $ \Omega $ is a domain in the plane, the estimate $ \sim \epsilon ^ {-} 2 $ for the expense of the number of arithmetic operations is obtained. The computational work in forming (5) can often also be estimated as $ O ( N \mathop{\rm ln} N ) $ if information on the given functions in the corresponding spaces is used. In particular, in the example $ f $ must be considered as an element of $ F = W _ {2} ^ {-} 1 ( \Omega ) $, but not of $ L _ {2} ( \Omega ) $( see [16]). A similar kind of estimate has been obtained for certain differential eigen value problems (see [8], [15]).

Questions on the minimization of the computational work for the solution of integral equations, ordinary differential equations and non-stationary partial differential equations have also been discussed (see, for example, [1]–[4], [20]–[22]).

References

[1]	N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)
[2]	J.F. Traub, H. Wozniakowski, "A general theory of optimal algorithms" , Acad. Press (1980)
[3]	G.I. Marchuk, "Methods of numerical mathematics" , Springer (1975) (Translated from Russian)
[4]	A.A. Samarskii, "Theorie der Differenzverfahren" , Akad. Verlagsgesell. Geest u. Portig K.-D. (1984) (Translated from Russian)
[5]	A.A. Samarskii, E.S. Nikolaev, "Numerical methods for grid equations" , 1–2 , Birkhäuser (1989) (Translated from Russian)
[6]	R. Glowinski, "Numerical methods for nonlinear variational problems" , Springer (1984)
[7]	V.G. Korneev, "Schemes for the finite element method with a high order of accuracy" , Leningrad (1977) (In Russian)
[8]	A.G. D'yakonov, "Minimization of computational work. Asymptotically-optimal algorithms" , Moscow (1989) (In Russian)
[9]	A. Borodin, I. Munro, "The computational complexity of algebraic and numeric problems" , Amer. Elsevier (1975)
[10]	J.F. Traub (ed.) , Analytic computational complexity , Acad. Press (1976)
[11]	P. Concus, G. Golub, "Use of fast direct methods for the efficient numerical solution of nonseparable elliptic equations" SIAM J. Numer. Anal. , 10 (1973) pp. 1103–1120
[12]	R.J. Barker, "Advanced techniques for the direct numerical solution of Poisson's equation" , Mathematical Models and Numerical Methods , Banach Center Publ. , 3 , PWN (1978) pp. 255–268
[13]	R.E. Bank, D.J. Rose, "Extrapolated fast direct algorithms for elliptic boundary value problems" , Algorithms and complexity (Proc. Symp. Carnegie-Mellon Univ.) , Acad. Press (1976) pp. 201–249
[14]	G.I. Marchuk, Yu.A. Kuznetsov, A.M. Matsokin, "Fictitious domain and domain decomposition methods" Soviet J. Numer. Anal. Math. Modelling , 1 : 1 (1986) pp. 3–35
[15]	E.G. D'yakonov, "Effective methods for solving eigenvalue problems with fourth-order elliptic operators" Soviet J. Anal. Math. Modelling , 1 : 1 (1986) pp. 59–82
[16]	U. Trottenberg (ed.) , Multigrid Methods. Proc. Köln-Porz, 1981 , Lect. notes in math. , 960 , Springer (1982)
[17]	, Theoretical foundations and construction of numerical algorithms of problems of mathematical physics , Moscow (1979) pp. 45–118 (In Russian)
[18]	V.M. Tikhomirov, "Some problems in approximation theory" , Moscow (1976) (In Russian)
[19]	S.L. Sobolev, "Applications of functional analysis in mathematical physics" , Amer. Math. Soc. (1963) (Translated from Russian)
[20]	K.V. Emel'yanov, A.M. Il'in, "Number of arithmetical operations necessary for the approximate solution of Fredholm integral equations of the second kind" USSR Comp. Math. Math. Phys. , 7 : 4 (1967) pp. 259–266 Zh. Vychisl. Mat. i Mat. Fiz. , 7 : 4 (1967) pp. 905–910
[21]	V.V. Ivanov, "Optimal algorithms for the numerical solution of singular integral equations" , Continuum Mechanics and Related Problems in Anal. , Moscow (1972) pp. 209–219 (In Russian)
[22]	Yu.R. Akopyan, L.A. Oganesyan, "A variational-difference method for solving two-dimensional linear parabolic equations" USSR Comp. Math. Math. Phys. , 17 : 1 (1977) pp. 101–110 Zh. Vychisl. Mat. Mat. Fiz. , 17 : 1 (1977) pp. 109–118

References

[a1]	J.F. Traub, H. Wozniakowski, "Information, uncertainty, complexity" , Addison-Wesley (1983)