Computer algebra: Systems and algorithms for algebraic computation

Cover
Title page
Preface
Foreword to English translation
1 How to use a Computer Algebra system
1.1 Introduction
1.2 Features of Computer Algebra systems
1.3 Syntax of the associated languages
1.4 Areas covered by existing systems
1.5 Computer Algebra by example
	1.5.1 Simple operations on numbers
	1.5.2 Polynomials and rational fractions
	1.5.3 Matrix calculation
	1.5.4 Differentiation - Taylor series
	1.5.5 Simplification of formulae
	1.5.6 Integration
	1.5.7 Ordinary differential equations
1.6 MACSYMA's possibilities in Algebra
	1.6.1 General Possibilities
	1.6.2 The division of the circle into 17 equal parts
1.7 Availability of MACSYMA
1.8 Other systems
1.9 AXIOM
2 The problem of data representation
2.1 Representations of integers
2.2 Representations of fractions
2.3 Representations of polynomials
	2.3.1 Canonical and normal representations
	2.3.2 Dense and sparse representations
	2.3.3 The g.c.d
2.4 Polynomials in several variables
2.5 Representations of rational functions
2.6 Representations of algebraic functions
	2.6.1 The simple radicals
	2.6.2 Nested radicals
	2.6.3 General algebraic functions
	2.6.4 Primitive elements
	2.6.5 Dynamic evaluation of algebraic functions
2.7 Representations of transcendentals
2.8 Representations of matrices
	2.8.1 Dense matrices
	2.8.2 Bareiss' algorithm
	2.8.3 Sparse matrices
2.9 Representations of series
	2.9.1 Taylor series: simple method
	2.9.2 Taylor series: Norman's method
	2.9.3 Other series
3 Polynomial simplification
3.1 Simplification of polynomial equations
	3.1.1 Reductions of polynomials
	3.1.2 Standard (Gröbner) bases
	3.1.3 Solution of a system of polynomials
	3.1.4 Buchberger's algorithm
	3.1.5 Relationship to other methods
3.2 Simplification of real polynomial systems
	3.2.1 The case of R¹
	3.2.1.1 Isolation of roots
	3.2.1.2 Real algebraic numbers
	3.2.2 The general case - (some definitions)
	3.2.2.1 Decomposition of R^n
	3.2.3 Cylindrical decompositions
	3.2.3.1 The case of R²
	3.2.3.2 The general case
3.2.4 Applications of cylindrical decomposition
	3.2.4.1 Quantifier elimination
	3.2.4.2 Robotics
4 Advanced algorithms
4.1 Modular methods
	4.1.1 g.c.d. in one variable
	4.1.1.1 The modular - integer relationship
	4.1.1.2 Calculation of the g.c.d
	4.1.1.3 Cost of this algorithm
	4.1.2 g.c.d. in several variables
	4.1.2.1 Bad reduction
	4.1.2.2 The algorithm
	4.1.2.3 Cost of this algorithm
	4.1.3 Other applications of modular methods
	4.1.3.1 Resultant calculation
	4.1.3.2 Calculating determinants
	4.1.3.3 Inverse of a matrix
	4.1.3.4 Other applications
4.2 p-adic methods
	4.2.1 Factorisation of polynomials in one variable
	4.2.1.1 Berlekamp's algorithm
	4.2.1.2 The modular - integer relationship
	4.2.2 Hensel's Lemma - linear version
	4.2.2.1 Hensel's Lemma - quadratic version
	4.2.2.2 Hensel's Lemma - refinement of the inverses
	4.2.2.3 The factorisation algorithm
	4.2.2.4 The leading coefficient
	4.2.3 Factorisation in several variables
	4.2.3.1 The algorithm
	4.2.3.2 The leading coefficient
	4.2.4 Other applications of p-adic methods
	4.2.4.1 g.c.d. by a p-adic algorithm
5 Formal integration and differential equations
5.1 Formal integration
	5.1.1 Introduction
	5.1.2 Integration of rational functions
	5.1.2.1 The naïve method
	5.1.2.2 Hermite's method
	5.1.2.3 Horowitz-Ostrogradski method
	5.1.2.4 The logarithmic part
	5.1.3 The integration of more complicated functions
	5.1.4 Integration of logarithmic functions
	5.1.4.1 The decomposition lemma
	5.1.4.2 The polynomial part
	5.1.4.3 The rational and logarithmic part
	5.1.5 Integration of exponential functions
	5.1.5.1 The decomposition lemma
	5.1.5.2 The generalised polynomial part
	5.1.5.3 The rational and logarithmic part
	5.1.6 Integration of mixed functions
	5.1.7 Integration of algebraic functions
	5.1.8 Integration of non-elementary functions
5.2 Algebraic solutions of o.d.e.s
	5.2.1 First order equations
	5.2.1.1 Risch's problem
	5.2.1.2 A theorem of Davenport
	5.2.2 Second order equations
	5.2.3 General order equations
	5.2.3.1 Homogeneous equations
	5.2.3.2 Inhomogeneous equations
5.3 Asymptotic solutions of o.d.e.s
	5.3.1 Motivation and history
	5.3.2 Classification of singularities
	5.3.3 A program for solving o.d.e.s at a regular singularity
	5.3.4 The general structure of the program
	5.3.5 Some examples treated by "DESIR"
	5.3.5.1 Examples with Bessel's equation
	5.3.5.2 Another example
Appendix. Algebraic background
	A.l Square-free decomposition
	A.2 The extended Euclidean algorithm
	A.3 Partial fractions
	A.4 The resultant
	A.5 Chinese remainder theorem
		A.5.1 Case of integers
		A.5.2 Case of polynomials
	A.6 Sylvester's identity
	A.7 Termination of Buchberger's algorithm
Annex. REDUCE: a Computer Algebra system
	R.l Introduction
		R.1.1 Examples of interactive use
	R.2 Syntax of REDUCE
	R.2.1 Syntactic elements
	R.2.2 Expressions
		R.2.2.1 Different types of expressions
		R.2.2.2 Simplification of expressions
		R.2.2.3 List expressions
	R.2.3 Declarations
		R.2.3.1 Plain variables
		R.2.3.2 Asymptotic declarations
		R.2.3.3 Array declarations
		R.2.3.4 Operator declarations
		R.2.3.5 Procedure declarations
	R.2.4 Commands
		R.2.4.1 Assignment
		R.2.4.2 Instruction group
		R.2.4.3 Conditional statement
		R.2.4.4 Iteration statement
		R.2.4.5 Blocks
		R.2.4.6 Local value assignment
	R.3 Built-in facilities
	R.3.1 Prefix operators
		R.3.1.1 Numeric operators
		R.3.1.2 Mathematical operators
		R.3.1.3 Differentiation
		R.3.1.4 Integration
		R.3.1.5 Factorisation
		R.3.1.6 Resultants
		R.3.1.7 Solution of systems of equations
	R.3.2 Manipulation of expressions
		R.3.2.1 Output of expressions
		R.3.2.2 Parts of expressions
	R.3.3 Substitution
		R.3.3.1 Local substitution
		R.3.3.2 Global substitution
	R.4 Matrix algebra
	R.5 IRENA
	R.6 Conclusion
Bibliography
Index