Geodesic
On the complexity of the computation of differentials and gradients
Diskretnaya Matematika, Tome 17 (2005) no. 3, pp. 45-67.

Voir la notice de l'article provenant de la source Math-Net.Ru

We obtain bounds for the complexity of circuit realisation of the system of differentials of orders from one to $k$ of an arbitrary elementary function in terms of the circuit complexity of this function. Similar bounds are obtained for the complexities of realisation of the Jacobian and Hessian matrices. We point out some applications to deduction of bounds for complexities of polynomials in several variables, linear transformations, and quadratic forms.This research was supported by the Russian Foundation for Basic Research, grants 02–01–10142 and 02–01–00985, and by the Program of the President of the Russian Federation for supporting the leading scientific schools, grant 1807.2003.1. 
@article{DM_2005_17_3_a5,
     author = {S. B. Gashkov and I. B. Gashkov},
     title = {On the complexity of the computation of differentials and gradients},
     journal = {Diskretnaya Matematika},
     pages = {45--67},
     publisher = {mathdoc},
     volume = {17},
     number = {3},
     year = {2005},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2005_17_3_a5/}
}
TY  - JOUR
AU  - S. B. Gashkov
AU  - I. B. Gashkov
TI  - On the complexity of the computation of differentials and gradients
JO  - Diskretnaya Matematika
PY  - 2005
SP  - 45
EP  - 67
VL  - 17
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2005_17_3_a5/
LA  - ru
ID  - DM_2005_17_3_a5
ER  - 
%0 Journal Article
%A S. B. Gashkov
%A I. B. Gashkov
%T On the complexity of the computation of differentials and gradients
%J Diskretnaya Matematika
%D 2005
%P 45-67
%V 17
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2005_17_3_a5/
%G ru
%F DM_2005_17_3_a5
S. B. Gashkov; I. B. Gashkov. On the complexity of the computation of differentials and gradients. Diskretnaya Matematika, Tome 17 (2005) no. 3, pp. 45-67. http://geodesic.mathdoc.fr/item/DM_2005_17_3_a5/

[1] Baur W., Strassen V., “The complexity of partial derivatives”, Theoret. Computer Sci., 22 (1983), 317–330 | DOI | MR | Zbl

[2] Kim K. V., Nesterov Yu. E., Cherkasskii B. V., “Otsenka trudoemkosti vychisleniya gradienta”, Dokl. AN SSSR, 275:6 (1984), 1306–1309 | MR | Zbl

[3] Knut D., Iskusstvo programmirovaniya. Osnovnye algoritmy, t. 1, Vilyams, Moskva, 2000

[4] Linnainmaa S., “Taylor expansion of the accumulated rounding error”, BIT, Nord. Tidskr. Inf.-Behandl., 16 (1976), 146–160 | MR | Zbl

[5] Grigorev D. Yu., “Nizhnie otsenki v algebraicheskoi slozhnosti vychislenii”, Teoriya slozhnosti vychislenii, Zapiski nauchnykh seminarov LOMI, 118 (1982), 25–82 | MR

[6] Gashkov S., Kochergin V., “On addition chains of vectors, gate circuits, and the complexity of computation of power”, Syberian Adv. Math., 4:4 (1994), 1–16 | MR

[7] Heintz J., Sievekieng M., “Lower bounds for polynomials with algebraic coefficients”, Theoret. Computer Sci., 11:3 (1980), 321–330 | DOI | MR | Zbl

[8] Arkhipov G.I., Sadovnichii V. A., Chubarikov V. N., Lektsii po matematicheskomu analizu, Vysshaya shkola, Moskva, 1999

[9] Gursa E., Kurs matematicheskogo analiza, ONTI SSSR, Moskva, 1936

[10] Gashkov S.B., Chubarikov V. N., Arifmetika. Algoritmy. Slozhnost vychislenii, Vysshaya shkola, Moskva, 2000

[11] von zur Gathen J., Gerhard J., Modern computer algebra, Cambridge Univ. Press, Cambridge, 1999 | MR

[12] Akho F., Khopkroft Dzh., Ulman Dzh., Postroenie i analiz vychislitelnykh algoritmov, Mir,, Moskva, 1979 | MR | Zbl

[13] Riordan Dzh., Vvedenie v kombinatornyi analiz, IL, Moskva, 1963

[14] Riordan Dzh., Kombinatornye tozhdestva, Nauka, Moskva, 1982 | MR | Zbl

[15] Bell E. T., “Exponential polynomials”, Ann. Math., 35 (1934), 258–277 | DOI | MR | Zbl

[16] Brent R. P., Kung H. T., “Fast algorithms for manipulating formal power series”, J. Assoc. Comput. Mach., 25:4 (1978), 581–595 | MR | Zbl

[17] Brent R. P., “Multiple-precision zero-finding methods and the complexity of elementary function evaluation”, Analytic Computational Complexity, Proc. Symp. (Carnegie–Mellon Univ., Pittsburgh 1975), Academic Press, New York, 1976, 151–176 | MR

[18] Steffensen J. F., “The poweroid, an extension of the mathematical notion of power”, Acta Math., 73 (1941), 333–366 | DOI | MR | Zbl