ББК 22.14 + 22.19 Д13 УДК 512 + 519.9 Дэвенпорт Дж., Сирэ И., Турнье Э. Д13 Компьютерная алгебра: Пер. с франц. - М.: Мир, 1991. - 352 с., ил. ISBN 5-03-001658-9 Книга французских специалистов, охватывающая различные вопросы компьютерной алгебры: проблему представления дан- ных, полиномиальное упрощение, современные алгоритмы вычис- ления НОД полиномов и разложения полиномов на множители, формальное интегрирование, применение систем компьютерной алгебры. Первый автор знаком читателю по переводу его книги "Интегрирование алгебраических функций" (М.: Мир, 1985). Для математиков-прикладников, механиков, физиков, раз- работчиков и пользователей систем компьютерной алгебры. д 1602120000—278 ^д дд 041(01)—91 ББК 22.14 + 22.19 Редакция литературы по математическим наукам ISBN 5-03-001658-9 (русск.) ISBN 2-225-80990-9 (франц.) © Masson, Paris, 1986 © перевод на русский язык, Е.В.Панкратьев, 1991 ОТ РЕДАКТОРА ПЕРЕВОДА И ПЕРЕВОДЧИКА Монография Дж. Дэвенпорта, И. Сирэ и Э. Турнье вышла на французском языке в издательстве Masson в 1987 г. и сразу же привлекла внимание специалистов в области компьютерной алгебры и большой армии пользователей систем символьных вычислений. Фактически это - одна из первых монографий по компьютерной алгебре, хотя в журнальной литературе данная область представлена весьма основательно. В книге удачно сочетаются алгоритмические аспекты основных задач компью- терной алгебры и инструкции по использованию наиболее рас- пространенных систем символьных вычислений. Системы MACSYMA и REDUCE описаны достаточно подробно, чтобы начинающий пользователь мог составить представление о их возможностях и приобрел некоторые навыки работы с ними. Краткие сведения о других системах, прежде всего о системе SCRATCHPAD, дают представление о направлениях развития систем компьютерной алгебры и проблемах, связанных с их разработкой. Основные алгоритмы проанализированы достаточно глубоко, чтобы чита- тель мог освоиться с используемым математическим аппаратом. Формулировки новейших достижений и нерешенных проблем, при- веденные в книге, будут, по нашему мнению, стимулировать дальнейшие исследования. В 1988 г. вышел перевод данной книги на английский язык. Его выполнили один из авторов, Дж. Дэвенпорт, и А. Дэвенпорт. Основные отличия английского издания от фран- цузского заключаются в следующем: добавлено несколько при- мечаний в тексте и полностью переработано приложение "Опи- сание системы REDUCE" - это описание соответствует более поздней версии системы REDUCE-3.2. Все эти изменения учтены [Abbott et al. 1985] Abbott J.A., Bradford R.J. & Davenport J.H, A Remark on Factorisation. SIGSAM Bulletin 19 (1985), 2, pp. 31-33,37. [Abbott et al. 1987] Abbott J.A., Bradford R.J. & Davenport J.H, A Remark on Sparse Polynomial Multiplication. To appear. [Abdali et al. 1977] Abdali S.K., Caviness B.F. & Pridor A., Modular Polynomial Arithmetic in Partial Fraction Decomposition. -Proc. 1977 MACSYMA Users' Conference, NASA publication CP-2012, National Technical Informa- tion Service, Springfield, Virginia, pp. 253-261. [Aho et al., 1974] Aho A.V., Hopcroft J.E & Ullman J.D. The Design and Analysis of Computer Algorithms. Addison- Wesley, 1974. [Имеется перевод: Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгорит- мов, - М.: Мир, 1979.] [Alien et al. 1978] Alien J.R., The Anatomy of LISP. McGraw-Hill, New York, 1978. [Arnon 1985] Arnon D.S., On Mechanical Quantifier Elimina- tion for Elementary Algebra and Geometry: Solution of a Nontrivial Problem. Proc EUROCAL 85, Vol. 2 [Sprin- ger Lecture Notes in Computer Science Vol. 204, Sprin- ger-Verlag, 1985], pp. 270-271. [Arnon, Smith 1983] Arnon D.S. & Smith S.F., Towards Mecha- nical Solution of the Kahan Ellipse Problem I. Proc. EUROCAL 83 [Springer Lecture Notes in Computer Science 162, Springer-Verlag, Berlin, Heidelberg, New York, 1983], pp. 36-44. [Arnon et al. 1984a] Arnon D.S., Collins G.E. & McCallum 314 Литература S., Cylindrical Algebraic Decomposition I: The Basic Algorithm. SIAM J. Сотр. 13 (1984), pp. 865-877. [Arnon et al. 1984b] Arnon D.S., Collins G.E. & McCallum S., Cylindrical Algebraic Decomposition I: An Adjacen- cy Algorithm for the Plane. SIAM J. Сотр. 13 (1984), pp. 878-889. [Bareiss 1968] Bareiss E.H., Sylvester's Identity and Mul- tistep Integerpreserving Qaussian Elimination. Math. Сотр. 22 (1968), pp. 565-578. [Bateman, Danielopoulos 1981] Bateman S.O.,Jr., & Danielo- , poulos S.D., Computerised Analytic Solutions of Second Order Differential Equations. Computer J. 24 (1981), pp. 180-183. [Berlekamp 1967] Berlekamp E.R., Factoring Polynomials over Finite Fields. Bell System Tech. J. 46 (1967), pp. 1853-1859. [Borodin et al. 1985] Borodin A., Fagin R., Hopcroft J.E. & Tompa M., Decreasing the Nesting Depth of an Expres- sion Involving Square Roots. J. Symbolic Сотр. 1 (1985), pp. 169-188. [Brent 1970] Brent R.P., Algorithms for Matrix Multiplica- tion. Report CS 157, Computer Science Department, Stanford University, March 1970. (Результаты описаны в книге [Knuth 1981], с. 482.) [Brown 1969] Brown W.S., Rational Exponential Expressions and a Conjecture concerning я and e. Amer. Math. Monthly 76 (1969), pp. 28-34. [Brown 1971] Brown W.S., On Euclid's Algorithm and the Com- putation of Polynomial Greatest Common Divisors. J. ACM 18 (1971), pp. 478-504. [Buchberger 1970] Buchberger В., Ein algorithmisches Krite- rium fiir die Losbarkeit eines algebraischen Glei- chungssystems. Aequati.ones Mathematicae 4 (1970), pp. 374-383. [Buchberger 1976a] Buchberger В., Theoretical Basis for the Reduction of Polynomials to Canonical Forms. SIGSAM Bulletin 39 (Aug. 1976), pp. 19-29. Компьютерная алгебра 315 [Buchberger 1976b] Buchberger В., Some Properties of Grobner-Bases for Polynomial Ideals. SIGSAM Bulletin 40 (Nov. 1976), pp. 19-24. [Buchberger 1979] Buchberger В., A Criterion for Detecting Unnecessary Reductions in the Construction of Groebner Bases. Proceedings of the 1979 European Symposium on Symbolic and Algebraic Computation [Springer Lecture Notes in Computer Science 72, Springer-Verlag, Berlin, Heidelberg, New York, 1979], pp. 3-21, [Buchberger 1981] Buchberger В., H-Bases and Grobner-Bases for Polynomial Ideals. CAMP-Linz publication 81-2.0, University of Linz, Feb. 1981. [Buchberger 1983] Buchberger В., A Note on the Complexity of Computing Grobner-Bases. Proc. EUROCAL 83 [Springer Lecture Notes in Computer Science 162, Springer-Ver- lag, Berlin, Heidelberg, New York, 1979], pp. 137-145. [Buchberger 1985] Buchberger В., A Survey on the Method of Groebner bases for Solving Problems in Connection with Systems of Multivariate Polynomials. Proc. 2nd RIK.EN Symposium Symbolic & Algebraic Computation (ed. N. Inada & T. Soma), World Scientific Publ., 1985, pp. 69-83. [Buchberger et al. 1982] Buchberger В., Collins G.E. & Loos R. (editors). Symbolic & Algebraic Computation. Computing Supplementum 4, Springer-Verlag, Wien, New York, 1982. [Имеется перевод: Компьютерная алгебра. Символьные и алгебраические вычисления. - M.: Мир, 1986.] [Capelli 1901] Capelli A., Sulla riduttibilita della fun- zione x^-A in campo qualunque di rationalita. Math. Ann. 54 (1901), pp. 602-603. [Cauchy 1829] Cauchy A.-L, Exercises de Mathematiques Qua- trieme Annee. De Bure Freres, Paris, 1829. CEuvres, Ser. II. Vol. IX, Gauthier-Villars; Paris, 1891. [Char et al. 1985] Char B.W., Geddes K.O., Gonnet G.H., Watt S.M., Maple user's guide. Watcom Publications, Waterloo 1985. 316 Литература [Cherry 1983] Cherry G.W., Algorithms for Integrating Ele- mentary Functions in Terms of Logarithmic Integrals and Error Functions. Ph. D.Thesis, Univ. Delaware, August 1983. [Cherry 1985] Cherry G.W., Integration in Finite Terms with Special Functions: the Error Function. J. Symbolic Сотр. 1 (1985), pp. 283-302. [Cherry, Caviness 1984] Cherry G.W. & Caviness B.F., Integ-' ration in Finite Terms with Special Functions: A Prog- ress Report. Proc. EUROSAM 84 [Springer Lecture Notes in Computer Science 174, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1984], pp. 351-359. [Chou, Collins 1982] Chou T.-W. & Collins G.E., Algorithms for the solution systems of linear Diophantine equa- tions. SIAM J. Сотр. 11 (1982), pp. 687-708. [Collins 1971] Collins G.E., The Calculation of Multivari- ate Polynomial Resultants. J. ACM 18 (1971), pp. 515- 532. [Collins 1975] Collins G.E., Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposi- tion. Proc. 2nd GI Conf. Automata Theory and Formal Languages (Springer Lecture Notes in Computer Science 33), pp. 134-183. [Collins, Loos 1982] Collins G.E. & Loos R., Real Zeros of Polynomials. Symbolic & Algebraic Computation (Compu- ting Supplementum 4) (ed. B.Buchberger, G.E. Collins & R.Loos) Springer-Verlag, Wien, New York, 1982, pp. 83- 94. [Имеется перевод: Коллинз Дж., Лоос Р., Веществен- ные нули полиномов. - В кн.: Компьютерная алгебра. Символьные и алгебраические вычисления. - М.: Мир, 1986, с. 112-126.] [Coppersmith, Davenport 1985] Coppersmith D. & Davenport J.H., An Application of Factoring. J. Symbolic Сотр. 1 (1985), pp. 241-243 [Coppersmith, Winograd 1982] Coppersmith D. & Winograd S., On the Asymptotic Complexity of Matrix Multiplication. SIAM J. Сотр. 11 (1982), pp. 472-492. Компьютерная алгебра 317 [Coppersmith et al. 1986] Coppersmith D., Odiyzko A.M. & Schroeppel R., Discrete Logarithms in GF(p). Algorith- mica 1 (1986), pp. 1-15. [Coxeter 1961] Coxeter H.S.M., Introduction to Geometry. Wiley, New York, 1961. [Davenport 1981] Davenport J.H., On the Integration of Al- gebraic Functions. Springer Lecture Notes in Computer Science 102, Springer-Verlag, Berlin, Heidelberg, New York, 1981. [Имеется перевод: Дэвенпорт Дж. Интегриро- вание алгебраических функций. - М.: Мир, 1985.] [Davenport 1982] Davenport J.H., On the Parallel Risch Al- gorithm (I). Proc. EUROCAM'82 [Springer Lecture Notes in Computer Science 174, Springer-Verlag, Berlin, Hei- delberg, New York, 1982], pp. 144-157. [Davenport 1984a] Davenport J.H., Integration algorithmique des fonctions elementairement transcendantes sur une coubre algebrique. Annales de 1'Institut Fourier 34 (1984), pp. 271-276. [Davenport 1984b] Davenport J.H., y'+fy=g- Proc. EURO- SAM 84 [Springer Lecture Notes in Computer Science 174, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1984], pp. 341-350. [Davenport 1984с] Davenport J.H., Solutions of Inhomoge- neous Differential Equations, preprint, Journees educations differentielles dans le champ complexe, June 1984. To appear in the S1GSAM Bulletin. [Davenport 1985a] Davenport J.H., Closed. Form Solutions of Ordinary Differential Equations. Proc. 2nd RIKEN Sym- posium Symbolic & Algebraic Computation (ed. N. Inada & T. Soma), World Scientific Publ., 1985, pp. 183-195. [Davenport 1985b] Davenport J.H., Computer Algebra for Cy- lindrical Algebraic Decomposition. TRITA-NA-8511, NADA, KTH, Stockholm, Sept. 1985. [Davenport 1985с] Davenport J.H., On the Risch Differential Equation Problem. SIAM J. Сотр. 15 (1986), pp. 903-918. [Davenport 1986] Davenport J.H., On a "Piano Movers" Prob- lem. S1GSAM Bulletin 20 (1986), 1&2, pp. 15-17. 318 Литература [Davenport, Heintz 1987] Davenport J.H. & Heintz J., Real Quantifier Elimination is Doubly Exponential. To ap- pear in J. Symbolic Сотр. [Davenport, Padget 1987] Davenport J.H. & Padget J.A., On Number Bases for Symbolic Computation. To appear. [Davenport, Tournier 1983] Davenport J.H. & Tournier E., Definition syntaxique de RLISP. Rapport Interne, IMAG, 1983. [Delaunay 1960] Delaunay Ch., Theorie du mouvement de la lune. Extract from the Comptes Rendus de 1'Academie des Sciences, Vol LI. [Delia Dora, Tournier 1981] Delia Dora J. & Tournier E., Formal Solutions of Differential Equations in the Neighborhood of Singular Points (Regular and Irregu- lar). Proceedings of the 1981 ACM Symposium on Symbo- lic and Algebraic Calculation, ACM Inc., New York, 1981, pp. 25-29. [Delia Dora, Tournier 1984] Delia Dora J. & Tournier E., Homogeneous Linear Differential Equations (Frobenius- Boole Method). Proc. EUROSAM 84 [Springer Lecture No- tes in Computer Science 174, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1984], pp. 1-12. [Delia Dora, Tournier 1986] Delia Dora J. & Tournier E., - Solutions formelles asymptotiques d'equations recurrentes li- neaires: methode de Pincherle-Ramis. Research report, IMAG, Grenoble. [Delia Dora et al. 1982] Delia Dora J. Dicrescenzo С. & Tournier E., An Algorithm to Obtain Formal Solutions of a Linear Homogeneous Differential Equation at an Irregular Singular Point. Proc. EUROCAM 82 [Springer Lecture Notes in Computer Science 144, Springer- Verlag, Berlin, Heidelberg, New York, 1982], pp. 273- 280. [Delia Dora et al. 1985] Delia Dora J. Dicrescenzo С. & Duval D., About a new Method for Computing in Algebra- ic Number Fields. Proc. EUROCAL 85, Vol. 2 [Springer \ Lecture Notes in Computer Science 204, Springer- Компьютерная алгебра 319 Verlag, Berlin, Heidelberg, New York, Tokyo, 1985], pp. 289-290. [Dicrescenzo, Duval 1984] Dicrescenzo C. & Duval D., Compu- tations on Curves. Proc. EUROSAM 84 [Springer Lecture Notes in Computer Science 174, Springer-Verlag, Ber- lin, Heidelberg, New York, Tokyo, 1984], pp. 100-107. [Dicrescenzo, Duval 1985] Dicrescenzo C. & Duval D., Algeb- raic Computation on Algebraic Numbers. Computers and Computing (ed. P. Chenin, C. Dicrescenzo, F. Robbert), Masson and Wiley, 1985, pp. 54-61. [Duval 1987a] Duval D., An algorithmic proof of the resul- tant formula. To appear (also in [Duval 1987b]). [Duval 1987b] Duval D., Diverses questions relatives au Calcul Formel avec des nombers algebriques. These d'Etat, Universite I de Grenoble, April 1987. [Dubreuil 1963] Dubreuil P., Algebre. Gauthier-Villars, Paris, 1963. [Ehrhard 1986] Ehrhard Т., Personal communication, March 1986. [Fitch 1974] Fitch J.P., CAMAL Users' Manual. University of Cambridge Computer Laboratory, 1974. [Fitch 1985] Fitch J.P., Solving Algebraic Problems with REDUCE. J. Symbolic Сотр. 1 (1985), pp. 211-227. . [Gebauer, Kredel 1984] Gebauer P. & Kredel.H., Note on "So- lution of a General System of Equations". SIGSAM Bul- letin 18 (1984) 3, pp. 5-6. [Giusti 1984] Giusti M., Some Effectivity Problems in Poly- nomial Ideal Theory. Proc. EUROSAM 84 [Springer Lectu- re Notes in Computer Science 174, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1984], pp. 159- 171. [Gregory, Krishnamurthy 1984] Gregory R.T. & Krishnamurthy E.V., Methods and Applications of Error-free Computa- tion. Springer-Verlag, New York, 1984, pp. 159-171. [Имеется перевод: Грегори Р., Кришнамурти E. Безоши- бочные вычисления. Методы и приложения. - M.: Мир, 1988.] 320 Литература [Griesmer et al. 1975] Griesmer J.H., Jenks R.D. & Yun D.Y.Y., SCRATCHPAD User's Manual. IBM Research Publi- cation RA70, June 1975. [Hadamard 1893] Hadamard J., Resolution d'une Question Re- lative aux Determinants. Bull. des Sci. Math. (2) 17 (1893), pp. 240-246. CEuvres, CNRS, Paris, 1968, Vol.1, pp. 239-245. [Hearn 1987] Hearn A.Q, REDUCE-3 User's Manual, version 3.3, Rand Corporation Publication CP78 (7/78), 1987. [Heindel 1971] Heindel L.E., Integer Arithmetic Algorithm for Polynomial Real Zero Determination. J. ACM 18 (1971), pp. 535-548. [Hermite 1872] Hermite С., Sur 1'integration des fractions rationelles. Nouvelles Annales de Mathematiques, 2 Ser., 11 (1872), pp. 145-148. Ann. Scientifiques de 1'Ecole Normale Superieure, 2 Ser 1 (1872), pp. 215- 218. [Hilali 1982] Hilali A., .Contribution a 1'etude de points singuliers des systemes differentiels lineaires. These de trousieme cycle, IMAG, Grenoble, 1982. [Hilali 1983] Hilali A;, Characterization of a Linear Dif- ferential System with a Regular Singularity. Proc. EUROCAL 83 [Springer Lecture Notes in Computer Science 162, Springer-Verlag, Berlin, Heidelberg, New York, 1983], pp. 68-77. ' [Hilali 1987] Hilali A., Solutions formelles de systemes differentiels lineaires au voisinage de points singu- liers. These d'Etat, Universite I de Grenoble, June 1987. [Horowitz 1969] Horowitz E., Algorithm for Symbolic Integ- ration of Rational Functions. Ph. D. Thesis, Univ. of Wisconsin, November 1969. [Horowitz 1971] Horowitz E., Algorithms for Practical Frac- tion Decomposition and Rational Function Integration. Proc. Second Symposium on Symbolic and Algebraic Mani- pulation, ACM Inc., 1971, pp. 441-457. [Ince 1953] Ince F.L., Ordinary Differential Equations. Do- Компьютерная алгебра 321 ver Publications, 1953. [Имеется перевод более раннего издания: Айнс Э.Л., Обыкновенные дифференциальные •уравнения. - Харьков: ОНТИ, 1939.] [Jenks 1984] Jenks R.D., A Primer: 11 Keys to New SCRATCH- PAD. Proc. EUROSAM 84 [Springer Lecture Notes in Com- puter Science 174, Springer-Verlag, Berlin, Heidel- berg, New York, Tokyo, 1984], pp. 127-147. [Johnson 1974] Johnson S.C., Sparse Polynomial Arithmetic. Proc. EUROSAM 74 (SIGSAM Bulletin Vol. 8, No. 3, Aug. / 1974, pp. 63-71). [Kahrimanian 1953] Kahrimanian H.G., Analytic differentia- tion by a digital computer. M.A. Thesis, Temple U., Philadelphia, Pennsylvania, May 1953. [Kaltofen et al. 1981] Kaltofen E., Musser D.R.. & Saun- ders B.D., A Generalized Class .of Polynomials that are Hard to Factor.. Proceedings of the 1981 ACM Symposium on Symbolic and Algebraic Computation, ACM Inc., New York, 1981, pp. 188-194. [Kaltofen et al. 1983] Kaltofen E., Musser D.R. & Saun- ders B.D., A Generalized Class of Polynomials that are Hard to Factor. SIAM J. Сотр. 12 (1983), pp. 473-483. [Knuth 1969] Knuth D.E., The Art of Computer Programming, Vol II, Semi-numerical . Algorithms, Addison-Wesley, 1969. [Имеется перевод: Кнут Д. Искусство программиро- вания для ЭВМ. Т. 2. - М.: Мир, 1977.] [Knuth 1973] Knuth D.E., The Art of Computer Programming, Vol I, Fundamental Algorithms, 2nd Edn., Addison- Wesley, 1973. [Имеется перевод: Кнут Д. Искусство про- граммирования для ЭВМ. Т. 1. - М.: Мир, 1976.] [Knuth 1981] Knuth D.E., The Art of Computer Programming, Vol II, Semi-numerical Algorithms, 2nd Edn., Addison- Wesley, 1981. [Kovacic 1977] Kovacic J.J., An Algorithm for solving Se- cond Order Linear Homogeneous Differential Equations. Preprint, Brooklyn College, City University of New York. [Kovacic 1986] Kovacic J.J., An Algorithm for solving Se- cond Order Linear Homogeneous Differential Equations. 176—21 322 Литература J. Symbolic Сотр. 2 (1986), рр.3-43 [Krishnamurthy 1985] Krishnamurthy E.V., Error-free Polyno- mial Matrix Computations. Springer-Verlag, New-York, 1985. [Landau 1905] Landau E., Sur Quelques Theoremes de M. Pet- rovitch Relatifs aux Zeros des Fonctions Analytiques. Bull. Soc. Math. France 33 (1905), pp. 251- 261 [Lang 1965] Lang S., Algebra. Addison-Wesley, Reading, Mass., 1965. [Имеется перевод: Ленг С., Алгебра. - M.: Мир, 1968.] [Lauer 1982] Lauer M., Computing by Homomorphic Images. Symbolic & Algebraic Computation (Computing Supplemen- tum 4) (ed. B. Buchberger, G.E. Collins & R. Loos) Springer-Verlag, Wien, New York, 1982, pp. 139-168. [Имеется перевод: Лауэр M. Вычисления с помощью гомоморфных образов. - В кн.: Компьютерная алгебра. Символьные и алгебраические вычисления. - M.: Мир, 1986. с. 178-211.] [Lauer 1983] Lauer M., Generalized p-adic Constructions. SIAM J. Comp 12 (1983), pp. 395-410. [Lazard 1983] Lazard D., Grobner Bases, Gaussian Elimina- tion and Resolution of Systems of Algebraic Equation. Proc. EUROCAL 83 [Springer Lecture Notes in Computer Science 162, Springer-Verlag, Berlin, Heidelberg, New York, 1983], pp. 146-157. [Lazard 1987] Lazard D., Quantifier Elimination: Optimal Solution for 2 Classic Examples. To appear in J.Symbo- lic Comp. [Lenstra et al. 1982] Lenstra A.K., Lenstra H.W., Jr. & Lovasz L, Factoring Polynomials with Rational Coeffi- cients. Math. Ann. 261 (1982), pp. 515-534. [Lipson 1976] Lipson J.D., Newton's Method: a great Algeb- raic Algorithm. Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation, ACM Inc., New York, pp. 260-270. [Loos 1982] Loos R., Generalized Polynomial Remainder Se- quences. Symbolic & Algebraic Computation (Computing Компьютерная алгебра 323 Supplementum 4) (ed. В. Buchberger, G.E. Collins & R. Loos), Springer-Verlag, Wien, New York, 1982, pp. 115- 137. [Имеется перевод: Лоос Р. Обобщенные последова- тельности полиномиальных остатков. - В кн.: Компьютер- ная алгебра. Символьные и алгебраические вычисления. - M.: Мир, 1986, с. 151-171.] [McCallum 1985a] McCallum S., An Improved Projection Algo- rithm for Cylindrical Algebraic Decomposition. Compu- ter Science Tech. Report 548, Univ. Wisconsin at Madi- son, 1985. [McCallum 1985Ц McCallum S., An Improved Projection Algo- rithm for Cylindrical Algebraic Decomposition. Proc. EUROCAL 85, Vol. 2 [Springer Lecture Notes in Computer Science 204, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1985], pp. 277-278. [McCarthy et al. 1965] McCarthy J., Abrahams P.W., Ed- wards W., Hart T.P. & Levin M., The LISP 1.5 Program- mers Manual. M.I.T. Press, 1965. [Macmillan, Davenport 1984] Macmillan R.J., Davenport J.H., Factoring Medium-Sized Integers. Computer J. 27 (1984), pp. 83-84. [Marti et al. 1978] Marti J.B., Hearn A.C, Griss M.L. & Griss Q, The Standard LISP Report. Report UCP-60, University of Utah, Jan. 1978. SIGSAM Bulletin 14 (1980), 1, pp. 23-43. [Mauny 1985] Mauny J.B., These de troisieme cycle, Paris VII, Sept. 1985. [Mayr, Mayer 1982] Mayr E. & Mayer A., The Complexity of the Word Problem for Commutative Semi-groups and Poly- nomial Ideals. Adv. in Math. 46 (1982), pp. 305-329. [Mignotte 1974] Mignotte .M., An Inequality about Factors of Polynomials. Math. Comp. 28 (1974), pp. 1153-1157. [Mignotte 1981] Mignotte M., Some Inequalities About Univa- riate Polynomials. Proceeding of the 1981 ACM Sympo- sium on Symbolic and Algebraic Computation, ACM Inc., New York, 1981, pp. 195-199. [Mignotte 1982] Mignotte M., Some Useful Bounds. Symbolic & 324 Литература Algebraic Computation (Computing Supplementum 4) (ed. B. Buchberger, G.E. Collins & R. Loos), Springer- Verlag, Wien, New York, 1981, pp. 259-263. [Имеется перевод: Миньотт М. Некоторые полезные неравенства. - В кн.: Компьютерная алгебра. Символьные и алгебраичес- кие вычисления. - М.: Мир, 1986, с. 151-171.] [Mignotte 1986] Mignotte M., Computer versus Paper and Pen- cil. CALSYF 4, pp. 63-69. [Moses 1966] Moses J., Solution of a System of Polynomial Equations by Elimination. Comm. ACM 9 (1966), pp. 634- 637. [Moses 1967] Moses J., Symbolic Integration. Ph.D. Thesis & Project MAC TR-47, M.I.T.. 1967. [Moses 1971a] Moses J., Algebraic Simplification - A Guide for the Perplexed. Comm. ACM 14 (1971), pp. 527-537. [Moses 1971b] Moses J., Symbolic Integration, the stormy decade. Comm ACM 14 (1971), pp. 548-560. [Musser 1978] Musser D.R., On the Efficiency of a Polyno- mial Irreducibility Test. J. -ACM 25 (1978), pp. 271- 282. [Najid-ZejIi 1984] Najid-ZejIi H., Computation in Radical Extensions. Proc. EUROSAM 84 [Springer Lecture Notes in Computer Science 174, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1984], pp. 115-122. [Najid-ZejIi 1985] Najid-ZejIi H., Extensions algebriques: cas general et cas des radicaux. These de troisieme cycle, IMAG, Grenoble, 25.6.85. [Nolan 1953] Nolan J., Analytic differentiation on a digi- tal computer. M.A.Thesis, Math. Dept, M.I.T., Cam- bridge, Massachusetts, May 1953. [Norman 1975] Norman A.C., Computing with Formal Power Se- ries. ACM Transactions on Mathematical Software 1 (1975), pp. 346-356. [Norman 1982] Norman A.C, The Development of a Vector- based Algebra System. Proc. EUROCAM 82 [Springer Lec- ture Notes in Computer Science 144, Springer-Verlag, Berlin, Heidelberg, New York, 1982], pp. 237-248. Компьютерная алгебра 325 [Norman, Davenport 1979] Norman A.C. & Davenport J.H., Sym- bolic Integration - the Dust Settles? Proceedings of the 1979 European Symposium on Symbolic and Algebraic Computation [Springer Lecture Notes in Computer Science 72, Springer-Verlag, Berlin, Heidelberg, New York, 1979], pp. 398-407. [Norman, Moore 1977] Norman A.C. & Moore P.M. A., Implemen- ting the new Risch Integration Algorithm. Proc, Symp. advanced computing methods in theoretical physics, Marseilles, 1977, pp. 99-110. [Ostrowski 1946] Ostrowski A.M., Sur 1'integrabilite 616- mentaire de quelques classes d'expressions. Comm. Math. Helvet. 18 (1946), pp. 283-308. [Pearce, Hicks 1981] Pearce P.D., & Hicks R.J., The Optimi- zation of User Programs for an Algebraic Manipulation System. Proceedings of the 1981 ACM Symposium on Sym- bolic and Algebraic Computation, ACM Inc., New York, 1981, pp. 131-136. [Pearce, Hicks 1982] Pearce P.D., & Hicks R.J., The Appli- cation of Algebraic Optimisation Techniques to Algeb- raic Mode Programs for REDUCE. SIGSAM Bulletin 15 (1981/2), 4, pp. 15-22. [Pearce, Hicks 1983] Pearce P.D., & Hicks R.J., Data Structures and Execution Times of Algebraic Mode Programs for REDUCE. SIGSAM Bulletin 17 (1983), 1, pp. 31-37. [Probst, Alagar 1982] Probst D. & Alagar V.S., An Adaptive Hybrid Algorithm for Multiplying Dense Polynomials. Proc. EUROCAM [Springer Lecture Notes in Computer Science 144, Springer-Verlag, Berlin, Heidelberg, New York, 1982], pp. 16-23. [Puiseux 1850] Puiseux M.V., Recherches sur les fonctions algebriques. J. Math. Pures et Appliquees 15 (1850), pp. 365-480. [Ramanujan 1927] . Ramanujan S., Problems and Solutions. In Collected Works (ed. G.H. Hardy, P.V. Secha Ayar & B.M. Wilson), C.U.P., 1927 326 Литература [Ramis, Thomann 1980] Ramis J.P. & Thomann J., Remarques sur 1'utilisation numerique des series de factoriel- les. Seminaire d'analyse numerique, Strasbourg No. 364, 1980. [Ramis, Thomann 1981] Ramis J.P. & Thomann J., Some Comments about the Numerical Utilization of Factorial Series Methods in the Study of Critical Phenomena. Springer-Verlag, Berlin, Heidelberg, New York, 1981. [Richard 1986] Richard F., Representation graphiques de solution d'equations differentielles dans le champ complexe. Rapport de recherche, IRMA, Strasbourg. [Richards, Whitby-Strevens 1979] Richards M. & Whitby- Strevens Q, BCPL, The Language and its Compiler. C.U.P., 1979. [Richardson 1968] Richardson D., Some Unsolvable Problems Involving Elementary Functions of a Real Variable. J. Symbolic Logic 33 (1968), pp. 511-520. [Risch 1969] Risch R.H., The Problem of Integration in Fi- nite Terms. Trans. A.M.S. 139 (1969), pp. 167-189. [Risch 1979] Risch R.H., Algebraic Properties of the Ele- mentary Functions of Analysis. Amer. J. Math. 101 (1979), pp. 743-759. [Rosenlicht 1976] Rosenlicht M., On Liouville's Theory of Elementary Functions. Pacific J. Math 65 (1976), pp. 485-492. [Rothstein 1976] Rothstein M., Aspects of Symbolic Integration and Simplification of Exponential and Primitive Functions. Ph. D. Thesis, Univ. of Wisconsin, Madison, 1976 (Xerox University Microfilms 77-8809.) [Sasaki, Murao 1981] Sasaki T. & Murao H., Efficient Gaus- sian Elimination Methods for Symbolic Determinants and Linear Systems. Proceedings of the 1981 ACM Symposium on Symbolic and Algebraic Computation, ACM Inc., New York, 1981, pp. 155-159. [Sasaki, Murao 1982] Sasaki T. & Murao H., Efficient Gaus- sian Elimination Method for Symbolic Determinants and Компьютерная алгебра 327 Linear Systems. ACM Transactions on Mathematical Soft- ware 8 (1982), pp. 277-289. [Saunders 1981] Saunders B.D., An Implementation of Kovacic's Algorithm for Solving Second Order Linear Homogeneous Differential Equations. Proceedings of the 1981 ACM Symposium on Symbolic and Algebraic Computation, ACM Inc., New York, 1981, pp. 105-108. [Schwarts, Sharir 1983a] Schwarts J.T. & Sharir M., On the "Piano Movers" Problem II. General Techniques for Com- puting Topological Properties of Real Algebraic Mani- folds. Advances Appl. Math. 4 (1983), pp. 298-351. [Schwarts, Sharir 1983b] Schwarts J.T. & Sharir M., On the "Piano Movers" Problem II. Coordinating the Motion of Several Independent Bodies: The Special Case of Circu- lar Bodies Moving Amidst Polygonal Barriers. Int. J. Robot. Res. 2 (1983), pp. 46-75. [Singer 1981] Singer M.F., Liovillian Solution of n-th Or- der Homogeneous Linear Differential Equations. Amer. J. Math. 103 (1981), pp. 661-682. [Singer 1985] Singer M.F., Solving Homogeneous Linear Dif- ferential Equations in Terms of Second Order Linear Differential Equations. Amer. J. Math. 107 (1985), pp. 663-696. [Singer, Davenport 1985] Singer M.F. & Davenport J.H., Ele- mentary and Liovillian Solution of Linear Differential Equations. Proc. EUROCAL 85 [Springer Lecture Notes in Computer Science 204, Springer-Verlag, Berlin, Heidel- berg, New York, Tokyo, 1985], pp. 595-596. [Singer, Davenport 1986] Singer M.F. & Davenport J.H., Ele- mentary and Liovillian Solution of Linear Differential Equations. J. Symbolic Сотр. 2 (1986), рр.237-260. [Singer et al. 1981] Singer M.F., Saunders B.D. & Caviness B.F., An Extension of Liouville's Theorem on Integra- tion in Finite Terms. Proceedings of the 1981 ACM Sym- posium on Symbolic and Algebraic Computation, ACM Inc., New York, 1981, pp. 23-24. [Singer et al. 1985] Singer M.F., Saunders B.D. & Caviness 328 Литература B.F., An Extension of Liouville's Theorem on Integra- tion in Finite Terms. SIAM J. Сотр. 14 (1985) pp. 966- 990. [Slagle 1961] Slagle J., A Heuristic Program that Solves Symbolic Integration Problems in Freshman Calculus. Ph. D. Dissertation, Harvard U., Cambridge, Mass. May 1961. [Smit 1981] Smit J., A Cancellation Free Algorithm, with Factoring Capabilities, for the Efficient Solution of Large Sparse Sets of Equations. Proceedings of the 1981 ACM Symposium on Symbolic and Algebraic Computa- tion, ACM Inc., New York, 1981, pp. 146-154. [Strassen 1969] Strassen V., Gaussian Elimination is not Optimal. Numer. Math. 13 (1969), pp. 354-356. [Tarski 1951] Tarski A., A Decision Method for Elementary Algebra and Geometry. 2nd ed., Univ. California Press, Berkeley, 1951. [Tournier 1987] Tournier E., Solutions formelles d'equa- tions differentielles: Le logiciel de calcul formel DESIR. These d'Etat, Universite I de Grenoble, April 1987. [Trager 1976] Trager B.M., Algebraic Factoring and Rational Function Integration. Proceedings of the 1976 ACM Sym- posium on Symbolic and Algebraic Computation, ACM Inc., New York, 1976, pp. 219-226. [Trager 1985] Trager B.M., On the Integration of Algebraic Functions. Ph.D. Thesis, Dept. of Electrical Enginee- ring & Computer Science, M.I.Т., August 1985. [Viry 1982] Viry G., Factorisation des polyn6mes a plu- sieurs variables. RAIRO Inform. Theor. 12 (1979), pp. 209-223. [van der Waerden 1949] van der Waerden, B. L., Modern Algeb- ra. Frederick Ungar, New York, 1949. [Имеются перево- ды: ван дер Варден Б.Л. Современная алгебра, т. 1,2 (пер. 2-го изд. 1937, 1940 гг.). - М.: ГОНТИ, 1947; Б.Л. ван дер Варден Б.Л. Алгебра. - М.: Наука, 1976 (пер. изд. 1971 г.).] ' Компьютерная алгебра 329 [Wang 1978] Wang P.S., An Improved Multivariable Polynomial Factorising Algorithm. Math. Сотр. 32 (1978), pp. 1215-1231. [Wang 1980] Wang P.S., The EEZ-GCD Algorithm. SIGSAM Bulle- tin 14 (1980), 2, pp. 50-60. [Wang 1981] Wang P.S., A p-adic Algorithm for Univariate Partial Fractions. Proceedings of the 1981 ACM Sympo- sium on Symbolic and Algebraic Computation, ACM Inc., New York, 1981, pp. 212-217. [Wang 1983] Wang P.S., Early Detection of True Factors in Univariate Polynomial Factorisation. Proc. EUROCAL 83 [Springer Lecture Notes in Computer Science 162, Springer-Verlag, Berlin, Heidelberg, New York, 1983], pp. 225-235. [Wang et al. 1982] Wang P.S., Guy M.J.T. & Davenport, J.H., p-adic Reconstruction -of Rational Numbers. SIGSAM Bul- letin 16 (1982), pp. 2-3. [Wasow 1965] Wasow W., Asymptotic Methods for Ordinary Dif- ferential Equations. Kreiger Publ. ~ Co., New York, 1965. [Watanabe 1976] Watanabe S., Formula Manipulation Solving Linear ODEs II. Publ. RIMS Kyoto Univ. 11 (1976), pp. 297-337. [Watanabe 1981] Watanabe S., A Technique for Solving Ordi- nary Differential Equations Using Riemann's p-functions. Proceedings of the 1981 ACM Symposium on Symbolic and Algebraic Computation, ACM Inc., New York, 1981, pp. 36-43. [Wilkinson 1959] Wilkinson J.H.. The Evaluation of the Ze- ros of lllconditioned Polynomials. Num. Math. 1 (1959), pp. 150-166, 167-180. [Winograd 1968] Winograd S., A New Algorithm for Inner Pro- duct. IEEE Trans. Computers C-17 (1968), pp. 693-694. [Winston, Horn 1981] Winston P.H. & Horn B.K.P., LISP. Ad- dison-Wesley, 1981. (The 2nd ed., 1984 is written for Common LISP.) [Wunderlicht 1979] Wunderlicht M.C,, A Running-Time Analy- 330 Литература sis of Brillhart's Continued Fraction Factoring Algo- rithm. In: Number Theory Carbondale 1979 (ed. M.B. Nathanson) [Springer Lecture Notes in Mathematics 751, Springer-Verlag, BerHn, Heidelberg, New York, 1979], pp. 328-342. [Yun 1974] Yun D.Y.Y, The Hensel Lemma in Algebraic Manipu- lation. Ph. D. Thesis & Project MAC TR-138, M.I.T., 1974 [reprinted Garland Publishing Co., New York, 1980]. [Yun 1976] Yun D.Y.Y, On Square-free Decomposition Algo- rithms. Proceedings of the 1976 ACM Symposium on Sym- bolic and Algebraic Computation, ACM Inc., New York, 1976, pp. 26-35. [Yun 1977] Yun D.Y.Y, On the Equivalence of Polynomial Gcd and Squarefree Factorisation Algorithms. Proc. 1977 MACSYMA User's Conference NASA publication CP-2012, National Technical Information Service, Springfield, Virginia, pp. 65-70. [Zassenhaus 1969] Zassenhaus H., On Hensel Factorisation. J. Number Theory 1 (1969). pp. 291-311. [Zippel 1979] Zippel R.E., Probabilistic Algorithm for Sparse Polynomials. Proceedings of the 1979 European Symposium on Symbolic and Algebraic Computation [Springer Lecture Notes in Computer Science 72, Sprin- ger-Verlag, Berlin, Heidelberg, New York, 1979], pp. 216-226. [Zippel 1985] Zippel R.E., Simplification of Expressions Involving Radicals. J. Symbolic Сотр. 1 (1985), pp. 189-210. Дополнительная литература1 1. Абрамов С. А. Задачи компьютерной алгебры, связанные с поиском полиномиальных решений линейных дифференциаль- ных и разностных уравнений. - Вестн. МГУ, сер. 15, 1989, № 3, с. 56-60. Добавлена переводчиком. Компьютерная алгебра 331 2. Абрамов С. А. Рациональные решения линейных дифференци- альных и разностных уравнений с полиномиальными коэф- фициентами. - Журн. выч. мат. и мат. физ., 1989, т. 29, № 11, с. 1611-1620 3. Аналитические вычисления на ЭВМ и их применение в теоре- тической физике. - ОИЯИ, Д11-80-13, Дубна, 1980. 4. Аналитические вычисления на ЭВМ и их применение в теоре- тической физике. - ОИЯИ, Д11-83-511, Дубна, 1983. 5. Аналитические вычисления на ЭВМ и их применение в теоре- тической физике. - ОИЯИ, Д11-85-791, Дубна, 1985. 6. IV Международное совещание по аналитическим вычислениям на ЭВМ в физических исследованиях (сборник аннотаций). - ОИЯИ, Е11-90-204, Дубна, 1990. 7. Арайс Е.А., Яковлев Н.Е. Автоматизация аналитических вычислений в научных исследованиях. - Новосибирск: Наука, 1985. 8. Бухбергер Б. Базисы Гребнера. Алгоритмический метод в теории полиномиальных идеалов. - В кн.: Компьютерная алгебра. Символьные и алгебраические вычисления. - М.: Мир, 1986, с. 331-372. 9. Вычислительная математика и вычислительная техника, вып.З. - Харьков: ФТИНТ АН УССР, 1972. 10. Гельфонд А. О. Трансцендентные и алгебраические числа. - М.: Гостехиздат, 1952. 11. Гердт В.П, Григорьев Д.Ю. Обзор: Алгоритмы, системы и применения компьютерной алгебры. - В кн.: Компьютерная алгебра. Символьные и алгебраические вычисления. - М.: Мир, 1986, с. 373-383. 12. Гердт В.П., Тарасов О. В., Шйрков Д. В. Аналитические вычисления на ЭВМ в приложении к физике и математике. - УФН, 1980, т. 130, вып. 1, с. 113-147. 13. Глушков В.М., Бондарчук В. Г., Гринченко Т. А. Аналитик - алгоритмический язык для описания процессов с исполь- зованием аналитических преобразований. - Кибернетика, 1971, № 3, с. 102-134. 14. Григорьев Д.Ю. Разложение многочленов над конечным по- лем и решение систем алгебраических уравнений. - Зап. 332 Литература науч. семинаров. Ленингр. отд-ние Мат. ин-т АН СССР, 1984, т. 137, 20-79. 15. Григорьев Д.Ю. Эффективные алгоритмы для символьного решения систем полиномиальных уравнений и неравенств. - В [5] с. 202-207. 16. Григорьев Д.Ю. Сложность разрешения теории первого по- рядка алгебраически замкнутых полей. - Изв. АН СССР, Сер. мат., 1986, т. 50, № 5, с. 1106-1120. 17. Григорьев Д.Ю., Чистов А.Л. Быстрое разложение много- членов на неприводимые и решение систем алгебраических уравнений. - Докл. АН СССР, 1984, т. 275, № 6, с. 1302-1306. 18. Грошева М.В., Ефимов Г. Б. О системах аналитических вычислений на ЭВМ. - В [30] с. 5-29. 19. Грошева М.В. Прикладные и эксплуатационные возможности систем аналитических вычислений. - В [30] с. 30-37. 20. Гурин Н.И., Скоморохов А. Г. Аналитические вычисления в системе REDUCE. Справ, пособие. - Минск: Наука и тех- ника, 1989. 21. Еднерал В.Ф., Крюков А. П., Родионов А. Я. Язык аналити- ческих вычислении REDUCE. - М.: Изд-во МГУ, 1988. 22. Закс М.Б. Аналитические преобразования на ЕС ЭВМ. - Саратов: Изд-во Саратов, ун-та, 1981. 23. Климов Д.М., Руденко В.М. Методы компьютерной алгебры в задачах механики. - М.: Наука, 1989. 24. Кондратьева М.В., Панкратьев Е.В., Серов Р.Е. Вычисле- ния в дифференциальных и разностных модулях. - В [5] с. 208-213. 25. Кондратьева М.В., Панкратьев Е.В. Алгоритмы вычисления характеристических многочленов Гильберта.. - В [30] с. 129-146. 26. Латышев В.Н. Конструктивная теория колец. Стандартные базисы. - М.: Изд-во МГУ,- 1988. 27. Люстерник Л. А. Абрамов А. А, Шестаков В. И., Шура-Бура М.Р. Решение математических задач на автоматических цифровых машинах. - М.: Изд-во АН СССР, 1952. 28. Малашонок Г. И. Система линейных уравнений над коммута- Компьютерная алгебра 333 тивным кольцом. - Львов: ФМИ АН УССР, 1986 (препринт №114). 29. Михалев А. В., Панкратьев Е.В. Компьютерная алгебра. Вычисления в дифференциальной и разностной алгебре. - М.: Изд-во МГУ, 1989. 30. Пакеты прикладных программ. Аналитические преобразова- ния. - М.: Наука, 1988. 31. i Панкратьев Е.В. Компьютерная алгебра. Факторизация мно- гочленов. - М.: Изд-во МГУ, 1988. 32. Системы для аналитических преобразований в механике. Тезисы докладов Всесоюзной конференции. - Горький: ГГУ, 1984. 33. Теория и практика автоматизированных систем аналитичес- ких преобразований. Тезисы докладо.в республиканской научной конференции. - Вильнюс: Лит. НИИНТИ, 1984. 34. Чистов А. Л. Алгоритм полиномиальной сложности для раз- ложения многочленов и нахождения компонент многообра- зия в субэкспоненциальное время. - Зап. науч. семина- ров. Ленингр. отд-ние Мат. ин-т АН СССР, 1984, т. 137, с. 124-188. 35. Akritas A.G. Elements of computer algebra with applica- tions. New York: Wiley, 1989. 36. Boyle A. Caviness B.F. (eds) Future directions for re- search in symbolic computation. Report of a workshop on symbolic and algebraic computation. April 29-30 1988 Washington, DC. Published by the Society for in- dustrial and applied mathematics Philadelphia, 1989. 37. Bronstein M., Davenport J.H., Trager B.M. Symbolic in- tegration is algorithmic! Препринт доклада на конфе- ренции Computers and Mathematics, Portland, 15 June 1989. 38. Carra' Ferro G. Some properties of the lattice points and their application to differential algebra. Commu- nication in Algebra. 15 (1987), pp. 2625-2632. 39. Carra' Ferro Q. Grobner Bases- and Differential Algebra, Led. Notes Comput. Sci. 356, Springer-Verlag, 1989, pp. 129-140 334 Литература 40. Chou Shang-Ching Mechanical geometry theorem proving. Dordrecht: D.Reidel Publishing Company, 1987. 41. Chudnovsky D.V., Jenks R.D. (eds) Computer algebra. Lect. Notes in Pure and Applied Math. 113, New York: Dekker, 1989. 42. Davenport J.H. (ed.) EUROCAL'87 European Conference on Computer Algebra. Leipzig, GDR, June 2-5, 1987. Pro- ceedings, Lect. Notes Comput. Sci. 378, Springer- Verlag, 1989. 43. Davenport J.H., Trager B. Scratchpad's Theory of Algeb- ra. I: Basic Commutative Algebra. To appear in Proc. DISCO-90 (Springer LNCS). 44. Galigo A., Traverso C. Practical determination of the dimension of an algebraic variety. In [47] pp. 46-52. 45. Carding L, Tambour T. Algebra for computer science. New York: Springer-Verlag, 1988. 46. Gianni (ed.) Symbolic and Algebraic Computation. Inter- national Symposium ISSAC'88, Rome, Italy, July 1988, Proceedings, Lect. Notes Comput. Sci. 358, Springer- Verlag 1989. 47. Kaltofen E., Watt S.M. (eds) Computers and Mathematics, New York: Springer, 1989. 48. Kondrat'eva M.V., Pankrat'ev E.V. A recursive algorithm for computation of the Hilbert polynomial. In [42] pp. 365-375. 49. Mignotte M. Mathematiques pour le calcul formel, Paris: Presses Univ. Fr., 1989. 50. Moller H.M., Mora F. New constructive methods in clas- sical ideal theory, J. Algebra. 100 (1986),№ 1, pp. 138-178. 51. Mora F., Moller H.M. The computation of the Hilbert function. Lect. Notes Comput. Sci. 162, Springer- Verlag, 1983, pp. 157-167.' 52. Pankrat'ev E.V. Computations in differential and diffe- rence modules. Acta Applicandae Mathematicae 16 (1989), pp. 167-189. 53. Pohst M. (ed.) Algorithmic methods in algebra and num- Компьютерная алгебра 335 ber theory. London: Academic Press, 1987. 54. Pohst M., Zassenhaus H. Algorithmic algebraic number theory. Cambridge: Cambridge University Press, 1989. 55. Rand R.H., Armbruster D. Perturbation methods, bifurca- tion theory and computer algebra. Appl. Math. Sci. 65, New York: Springer, 1988. 56. Rayna G. REDUCE. Software for Algebraic Computation. New York: Springer, 1989. 57. Sharpe D. Rings and factorization. Cambridge: Cambridge University Press, 1987. 58. Proceedings of the ACM-SIGSAM 1989 International Sympo- sium on Symbolic and Algebraic Computation ISSAC'89 July 17-19, 1989 Portland, Oregon. New York: ACM Press, 1989. 59. Tangora (ed) Computer in algebra. Lect. Notes in Pure and Appl. Math. Ill, 1988. 60. Tournier E. (ed.) Computer Algebra and Differential Equations. Academic Press, 1989. ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Адамара граница (borne de Hadamard) 184 алгебраическая функция (fonction algebrique) 101, 104 алгебраическое выражение (expression algebnque) 101 — расширение (extension algebrique) 77 — число (nombre algebrique) 101 алгоритм Барейса (methodes de Bareiss) 83, 100, 115 — Берлекэмпа (algorithme de Berlekamp) 188 — Бухбергера (~ ~ Buchberger) 133 — Гензеля, квадратичный вариант (~ quadratique de Hensel) 198, 201 — — линейный вариант (~ lineaire de ~) 197 — Евклида (~ d'Euclide) 94 — — расширенный (~ ~ etendu) 271, 273 — изоляции вещественных корней полинома (~ d'isolement des racines reelles) 146 — модулярного НОД (~ de p.g.c.d. modulaire) 180 — Ньютона (~ ~ Newton) 199 — разложения полиномов на множители (~ ~ factorisation) 202, 203 — Фробениуса (~ ~ Frobenius) 256 — Цассенхауза (~ ~ Zassenhaus) 193 базис редуцированный (base reduite) 130 — стандартный (Грёбнера) (~ standard (de Grobner)) 129 Барейса алгоритм (methodes de Bareiss) 83, 100, 115 Безу тождество (identite de Bezout) 272 Бесселя уравнение (equation de Bessel) 261 Берлекэмпа алгоритм (algorithme de Berlekamp) 188 — теорема (theoreme ne Berlekamp) 190 Брауна метод (methode de Brown) 86 Бухбергера алгоритм (algorithme de Buchberger) 133 — критерий (critere de Buchberger) 136 Вамга метод (methode de Wang) 211 вариация (variation) 143 взрыв комбинаторный (explosion combinatoire) 194, 210 вложенный радикал (radical imbrique) 101, 103 внутреннее представление (representation interne) 97 вполне редуцированный полином (polynome completement reduit) .129 Компьютерная алеейра 337 выражение алгебраическое (expression algcbriquc) 101 вычисления ленивые (evalution paresseuse) 124 — матричные (calcul matriciel) 38 — неявные (~ implicite) 112 — явные (~ explicite) 112 Гаусса исключение (elimination de Gauss) 100, 118 — лемма (lemme de Gauss) 188 Гензеля алгоритм, квадратичный вариант (algorithme quadra- tique de Hensel) 198, 201 — — линейный вариант (~ lineaire de ~) 197 — лемма (lemme de ~) 195, 198 Гильберта матрица (matrice de Hilbert) 39 — теорема неприводимости (theoreme d'irreductibilite de ~' 207 главная переменная (indeterminee principale) 95 Горовица метод (methode de Horowitz) 221 гоаница Адамара (borne de Hadamardi 184 Грёбнера базис (base dc Grobner) 12& Дискриминант (discriminants) 155, 277 дифференцирование (derivation) 47 — формальное (derivation formelle) 215 дроби простейшие (elements simples) 273 дробь правильная (fraction propre) 274 Дэвенпорта теорема (theoreme de Davenport) 240, 245 Евклида алгоритм (algorithme d'Euclide) 94 — — расширенный (~ ~ etendu) 271, 273 — последовательность (suite ~) 93 естественное представление (representation naturelle) 86 задача интегрирования (probleme d'integration) 217 — планирования движения (de planification au mouvement) 159 идеал (ideal) 126 — нульмерный (~ de dimension zero) 130 изолированный корень (racine isolee) 140 изолирующий интервал (intervalle d'isolement) 140 инвариантное разбиение (decomposition invariante) 149 интегрирование (integration) 61 — алгебраических функций (~ de fonctions algebriques) 239 — логарифмических функций (~ ~ ~ logarithmiques) 226 — неэлементарных функций (~ ~ ~ поп elementaires) 240 — рациональных функций (~ ~ ~ rationelles) 217 — смешанных функций (~ ~ ~ mixtes) 236 — формальное (~ formelle) 215 — экспоненциальных функций (~ de fonctions exponentielles) &о 1 интервал изолирующий (intervalle d'isolement) 140 338 Предметный у ии загс. иррегулярная особенность (singularitc irregulicre) 258 исключение Гаусса (elimiiiat ion (!e Guuss) 100, 118 каноническое представление, (representation canonique) 85 китайская теорема об остатках (theoreme cuinois des restes) 278, 280 — — — — обобщенная (~ ~ ~ ~ generalise) 279, 281 класс эффективный (class effect if) 217 Кнута метод (methode de Knuth) 190 —'неравенство (inegalite de Knuth) 144 Ковачича теорема (Theoreme dc Kovacic) 247 комбинаторный взрыв (explosion combinatoire) 194, 210 компактное представление (representation compacte) 86 композиция (composition) 52 компонента полуалгебраичсская (composante semi-algcbrique) 148 корень изолированный (racine isolec) 140 Коши неравенство (inegalite de Cauchy) 144 коэффициент старший (coefficient principal) 205, 209, 210 Крамера правило (methode de Cramer) 114, 118 критерий Ьухбергсра (critere de Buchberger) 136 — Мюссе (~ - Musser) 204 Ландау - Миньотта неравенство (inegalite de' Landau - Mip- nofte) 164 ° Ланцоша метод (methode dc Lanczos) 118 Лапласа преобразование (transformation de Laplace) 64 лексикографический порядок (ordre lexicographique) 95, 127 лемма Гаусса (lemme de Gauss) 188 — Гензеля (~ ~ Hensci) 195, 198 — о разложении (~ ~ Decomposition) 227, 232 — Риша (~ ~ Risch) 244, 245 ленивые вычисления (evalution paresscuse) 124 линейное рекуррентное уравнение (equation recurrcntc lineaire) 257 линейные уравнения (equations lineaires) 187 Лисп (LISP) 20 лиувиллева образующая (generateur liouvillien) 246 — функция (fonction liouvillienne) 247 Лиувилля принцип (principe de Liouville) 226 логарифм (logarithme) 111 Лорана ряды (series de Laurent) 124 малая теорема Ферма (petit theoreme de Fermat) 189 матрица Гильберта (matrice de Hilbert) 39 — обратная (~ inverse) 184 — плотная (~ dense) 113 — разреженная (~ creuse) 117 — Сильвестра (~ de Sylvester) 17.1, 275 матричные вычисления (calcul matriciel) 38 метод Брауна (methode de Brown) 86 — Ванга "(~ ~ Wang) 211 — Горовица (~ ~ Horowitz) 221 — Кнута (~ ~ Knuth) 190 — Ланцоша (~ ~ Lanczos) 118 Компьютерна.ч члгсора 33 У метод наивный (methode naive) 218 — Нормана (~ de Nonnan) 122 — одношаговый (~ "d'un pas") ll6 — Островского (~ d'Ostrowski) — повторного исключения (~ de 1'elimination repetee) 138 — последовательных приближений (~ d'approximation repetee) 119 — сопряженных градиентов (~ des gradients conjugues) 118 — Эрмита (~ de Hermite) 220 Мечина формула (formule de Mechain) 28 многогранник 'Ньютона (polygone de Newton) 254 многообразие полуалгебраическое (variete serni-algebrique) 148 множители паразитические (facteurs parasites) 209 модулярный НОД (p.g.c.d. modulaire) 168 моном (топоте) 95 — старший (~ principal) 128 Мора пример (example de Mora) 137 Морли теорема (theoreme de Morley) 56 Мюссе критерий (critere de Musser) 204 наивный метод (methode na'i've) 218 некоммутативное умножение (multiplication non commutative) 52 некоммутирующие переменные (indeterminees non-commutatives) 112 неравенство Кнута, (inegalite de Knuth) 144 — Коши (-~ ~ Cauchy) 144 — Ландау - Миньотта (~ ~ Landau - Mignotte) 164 неявные вычисления (calcul implicite) 112 НОД модулярный (p.g.c.d. modulaire) 168 — полиномов (~ des polynomes) 92 норма полинома (norme du polynome) 106 нормальное представление (representation normale) 85 Нормана метод (methode de Norman) 122 нули плохие (zeros mauvais) 209 нульмерный идеал (ideal de dimension zero) 130 Ньютона алгоритм (algorithme de Newton) 199 — многогранник (polygone de ~) 254 обобщенный полином (polynome generalise) 232 образующая идеала (generateur d un ideal) 127 — лиувиллева (~ liouviliien) 246 — элементарная (~ elementaire) 225 обратная матрица (matrice inverse) 184 одношаговый метод (methode "d'un pas") 116 определитель (determinant) 41 особенность иррегулярная (singularite irreguliere) 258 — регулярная (~ reguliere) 258 Островского метод (methode d'Ostrowski) отмеченное разбиение (decomposition marquee) 149 паразитические множители (facteurs parasites) 209 — решения (solutions ~) 138 340 Предметный указатель переменная главная (indeterminee principale) 95 переменные некоммутирующие (indeterminees non-commutatives) 112 плотная матрица (matrice dense) 113 плотное представление (representation dense) 87 плохая редукция (mauvaise reduction) 178 плохие нули (zeros mauvais) 209 подстановка (substitution) 48, 54, 91 поле лиувиллевых функций (corps de fonctions liouvillien- nes) 247 — элементарных функций (~ ~ ~ elementaires) 225 полином обобщенный (polynome generalise) 232 — вполне редуцированный (~ cornpletement reduit) 129 — примитивный (~ primitif) 174 — редуцированный (~ reduit) 128 — Уилкинсона (~ de Wilkinson) 146 — характеристический (~ caracteristique) 41 полиномы эквивалентные (polynomes equivalents) 127 полуалгебраическая компонента (composante semi-algebrique) полуалгебраическое многообразие (variete semi-algebrique) порядок лексикографический (ordre lexicographique) 95, 127 — общей степени, затем лексикографический (~ de degre to- tal, puis lexicographique) 96, 127 — общей степени, затем обратный лексикографический (~ ~ ~ ~ ~ inverse lexicographique) 96, 127 последовательности примитивные (suites primitives) 93 последовательность Евклида (suite d'Euclide) 93 — полиномиальных остатков (~ de restes de polynomes) 93 — — субрезультантов (~ des polynomes sous-resultants) 93 — Штурма (~ de Sturm) 142 правила перезаписи (regles de reecriture) 109 — упрощения (~ ~ simplification) 108 правило Крамера (methode de Cramer) 114, 118 правильная дробь (fraction propre) 274 представление (representation) 85 — вещественного алгебраического числа (~ d'un nornbre algebrique reel) 147 — внутреннее (~ interne) 97 — дробей (~ des fractions) 83 — естественное (~ naturelle) 86 — каноническое (~ canonique) 85 — компактное (~ compacte) 86 — нормальное (~ normale) 85 — плотное (~ dense) 87 — полиномов (~ des polymomes) 84 — разреженное (~ creux) 87 — распределенное (^ distribuee) 97 — рациональных функций (~ des fonctions rationelles) 98 — регулярное (~ reguliere) 84 — рекурсивное (~ recursive) 31, 71, 97 — целых чисел (~ des entiers) 79 преобразование Лапласа (transformation de Laplace) 64 пример Мора (example de Mora) 137 примитивная часть (partie primitive) 174 Компьютерная алгебра 341 примитивные последовательности (suites primitives) 93 примитивный полином (polynome primitif) 174 — элемент (element primitif) 107 принцип Лиувилля (principe de Liouville) 226 — модулярных вычислений (~ ~ Calcul Modulaire) 185 проблема Риша (probleme de Risch) 242 простейшие дроби (elements simples) 273 простой радикал (radical simple) lOi Пуассона ряды (series de Poisson) 125 Пюизо ряды (~ ~ Puiseux) 124 радикал вложенный (radical imbrique) 101, 103 — простой (~ simple) 101 разбиение (decomposition) 149 — инвариантное (~ invariante) 149 — отмеченное (~ marquee) 149 — цилиндрическое (~ cylindrique) 150, 151 разбухание промежуточных данных (croissance des donnees intermedi-aires) 80 разложение на множители полиномов (factorisation des polynomes) 187 — — — целых чисел (factorisation des entiers) 82 — — свободные от квадратов множители (decomposition sans facteurs multiples) 270 разностные уравнения (equations aux differences) 260 разреженная матрица (matrice creuse) 117 разреженное представление (representation creux) 87 распределенное представление (representation distribuee) 97 расширение алгебраическое (extension algebrique) 77 рациональная функция (fonction rationnelle) 98 рациональное число (nombre rationnel) 83 регулярная особенность (singularite reguliere) 258 регулярное представление (representation reguliere) 84 редукция (reduction) 127 — плохая (mauvaise reduction) 178 — хорошая (bonne reduction) 167, 178 редуцированный базис (base reduite) 130 — полином (polynome reduit) 128 результант (resultants) 34, 183, 274, 275 рекурсивное представление (representation recursive) 31, 71, 97 решения паразитические (solutions parasites) 138 Ричардсона теорема (theoreme de Richardson) 217 Риша лемма (lemme de Risch) 244, 245 — проблема (probleme de ~) 242 — теорема (theoreme de ~) 239 ряды Лорана (series de Laurent) 124 — Пуассона (~ ~'Poisson) 125 — Пюизо (~ ~ Puiseux) 124 — Тейлора (~ ~ Taylor) 47, 119, 122, 124 — Фурье (~ ~ Fourier) 124 свойство Чёрча - Россера (propriete de Church - Rosser) 129 Сильвестра матрица (matrice de Sylvester) 171, 275 342 Предметный указатель Сильвестра тождество (identite de Sylvester) 116 Сингера теорема (theoreme de Singer) 249 Сингера - Дэвенпорта теорема (~ ~ Singer-Davenport) 250 сложение дробей (addition des tractions) 83 — полиномов (~ ~ polynomes) 88 содержание полинома (contenu d'un polynome) 174 стандартный базис (base standard) 129 старший коэффициент (coefficient principal) 205, 209, 210 — моном (monome principal) 128 — член (terme principal 128 структурная теорема (theoreme de structure) 110 Тейлора ряды (series de Taylor) 47, 119, 122, 124 теорема Берлекэмпа (theoreme de Berlekamp) 190 — Дэвенпорта (~ ~ Davenport) 240, 245 — Ковачича (~ ~ Kovacic) 247 — Морли (~ ~ Morley) 56 — неприводимости Гильберта (~ d'irreductibilite de Hil- bert) 207 — об остатках китайская (~ chinois des restes) 278, 280 — — — — обобщенная (~ ~ ~ ~ generalise) 279, 281 — о субрезультантах (~ des sous-resultants) 94 — Ричардсона (~ de Richardson) 217 — Риша (~ ~ Risch) 239 —'- Сингера (~ .~ Singer) 249 — Сингера - Дэвенпорта (~ ~ Singer-Davenport) 250 — структурная (~ ~ structure) 110 — Ферма малая (petit theoreme de Fermat) 189 — Штурма (~ de Sturm) 143 тождество Безу (identite de Bezout) 272 — Сильвестра (~ ~ Sylvester) 116 точность (precision) 23 трансцендентная функция (fonction transcendente) 108 Уилкинсона полином (polynome de Wilkinson) 146 умножение дробей (multiplication des fractions) 83 — некоммутативное (~ поп commutative) 52 — полиномов (~ des polynomes) 88 упрощение (simplification) 47, 84 — формул (~ des formules) 53 уравнение линейное рекуррентное (equation recurrente lineaire) 257 — Фредгольма (~ de Fredholm) 66 — характеристическое (~ caracteristique) 259 уравнения линейные (equations lineaires) 187 — разностные (~ aux differences) 260 Ферма малая теорема (petit theoreme de Fermat) 189 формальное дифференцирование (derivation formelle) 215 формула Мечина (formule de Mechain) 28 Фредгольма уравнение (equation de Fredholm) 66 Фробениуса алгоритм (algorithme de Frobenius) 256 343 Компьютерная алгебра функция алгебраическая (fonction algebrique) 101, 104 — лиувиллева (~ liouvillienne) 247 — рациональная (~ rationnelle) 98 — типа Е над полем К (~ de type E sur un corp К) 241 — типа L над полем К. (~ ~ ~ L sur un согр Л) 24l — трансцендентная (~ transcendente) 108 — элементарная (~ elementaire) 225 Фурье ряды (series de Fourier) 124 характеристический полином (polynome caracteristique) 41 характеристическое уравнение (equation caracteristique) 259 хорошая редукция (bonne reduction) 167, 178 И^ассенхауза алгоритм (algorithme de Zassenhaus) 193 цилиндрическое разбиение (decomposition cylindrique) 150, 151 часть примитивная (partie primitive) 174 Чёрча -- Россера свойство (propriete de Church - Rosser) 129 число алгебраическое (nombre algebrique) 101 — рациональное (~ rationnel) 83 — с плавающей точкой (~ fiottant) 83 — с плохой редукцией (~ de mauvaise reduction) 167 — с хорошей редукцией (~ ~ bonne reduction) i67 — р-адическое (~ p-adique) 199 член старший (terme principal) 128 Штурма последовательность (suite de Sturm) 142 — теорема (theoreme de ~) 143 экспонента (exponentielle) 111 эквивалентные полиномы (polynomes equivalents) 127 элемент примитивный (element primitif) 107 элементарная образующая (generateur „elementaire) 225 — функция (fonction ~) 225 элиминация кванторов (elimination des quantificateurs) 156, 157 Эрмита метод (methode de Hermite) 220 явные вычисления (calcul explicite) 112 ядро (noyau) 108 AlPi 6 АМР 69 bignum 80 CAMAL 84 CoCoa 6 DESIR 261 FROBENIUS 260 LISP 20 346 Оглавление 2.5. Представления рациональных функций ...... 98 2.6. Представление алгебраических функций ..... 101 2.6.1. Простые радикалы ........... 101 2.6.2. Вложенные радикалы .......... 103 2.6.3. Алгебраические функции общего вида . . 104 2.6.4. Примитивные элементы ......... 107 2.7. Представление трансцендентных функций .... 108 2.8. Представления матриц ............. 112 2.8.1. Плотные матрицы ............ 113 2.8.2. Алгоритм Барейса ........... 115 2.8.3. Разреженные матрицы .......... 117 2.9. Представления рядов ............. 119 2.9.1. Ряды Тейлора: простой метод ...... 119 2.9.2. Ряды Тейлора: метод Нормана ...... 122 2.9.3. Другие ряды .............. 124 Глава 3. Полиномиальное упрощение .......... 126 3.1. Упрощение полиномиальных уравнений ...... 126 3.1.1. Редукция полиномов .......... 127 3.1.2. Стандартные базисы (Гре'бнера) ..... 129 3.1.3. Решение системы полиномов ....... 130 3.1.4. Алгоритм Бухбергера .......... 133 3.1.5. Сравнения с другими методами ..... 137 3.2. Упрощение систем вещественных полиномов . . . 139 3.2.1. Случай R1 ..............'. 140 3.2.1.1. Изоляция корней ........ 142 3.2.1.2. Вещественные алгебраические числа 147 3.2.2. Общий случай (некоторые определения) 148 3.2.2.1. Разбиение пространства R" ... 149 3.2.3. Цилиндрические разбиения ....... 150 3.2.3.1. Случай пространства R ..... 153 3.2.3.2. Общий случай .......... 155 3.2.4. Приложения цилиндрического разбиения . 156 3.2.4.1. Элиминация кванторов ...... 156 3.2.4.2. Робототехника ......... 159 Глава 4. Современные алгоритмы ............ 162 4.1. Модулярные методы .............. 162 Компьютерная алгебра 4.1.1. НОД при одной переменной ....... 4.1.1.1. Соответствие модулярное - целое 4.1.1.2. Вычисление ПОД ......... 4.1.1.3. Стоимость алгоритма ...... 4.1.2. НОД при нескольких переменных ..... 4.1.2.1. Плохая редукция ........ 4.1.2.2. Алгоритм ............ 4.1.2.3. Стоимость приведенного алгоритма 4.1.3. Другие применения модулярных методов 4.1.3.1. Вычисление результанта ..... 4.1.3.2. Вычисление определителей .... 4.1.3.3. Обращение матрицы ....... 4.1.3.4. Другие приложения ....... 4.2. р-адические методы .............. 4.2.1. Разложение полиномов от одной переменной 4.2.1.1. Алгоритм Берлекэмпа ...... 4.2.1.2. Соотношение модулярное - целое 4.2.2. Лемма Гензеля - линейный вариант . . . 4.2.2.1. Лемма Гензеля - квадратичный вариант ............ 4.2.2.2. Лемма Гензеля - уточнение алгоритма ........... 4.2.2.3. Алгоритм разложения на множители 4.2.2.4. Старший коэффициент ...... 4.2.3. Разложение для нескольких переменных 4.2.3.1. Алгоритм ............ 4.2.3.2. Старший коэффициент ...... 4.2.4. Другие применения р-адических методов 4.2.4.1. НОД с помощью р-адического алгоритма ........... Глава 5. Формальное интегрирование и дифференциальные уравнения .................... 5.1. Формальное интегрирование .......... 5.1.1. Введение ............... 5.1.2. Интегрирование рациональных функций . . 5.1.2.1. Наивный метод ......... 5.1.2.2. Метод Эрмита .......... 348 Оглавление 5.1.2.3. Метод Горовица ......... 221 5.1.2.4. Логарифмическая часть ..... 222 5.1.3. Интегрирование более сложных функций . 224 5.1.4. Интегрирование логарифмических функций 226 5.1.4.1. Лемма о разложении ...... 227 5.1.4.2. Полиномиальная ча^ть ...... 228 5.1.4.3. Рациональная и логарифмическая части ............. 230 5.1.5. Интегрирование экспоненциальных функций 231 5.1.5.1. Лемма о разложении ....... 232 5.1.5.2. Обобщенная полиномиальная часть 234 5.1.5.3. Рациональная и логарифмическая части ............. 235 5.1.6. Интегрирование смешанных функций . . . 236 • 5.1.7. Интегрирование алгебраических функций . 239 5.1.8. Интегрирование неэлементарных функций . 240 5.2. Алгебраические решения О.Д.У. ........ 242 5.2.1. Уравнения первого порядка ....... 242 5.2.1.1. Проблема Риша .......... 242 5.2.1.2. Теорема Дэвенпорта ....... 245 5.2.2. Уравнения второго порядка ........ 246 5.2.3. Уравнения произвольного порядка .... 249 5.2.3.1. Однородные уравнения ...... 249 5.2.3.2. Неоднородные уравнения ..... 249 5.3. Асимптотические решения О.Д.У. ........ 251 5.3.1. Мотивация и история .......... 251 5.3.2. Классификация особенностей ...... 252 5.3.3. Программа для решения О.Д.У. в регулярной особенности .............. 256 5.3.4. Общая структура программы ....... 258 5.3.5. Несколько примеров применения программы "DESIR" ................ 261 5.3.5.1. Примеры с уравнением Бесселя . . 261 5.3.5.2. Другой пример ......... 265 Дополнение. Основные сведения из алгебры ....... 269 A.I. Разложение на свободные от квадратов множители 269 А.2. Расширенный алгоритм Евклида ......... 271 Компьютерная алгебра А.З. Простейшие дроби ............. А. 4. Результант ................ А.5. Китайская теорема об остатках ...... А.5.1. Случай целых чисел ........ А.5.2. Случай полиномов ......... Приложение. REDUCE: система компьютерной алгебры R.I. Введение ................ R.I.I. Примеры интерактивного использования R.2. Синтаксис системы REDUCE ........ R.2.1. Синтаксические элементы ..... Числа ............... Переменные ............. Операторы .............. R.2.2. Выражения ............ R.2.2.1. Различные типы выражений . . R.2.2.2. Упрощение выражений .... R.2.2.3. Списочные выражения ... R.2.3. Объявления ........... R.2.3.1. Простые переменные .... R.2.3.2. Асимптотические объявления R.2.3.3. Объявления массивов . . . R.2.3.4. Объявления операторов . . R.2.3.5. Объявления процедур . . . R.2.4. Команды ............. R.2.4.1. Оператор присваивания . . R.2.4.2. Групповые команды .... R.2.4.3. Условные операторы .... R.2.4.4. Команды повторения .... R.2.4.5. Блоки .......... R.3. Встроенные возможности ......... R.3.1. Префиксные операторы ...... R.3.1.1. Числовые операторы .... R.3.1.2. Математические операторы R.3.1.3. Дифференцирование .... R.3.1.4. Интегрирование ...... R.3.1.5. Разложение на множители R.3.1.6. Результанты ....... 350 Оглавление R.3.1.7. Решение систем уравнений .... 300 R.3.2. Работа с выражениями ......... 301 R.3.2.1. Вывод выражений ........ 301 R.3.2.2. Части выражений ........ 304 R.3.3. Подстановки .............. 305 R.3.3.1. Локальные подстановки ..... 306 R.3.3.2. Глобальные подстановки ..... 306 R.4. Матричная алгебра .............. 309 R.5. Заключение .................. 310 1 Литература ..................... 311 \ Предметный указатель ................ 336 1 Научное издание Джеймс Дэвенпорт, Ивон Сирэ, Эвелина Турнье КОМПЬЮТЕРНАЯ АЛГЕБРА Системы и алгоритмы алгебраических вычислений Заведующий редакцией академик В. И. Арнольд Зам. зав. редакцией А. С. Попов Ст. научный редактор Г.М. Цукерман Художественный редактор В. И. Шаповалов Художник О. С. Василькова Корректор В.Н. Радакова ИБ № 7325 Оригинал-макет подготовлен на персональном компьютере и от- печатан на лазерном принтере в издательстве «Мир» Подписано к печати 21.02.91. Формат 60х90 1/16. Бумага офсетная №2. Печать офсетная. Объем 11,0 бум. л. Усл. печ. л. 22,0. Усл. кр.-отт. 22,0. Уч.-изд. л. 17,84. Изд. №1/7082. Тираж 7 000 экз. Зак.№ 176. Цена 4 р. 90 к. Издательство «Мир» В/О «Совэкспорткнига» Государственного комитета СССР по печати. 129820, ГСП, Москва, 1-й Рижский пер., 2. Тульская типография Государственного комитета СССР по печати. 300600. г. Тула, проспект Ленина, 109