Structured Matrix Based Methods for Approximate Polynomial GCD
Defining and computing a greatest common divisor of two polynomials with inexact coefficients is a classical problem in symbolic-numeric computation. The first part of this book reviews the main results that have been proposed so far in the literature. As
- PDF / 1,570,551 Bytes
- 208 Pages / 425.197 x 680.315 pts Page_size
- 39 Downloads / 198 Views
tesi di perfezionamento in Matematica sostenuta il 5 ottobre 2007 C OMMISSIONE G IUDICATRICE Mariano Giaquinta, Presidente Bernhard Beckermann Dario Bini Luca Gemignani Patrizia Gianni Stefano Marmi Alessandro Profeti
Paola Boito Universit´e de Limoges / CNRS 123 avenue Albert Thomas 87060 Limoges Cedex, France Structured Matrix Based Methods for Approximate Polynomial GCD
Paola Boito
Structured Matrix Based Methods for Approximate Polynomial GCD
c 2011 Scuola Normale Superiore Pisa
ISBN: 978-88-7642-380-2 e-ISBN: 978-88-7642-381-9
“He found him under a pine tree, sitting on the ground, arranging fallen pine cones in a regular design: an isosceles triangle. At that hour of dawn Agilulf always needed to apply himself to some precise exercise: counting objects, arranging them in geometric patterns, resolving problems of arithmetic. It was the hour in which objects lose the consistency of shadow that accompanies them during the night and gradually reacquire colors, but seem to cross meanwhile an uncertain limbo, faintly touched, just breathed on by light; the hour in which one is least certain of the world’s existence. He, Agilulf, always needed to feel himself facing things as if they were a massive wall against which he could pit the tension of his will, for only in this way did he manage to keep a sure consciousness of himself. But if the world around was instead melting into the vague and ambiguous, he would feel himself drowning in that morbid half light, incapable of allowing any clear thought or decision to flower in that void. In such moments he felt sick, faint; sometimes only at the cost of extreme effort did he feel himself able to avoid melting away completely. It was then he began to count: trees, leaves, stones, lances, pine cones, anything in front of him. Or he put them in rows and arranged them in squares and pyramids.”
Italo Calvino, The Nonexistent Knight
Contents
Introduction
xi
Notation
xv
1 Approximate polynomial GCD 1.1. Coefficient-based definitions . . . . . . . . . . 1.1.1. Quasi-GCD . . . . . . . . . . . . . . . 1.1.2. −GCD . . . . . . . . . . . . . . . . . 1.1.3. AGCD . . . . . . . . . . . . . . . . . 1.2. A geometrical interpretation . . . . . . . . . . 1.3. Pseudozeros and root neighborhoods . . . . . . 1.4. A root-based definition . . . . . . . . . . . . . 1.5. Graph-theoretical techniques . . . . . . . . . . 1.6. Formulations of the approximate GCD problem
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
1 2 2 4 5 6 8 13 16 19
2 Structured and resultant matrices 2.1. Toeplitz and Hankel matrices . . . . . . . . . . . . 2.2. Displacement structure . . . . . . . . . . . . . . . 2.2.1. Toeplitz-like matrices . . . . . . . . . . . . 2.2.2. Cauchy-like matrices . . . . . . . . . . . . 2.3. Computation of displacement generators . . . . . . 2.3.1. Sum of displacement structured matrices . 2.3.2. Product of displacement structured matrices 2.3.3. Inverse of a displacement structured matrix 2.4. Fast GEPP for structured matrices . . . . . . . .
Data Loading...
