Algorithmic Algebra

Автор(ы):Bhudanesvar Mishra
06.10.2007
Год изд.:1993
Описание: The book is meant for graduate students with a training in theoretical computer science, who would like to either do research in computational algebra or understand the algorithmic underpinnings of various commercial symbolic computational systems: Mathematica, Maple or Axiom, for instance. Also, it is hoped that other researchers in the robotics, solid modeling, computational geometry and automated theorem proving communities will find it useful as symbolic algebraic techniques have begun to play an important role in these areas. The main four topics-Grobner bases, characteristic sets, resultants and semialgebraic sets-were picked to reflect my original motivation. The choice of the topics was partly influenced by the syllabii proposed by the Research Institute for Symbolic Computation in Linz, Austria, and the discussions in Hearn's Report ("Future Directions for Research in Symbolic Computation"). The book is meant to be covered in a one-semester graduate course comprising about fifteen lectures. The book assumes very little background other than what most beginning computer science graduate students have. For these reasons, I have attempted to keep the book self-contained and largely focussed on the very basic materials.
Оглавление:
Algorithmic Algebra — обложка книги. Обложка книги.
1 Introduction [1]
  1.1 Prologue: Algebra and Algorithms [1]
  1.2 Motivations [4]
    1.2.1 Constructive Algebra [5]
    1.2.2 Algorithmic and Computational Algebra [6]
    1.2.3 Symbolic Computation [7]
    1.2.4 Applications [9]
  1.3 Algprithmic Notations [13]
    1.3.1 Data Structures [13]
    1.3.2 Control Structures [15]
  1.4 Epilogue [18]
    Bibliographic Notes [20]
  2 Algebraic Preliminaries [23]
  2.1 Introduction to Rings and Ideals [23]
    2.1.1 Rings and Ideals [26]
    2.1.2 Homomorphism, Contraction and Extension [31]
    2.1.3 Ideal Operations [33]
  2.2 Polynomial Rings [35]
    2.2.1 Dickson's Lemma [36]
    2.2.2 Admissible Orderings on Power Products [39]
  2.3 Grobner Bases [44]
    2.3.1 Grobner Bases in (?) [46]
    2.3.2 Hilbert's Basis Theorem [47]
    2.3.3 Finite Grobner Bases [49]
  2.4 Modules and Syzygies [49]
  2.5 S-Polynomials [55]
    Problems [60]
    Solutions to Selected Problems [63]
    Bibliographic Notes [69]
3 Computational Ideal Theory [71]
  3.1 Introduction [71]
  3.2 Strongly Computable Ring [72]
    3.2.1 Example: Computable Field [73]
    3.2.2 Example: Ring of Integers [76]
  3.3 Head Reductions and Grobner Bases [80]
    3.3.1 Algorithm to Compute Head Reduction [83]
    3.3.2 Algorithm to Compute Grobner Bases [84]
  3.4 Detachability Computation [87]
    3.4.1 Expressing with the Grobner Basis [88]
    3.4.2 Detachability [92]
  3.5 Syzygy Computation [93]
    3.5.1 Syzygy of a Grobner Basis: Special Case [93]
    3.5.2 Syzygy of a Set: General Case [98]
  3.6 Hilbert's Basis Theorem: Revisited [102]
  3.7 Applications of Grobner Bases Algorithms [103]
    3.7.1 Membership [103]
    3.7.2 Congruence, Subideal and Ideal Equality [ 103]
    3.7.3 Sum and Product [104]
    3.7.4 Intersection [105]
    3.7.5 Quotient [106]
    Problems [108]
    Solutions to Selected Problems [118]
    Bibliographic Notes [130]
4 Solving Systems of Polynomial Equations [133
  4.1 Introduction [133]
  4.2 Triangular Set [134]
  4.3 Some Algebraic Geometry [138]
    4.3.1 Dimension of an Ideal [141]
    4.3.2 Solvability: Hilbert's Nullstellensatz [142]
    4.3.3 Finite Solvability [145]
  4.4 Finding the Zeros [149]
    Problems [152]
    Solutions to Selected Problems [157]
    Bibliographic Notes [165]
5 Characteristic Sets [167]
  5.1 Introduction [167]
  5.2 Pseudodivision and Successive Pseudodivision [168]
  5.3 Characteristic Sets [171]
  5.4 Properties of Characteristic Sets [176]
  5.5 Wu-Ritt Process [178]
  5.6 Computation [181]
  5.7 Geometric Theorem Proving [186]
    Problems [189]
    Solutions to Selected Problems [192]
    Bibliographic Notes [196]
6 An Algebraic Interlude [199]
  6.1 Introduction [199]
  6.2 Unique Factorization Domain [199]
  6.3 Principal Ideal Domain [207]
  6.4 Euclidean Domain [208]
  6.5 Gauss Lemma [211]
  6.6 Strongly Computable Euclidean Domains [212]
    Problems [216]
    Solutions to Selected Problems [220]
    Bibliographic Notes [223]
7 Resultants and Subresultants [225]
  7.1 Introduction [225]
  7.2 Resultants [227]
  7.3 Homomorphisms and Resultants [232]
  7.3.1 Evaluation Homomorphism [234]
  7.4 Repeated Factors in Polynomials and Discriminants [238]
  7.5 Determinant Polynomial [241]
    7.5.1 Pseudodivision: Revisited [244]
    7.5.2 Homomorphism and Pseudoremainder [246]
  7.6 Polynomial Remainder Sequences [247]
  7.7 Subresultants [250]
    7.7.1 Subresultants and Common Divisors [255]
  7.8 Homomorphisms and Subresultants [262]
  7.9 Subresultant Chain [265]
  7.10 Subresultant Chain Theorem [274]
    7.10.1 Habicht's Theorem [274]
    7.10.2 Evaluation Homomorphisms [276]
    7.10.3 Subresultant Chain Theorem [279]
    Problems [283]
    Solutions to Selected Problems [291]
    Bibliographic Notes [296]
8 Real Algebra [297]
  8.1 Introduction [297]
  8.2 Real Closed Fields [298]
  8.3 Bounds on the Roots [306]
  8.4 Sturm's Theorem [309]
  8.5 Real Algebraic Numbers [315]
    8.5.1 Real Algebraic Number Field [316]
    8.5.2 Root Separation, Thorn's Lemma and Representation [319]
  8.6 Real Geometry [333]
    8.6.1 Real Algebraic Sets [337]
    8.6.2 Delineability [339]
    8.6.3 Tarski-Seidenberg Theorem [345]
    8.6.4 Representation and Decomposition of Semialgebraic Sets [347]
    8.6.5 Cylindrical Algebraic Decomposition [348]
    8.6.6 Tarski Geometry [354]
    Problems [361]
    Solutions to Selected Problems [372]
    Bibliographic Notes [381]
Appendix A: Matrix Algebra [385]
A.I Matrices [385]
A.2 Determinant [386]
A.3 Linear Equations [388]
Bibliography [391]
Index [409]
Формат: djvu
Размер:4057615 байт
Язык:ENG
Рейтинг: 257 Рейтинг
Открыть: