Fundamental Problems of Algorithmic Algebra by Chee Keng YapFundamental Problems of Algorithmic Algebra by Chee Keng Yap

Fundamental Problems of Algorithmic Algebra

byChee Keng Yap

Hardcover | February 23, 2000

Pricing and Purchase Info


Earn 1271 plum® points

In stock online

Ships free on orders over $25

Not available in stores


Popular computer algebra systems such as Maple, Macsyma, Mathematica, and REDUCE are now basic tools on most computers. Efficient algorithms for various algebraic operations underlie all these systems. Computer algebra, or algorithmic algebra, studies these algorithms and their properties andrepresents a rich intersection of theoretical computer science with classical mathematics. Fundamental Problems of Algorithmic Algebra provides a systematic and focused treatment of a collection of core problemsthe computational equivalents of the classical Fundamental Problem of Algebra and its derivatives. Topics covered include the GCD, subresultants, modular techniques, thefundamental theorem of algebra, roots of polynomials, Sturm theory, Gaussian lattice reduction, lattices and polynomial factorization, linear systems, elimination theory, Grobner bases, and more. Features DT Presents algorithmic ideas in pseudo-code based on mathematical concepts and can be used with any computer mathematics system DT Emphasizes the algorithmic aspects of problems without sacrificing mathematical rigor DT Aims to be self-contained in its mathematical development DT Ideal for a first course in algorithmic or computer algebra for advanced undergraduates or beginning graduate students
Chee Keng Yap is at New York University.
Title:Fundamental Problems of Algorithmic AlgebraFormat:HardcoverDimensions:528 pages, 3.39 × 4.29 × 0.2 inPublished:February 23, 2000Publisher:Oxford University PressLanguage:English

The following ISBNs are associated with this title:

ISBN - 10:0195125169

ISBN - 13:9780195125160

Look for similar items by category:


Table of Contents

O INTRODUCTION1. Fundamental Problem of Algebra2. Fundamental Problem of Classical Algebraic Geometry3. Fundamental Problem of Ideal Theory4. Representation and Size5. Computational Models6. Asymptotic Notations7. Complexity of Multiplication8. On Bit versus Algebraic Complexity9. Miscellany10. Computer Algebra SystemsI ARITHMETIC1. The Discrete Fourier Transform2. Polynomial Multiplication3. Modular FFT4. Fast Integer Multiplication5. Matrix MultiplicationII THE GCD1. Unique Factorization Domain2. Euclid's Algorithm3. Euclidean Ring4. The Half-GCD problem5. Properties of the Norm6. Polynomial HGCDA. APPENDIX: Integer HGCDIII SUBRESULTANTS1. Primitive Factorization2. Pseudo-remainders and PRS3. Determinantal Polynomials4. Polynomial Pseudo-Quotient5. The Subresultant PRS6. Subresultants7. Pseudo-subresultants8. Subresultant Theorem9. Correctness of the Subresultant PRS AlgorithmIV MODULAR TECHNIQUES1. Chinese Remainder Theorem2. Evaluation and Interpolation3. Finiding Prime Moduli4. Lucky homomorphisms for the GCD5. Coefficient Bounds for Factors6. A Modular GCD algorithm7. What else in GCD computation?IV FUNDAMENTAL THEOREM OF ALGEBRA1. Elements of Field Theory2. Ordered Rings3. Formally Real Rings4. Constructible Extensions5. Real Closed Fields6. Fundamental Theorem of AlgebraVI ROOTS OF POLYNOMIALS1. Elementary Properties of Polynomial Roots2. Root Bounds3. Algebraic Numbers4. Resultants5. Symmetric Functions6. Discriminant7. Root Separation8. A Generalized Hadamard Bound9. Isolating Intervals10. On Newton's Method11. Guaranteed Convergence of Newton IterationVII STURM THEORY1. Sturm Sequences from PRS2. A Generalized Sturm Theorem3. Corollaries and Applications4. Integer and Complex Roots5. The Routh-Hurwitz Theorem6. Sign Encoding of Algebraic Numbers: Thom's Lemma7. Problem of Relative Sign Conditions8. The BKR algorithmVIII GAUSSIAN LATTICE REDUCTION1. Lattices2. Shortest vectors in planar lattices3. Coherent Remainder SequencesIX LATTICE REDUCTION AND APPLICATIONS1. Gram-Schmidt Orthogonalization2. Minkowski's Convex Body Theorem3. Weakly Reduced Bases4. Reduced Bases and the LLL-algorithm5. Short Vectors6. Factorization via Reconstruction of Minimal PolynomialsX LINEAR SYSTEMS1. Sylvester's Identity2. Fraction-free Determinant Computation3. Matrix Inversion4. Hermite Normal Form5. A Multiple GCD Bound and Algorithm6. Hermite Reduction Step7. Bachem-Kannan Algorithm8. Smith Normal Form9. Further ApplicationsXI ELIMINATION THEORY1. Hilbert Basis Theorem2. Hilbert Nullstellensatz3. Specializations4. Resultant Systems5. Sylvester Resultant Revisited6. Interial Ideal7. The Macaulay Resultant8. U-Resultant9. Generalized Characteristic Polynomial10. Generalized U - resultant11. A Multivariate Root BoundA. APPENDIX A: Power SeriesB. APPENDIX B: Counting Irreducible PolynomialsXII GROBNER BASES1. Admissible Orderings2. Normal Form ALgorithm3. Characterizations of Grobner Bases4. Buchberger's Algorithm5. Uniqueness6. Elimination Properties7. Computing in Quotient Rings8. SyzygiesXIII BOUNDS IN POLYNOMIAL IDEAL THEORY1. Some Bounds in Polynomial Ideal Theory2. The Hilbert-Sette Theorem3. Homogeneous Sets4. Cone Decomposition5. Exact Decomposition of NF (I)6. Exact Decomposition of Ideals7. Bouding the Macaulay constants8. Term Rewriting Systems9. A Quadratic Counter10. Uniqueness Property11. Lower BoundsA. APPENDIX: Properties of SoXIV CONTINUED FRACTIONS1. Introductions2. Extended Numbers3. General Terminology4. Ordinary Continued Fractions5. Continued fractions as Mobius transformations6. Convergence Properties7. Real Mobius Transformations8. Continued Fractions of Roots9. Arithmetic Operations