×

The complexity of partial derivatives. (English) Zbl 0498.68028

Summary: Let \(L\) denote the nonscalar complexity in \(k(x_1,\ldots, x_n)\). We prove \[ L(f,\partial f/\partial x_1,\ldots,\partial f/\partial x_n)\leq 3L(f). \] Using this we determine the complexity of single power sums, single elementary symmetric functions, the resultant and the discriminant as root functions, up to order of magnitude. Also we linearly reduce matrix inversion to computing the determinant.

MSC:

68Q25 Analysis of algorithms and problem complexity
65F05 Direct numerical methods for linear systems and matrix inversion
65F40 Numerical computation of determinants
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Borodin, A.; Munro, I., The Computational Complexity of Algebraic and Numeric Problems (1975), American Elsevier: American Elsevier New York · Zbl 0404.68049
[2] Heintz, J., Definability bounds of first order theories of algebraically closed fields, extended abstract, (Budach, I., Fundamentals of Computation Theory FCT ’79 (1979), Akademic-Verlag: Akademic-Verlag Berlin), 160-166 · Zbl 0439.03003
[3] Knuth, D. F., The Art of Computer Programming. Vol. II: Seminumerical Algorithms (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0191.18001
[4] Schnorr, C. P., An extension of Strassen’s degree bound, SIAM J. Comput., 10, 371-382 (1981) · Zbl 0475.68017
[5] Strassen, V., Gaussian elimination is not optimal, Numer. Math., 13, 354-356 (1969) · Zbl 0185.40101
[6] Strassen, V., Berechnung und Programm I, Acta Informat., 1, 320-335 (1972) · Zbl 0252.68018
[7] Strassen, V., Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numer. Math., 20, 238-251 (1973) · Zbl 0251.65036
[8] Strassen, V., Vermeidung von Divisionen, Crelle J. Reine Angew. Math., 264, 184-202 (1973) · Zbl 0294.65021
[9] Valiant, L. G., Reducibility by algebraic projections, (Logic and Algorithmic. Logic and Algorithmic, International Symposium held in honour of Ernst Specker. Logic and Algorithmic. Logic and Algorithmic, International Symposium held in honour of Ernst Specker, L’Enseignement Math (1982), Genève) · Zbl 0474.68062
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.