View source for 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m0640001.png" />, of a problem <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m0640002.png" /> from a class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m0640003.png" /> 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, [[#References|[1]]], [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m0640004.png" /> (usually <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m0640005.png" />, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m0640006.png" /> a precise solution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m0640007.png" /> is sought) be the required accuracy for the solution of a problem <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m0640008.png" /> from a given class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m0640009.png" /> of related problems, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400010.png" /> be an admissible method for finding the solution of any problem from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400011.png" />; the set of such methods will be denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400012.png" />. Let a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400013.png" /> characterize the computational cost when by using the method <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400014.png" /> a solution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400015.png" /> is to be found with accuracy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400016.png" />, and put

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400017.png" /></td> </tr></table>

Then the minimization problem is to find a method <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400018.png" /> such that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400019.png" /></td> </tr></table>

that is, in essence one seeks an optimal method for solving not just a fixed problem <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400020.png" />, but a whole class of problems (optimization for a class). Mostly the minimization of the computational work is done in the asymptotic sense as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400021.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400022.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400023.png" /> is a parameter defining the  "dimension"  of the problem to be solved.

A method <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400024.png" /> is called order optimal if the computational cost in it is at most finitely many times a quantity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400025.png" /> which is a lower estimate of the computational cost in any possible method; a method <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400026.png" /> is called logarithmically optimal if

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400027.png" /></td> </tr></table>

The computational work <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400028.png" /> itself is usually characterized by the number of arithmetic operations generated by the method <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400029.png" /> in attaining the accuracy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400030.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400031.png" /> must be made precise and the metric space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400032.png" /> 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 [[#References|[2]]]–[[#References|[8]]]), and for problems similar to the problems of calculating elementary functions and finding discrete Fourier transforms (see [[#References|[1]]], [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400033.png" /> of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400034.png" /> for given values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400035.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400036.png" />, the multiplication of two square matrices of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400037.png" />, the solution of a given system of algebraic equations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400038.png" /> with a square matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400039.png" />, and the problem of finding the discrete Fourier transform (see [[#References|[1]]], [[#References|[9]]]):

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400040.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400041.png" /> is the imaginary unit, the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400042.png" /> is given and a vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400043.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400044.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400045.png" /> is sought. No concrete restrictions are imposed on the form of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400046.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400047.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400048.png" />, the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400049.png" />, and the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400050.png" />, and, therefore, in each of these problems the admissible class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400051.png" /> consists of all problems of such form. In similar problems <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400052.png" /> takes the role of a parameter and special consideration is given to the behaviour of the computational cost <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400053.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400054.png" />. For the first of these problems Horner's method, writing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400055.png" /> in the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400056.png" /></td> </tr></table>

allows one to calculate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400057.png" /> using <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400058.png" /> multiplications and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400059.png" /> additions. It has been proved (see [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400060.png" /> is not large (see [[#References|[1]]]).

For the second and third problems there are a number of methods giving solutions as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400061.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400062.png" /> arithmetic operations (see [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400063.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400064.png" /> (see [[#References|[9]]], [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400065.png" /> arithmetic operations, where

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400066.png" /></td> </tr></table>

For problem (1), the subject of harmonic analysis, the simplest methods require <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400067.png" /> arithmetic operations with complex numbers. In 1965 a method was suggested which allows one to find the vector in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400068.png" /> arithmetic operations (see [[#References|[1]]], [[#References|[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 [[#References|[9]]], [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400069.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400070.png" /> is the number of unknowns in the system, and as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400071.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400072.png" /> arithmetic operations (see [[#References|[3]]], [[#References|[5]]], [[#References|[8]]], [[#References|[11]]], [[#References|[12]]]). In the case of a rectangle (see [[#References|[13]]]) an order-optimal method is known which requires <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400073.png" /> operations. Using the same iteration method one can obtain a logarithmically-optimal estimate of the type

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400074.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400075.png" /> 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 [[#References|[2]]]–[[#References|[8]]], [[#References|[14]]]). (For example, in a plane <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400076.png" /> they may be generated from a finite number of rectangles with sides parallel to the coordinate axes; and in a three-dimensional space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400077.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400078.png" /> the use of grids, topologically equivalent to the above grid domains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400079.png" />, 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 [[#References|[3]]], [[#References|[8]]], [[#References|[15]]], [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400080.png" /> and even <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400081.png" />, under the condition that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400082.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400083.png" />. 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 [[#References|[8]]], [[#References|[16]]]).

There are methods which allow one to find with accuracy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400084.png" /> the minor eigen values and corresponding eigen functions for certain grid analogues of elliptic eigen value problems, at an expense of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400085.png" />, or even <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400086.png" /> (for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400087.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400088.png" />), operations (see [[#References|[8]]], [[#References|[15]]], [[#References|[16]]]).

Let the problem <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400089.png" /> be to solve a well-posed operator equation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400090.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>

where the operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400091.png" /> acts from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400092.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400093.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400094.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400095.png" /> are infinite-dimensional Banach spaces. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400096.png" /> be the class of such problems with different <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400097.png" /> for which the solution to (2) belongs to some compact set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400098.png" />. Usually <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m06400099.png" /> is given by one condition:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000100.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000101.png" /> is a Banach space imbedded in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000102.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000103.png" /> is sought with accuracy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000104.png" /> in the norm of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000105.png" />, then often information estimates, uniform with respect to all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000106.png" />, are known for the least dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000107.png" /> of a vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000108.png" />, the assignment of which allows one to obtain an element

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000109.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>

(see [[#References|[1]]], [[#References|[2]]], [[#References|[8]]], [[#References|[17]]], [[#References|[18]]]). These lower estimates for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000110.png" /> 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

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

in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000112.png" /> unknowns, for which, first, order-optimal iteration methods of approximate solution are known and, secondly, the corresponding functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000113.png" /> of the vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000114.png" /> (see (4)) are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000115.png" />-approximations in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000116.png" /> of the solution of (2), where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000117.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000118.png" /> is a constant not depending on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000119.png" /> (see [[#References|[7]]], [[#References|[8]]], [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000120.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000121.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000122.png" /> are the Sobolev spaces [[#References|[19]]]), if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000123.png" /> is a domain in the plane, the estimate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000124.png" /> for the expense of the number of arithmetic operations is obtained. The computational work in forming (5) can often also be estimated as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000125.png" /> if information on the given functions in the corresponding spaces is used. In particular, in the example <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000126.png" /> must be considered as an element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000127.png" />, but not of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064000/m064000128.png" /> (see [[#References|[16]]]). A similar kind of estimate has been obtained for certain differential eigen value problems (see [[#References|[8]]], [[#References|[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, [[#References|[1]]]–[[#References|[4]]], [[#References|[20]]]–[[#References|[22]]]).

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  N.S. Bakhvalov,   "Numerical methods: analysis, algebra, ordinary differential equations" , MIR  (1977)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  J.F. Traub,   H. Wozniakowski,   "A general theory of optimal algorithms" , Acad. Press  (1980)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  G.I. Marchuk,   "Methods of numerical mathematics" , Springer  (1975)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A.A. Samarskii,   "Theorie der Differenzverfahren" , Akad. Verlagsgesell. Geest u. Portig K.-D.  (1984)  (Translated from Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  A.A. Samarskii,   E.S. Nikolaev,   "Numerical methods for grid equations" , '''1–2''' , Birkhäuser  (1989)  (Translated from Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  R. Glowinski,   "Numerical methods for nonlinear variational problems" , Springer  (1984)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  V.G. Korneev,   "Schemes for the finite element method with a high order of accuracy" , Leningrad  (1977)  (In Russian)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  A.G. D'yakonov,   "Minimization of computational work. Asymptotically-optimal algorithms" , Moscow  (1989)  (In Russian)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  A. Borodin,   I. Munro,   "The computational complexity of algebraic and numeric problems" , Amer. Elsevier  (1975)</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  J.F. Traub (ed.) , ''Analytic computational complexity'' , Acad. Press  (1976)</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[13]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[14]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[15]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[16]</TD> <TD valign="top">  U. Trottenberg (ed.) , ''Multigrid Methods. Proc. Köln-Porz, 1981'' , ''Lect. notes in math.'' , '''960''' , Springer  (1982)</TD></TR><TR><TD valign="top">[17]</TD> <TD valign="top"> , ''Theoretical foundations and construction of numerical algorithms of problems of mathematical physics'' , Moscow  (1979)  pp. 45–118  (In Russian)</TD></TR><TR><TD valign="top">[18]</TD> <TD valign="top">  V.M. Tikhomirov,   "Some problems in approximation theory" , Moscow  (1976)  (In Russian)</TD></TR><TR><TD valign="top">[19]</TD> <TD valign="top">  S.L. Sobolev,   "Applications of functional analysis in mathematical physics" , Amer. Math. Soc.  (1963)  (Translated from Russian)</TD></TR><TR><TD valign="top">[20]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[21]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[22]</TD> <TD valign="top">  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</TD></TR></table>



====Comments====


====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J.F. Traub,   H. Wozniakowski,   "Information, uncertainty, complexity" , Addison-Wesley  (1983)</TD></TR></table>