Abstract
We present a well-parallelizable algorithm which, taking a straight-line program for the evaluation of a vectorial field of rational functions of Q(X 1,...,X n ) as input, decides whether they allow a rational potential function and, in case of affirmative answer, computes it as output. We introduce a mixed model of representation of polynomials to allow the application of integration techniques and show how to perform some basic operations with it. The algorithm is presented as a family of arithmetic networks of polynomial size and poly logarithmic depth in the degree of the occurring polynomials.
Partially supported by Research Project PB93-0472-C02-02
Partially supported by GDR de Calcul Formel Medicis (CNRS) France
EC Project ESPRIT BRA Contract 6846 PoSSo
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baur W., Strassen V.: The complexity of partial derivatives. Theoret. Comput. Sci. 22 (1982) 317–330.
Berkowitz S.J.: On computing the determinant in small parallel time using a small number of processors. Information Processing Letter 18 (1984) 147–150.
Borodin A., von zur Gathen J., Hopcroft J.: Fast parallel matrix and GCD computations. Information and Control 52 (1982) 241–256.
Bronstein M.: Formulas for series computations. Applied Algebra in Engineering, Communication and Computing, AAECC 2, Springer-Verlag (1992) 195–206.
Davenport J.H.: Intégration Formelle. IMAG Reserch Report No.375 (1983) 1–23.
Fitchas N., Giusti M. and Smietanski F.: Sur la complexité du théorème des zéros. Preprint Ecole Polytechnique Palaiseau (1992).
von zur Gathen J.: Parallel algorithms for algebraic problems. Proc. 13-th. Conf. MFCS, Springer LN Comput. Sci. 356 (1989) 269–300.
Heintz J.: On the computational complexity of polynomials and bilinear mappings. A survey. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 5th Intern. Conf. AAECC-5, Menorca 1987, L. Huguet and A. Poli, eds., Springer LN Comput. Sci. 356 (1989) 269–300.
Heintz J. and Schnorr C.P.: Testing polynomials which are easy to compute, in: 12-th Ann. ACM Symp. Theory of Computing (1980) 262–280.
Ibarra O.H. and Moran S.: Probabilistic algorithms for deciding equivalence of straight-line programs. J.ACM 30, 1 (1983) 217–228.
Kaltofen E.: Greatest common divisors of polynomials given by Straight-line Programs. J.ACM 35 No. 1 (1988) 234–264.
Lang S.: Algebra. Adisson-Wesley Publ. Comp., Reading, Massachusetts (1969).
Stoss H.J.: On the representation of rational functions of bounded complexity. Theoret. Comput. Sci. 64 (1989) 1–13.
Strassen V.: Berechnung und Programm I. Acta Inform.1 (1972) 320–334.
Strassen V.: Vermeidung von Divisionen. J. reine u. angew. Math. vol. 264 (1973) 182–202.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Matera, G. (1995). Integration of multivariate rational functions given by straight-line programs. In: Cohen, G., Giusti, M., Mora, T. (eds) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. AAECC 1995. Lecture Notes in Computer Science, vol 948. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60114-7_27
Download citation
DOI: https://doi.org/10.1007/3-540-60114-7_27
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60114-2
Online ISBN: 978-3-540-49440-9
eBook Packages: Springer Book Archive