htswanalysis/MACS/lib/gsl/gsl-1.11/poly/TODO

   1 * Estimate error on general poly roots using Newton method? Allow for
   2 multiple roots and higher derivatives
   3
   4 * Newton-Maehly (Newton with implicit deflation)
   5
   6 * Jenkins-Traub
   7
   8 * Brian Smith's adaptation of Laguerre's method
   9
  10 * Hirano's method, SIAM J Num Anal 19 (1982) 793-99 by Murota
  11
  12 * Carstensen, Petkovic, "On iteration methods without derivatives for
  13 the simultaneous determination of polynomial zeros", J. Comput. Appl.
  14 Math., 45 (1993) 251-267
  15
  16 * Investigate this,
  17
  18  > NA Digest   Sunday, July 11, 1999   Volume 99 : Issue 28
  19  >
  20  > From: Murakami Hiroshi <nadigest@tmca.ac.jp>
  21  > Date: Sun, 11 Jul 1999 18:56:54 +0900 (JST)
  22  > Subject: Code for Wilf's Complex Bisection Method
  23  >
  24  >   A sample demo source of root finding method for the general complex
  25  > coefficient polynomial is placed to URL <ftp://ftp.tmca.ac.jp/wilf.taz>.
  26  > It is about 8KB in size and is a tar and gnu-zipped file.
  27  > The algorithm is taken from the following reference:
  28  >     HERBERT S.WILF,"A Global Bisection Algorithm for Computing the Zeros
  29  >     of Polynomials in the Complex Plane",ACM.vol.25,No.3,July 1978,pp.415-420.
  30  >
  31  >   The Wilf's method is the complex plane version of the Sturm bi-section
  32  > method for the real polynomial. And theoretically very interesting.
  33  > For the given complex interval (complex rectilinear region and sides are
  34  > parallel to the x-y axis), the procedure gives the count of the complex
  35  > roots of the polynomial inside the interval. Thus, successive bi-section
  36  > or quad-section of the interval can give the sequence of the shrinking
  37  > intervals containing the root inside to attain the required accuracies.
  38  >   The source code is written mostly Fortran77 language, however some
  39  > violations are intensionally left as: 1: The DO-ENDDO loop structure.
  40  > 2: The longer than 6 letter names. 3: The use of under-score letter.
  41  > 4: The use of include statement.
  42  >   The code will be placed in the public domain.
  43  >
  44
  45 * Investigate this
  46
  47 From: "Steven G. Johnson" <stevenj@alum.mit.edu>
  48 To: help-gsl@gnu.org
  49 Subject: [Help-gsl] (in)accuracy of gsl_poly_complex_solve for repeated
  50         roots?
  51 Date: Sun, 05 Jun 2005 16:25:40 -0400
  52 Precedence: list
  53 Envelope-to: bjg@network-theory.co.uk
  54
  55 Hi, I noticed that gsl_poly_complex_solve seems to be surprisingly
  56 inaccurate.  For example, if you ask it for the roots of 1 + 4x + 6x^2 +
  57 4x^3 + x^4, which should have x = -1 as a four-fold root (note that the
  58 coefficients and solutions are exactly representable), it gives roots:
  59
  60 -0.999903+9.66605e-05i
  61 -0.999903-9.66605e-05i
  62 -1.0001+9.66834e-05i
  63 -1.0001-9.66834e-05i
  64
  65 i.e. it is accurate to only 4 significant digits.  (On the other hand,
  66 when I have 4 distinct real roots it seems to be accurate to machine
  67 precision.)
  68
  69 If this kind of catastrophic accuracy loss is intrinsic to the algorithm
  70 when repeated roots are encountered, please note it in the manual.
  71
  72 However, I suspect that there may be algorithms to obtain higher
  73 accuracy for multiple roots.   I found the below references in a
  74 literature search on the topic, which you may want to look into.  (The
  75 first reference can be found online at
  76 http://www.neiu.edu/~zzeng/multroot.htm)
  77
  78 Cordially,
  79 Steven G. Johnson
  80
  81 ---------------------------------------------------------------------
  82 Algorithm 835: MULTROOT - a Matlab package for computing polynomial
  83 roots and multiplicities
  84 Zeng, Z. (Dept. of Math., Northeastern Illinois Univ., Chicago, IL, USA)
  85 Source: ACM Transactions on Mathematical Software, v 30, n 2, June 2004,
  86 p 218-36
  87 ISSN: 0098-3500 CODEN: ACMSCU
  88 Publisher: ACM, USA
  89
  90 Abstract: MULTROOT is a collection of Matlab modules for accurate
  91 computation of polynomial roots, especially roots with nontrivial
  92 multiplicities. As a blackbox-type software, MULTROOT requires the
  93 polynomial coefficients as the only input, and outputs the computed
  94 roots, multiplicities, backward error, estimated forward error, and the
  95 structure-preserving condition number. The most significant features of
  96 MULTROOT are the multiplicity identification capability and high
  97 accuracy on multiple roots without using multiprecision arithmetic, even
  98 if the polynomial coefficients are inexact. A comprehensive test suite
  99 of polynomials that are collected from the literature is included for
 100 numerical experiments and performance comparison (21 refs.)
 101
 102 ---------------------------------------------------------------------
 103 Ten methods to bound multiple roots of polynomials
 104 Rump, S.M. (Inst. fur Informatik III, Tech. Univ. Hamburg-Harburg,
 105 Hamburg, Germany) Source: Journal of Computational and Applied
 106 Mathematics, v 156, n 2, 15 July 2003, p 403-32
 107 ISSN: 0377-0427 CODEN: JCAMDI
 108 Publisher: Elsevier, Netherlands
 109
 110 Abstract: Given a univariate polynomial P with a k-fold multiple root or
 111 a k-fold root cluster near some z, we discuss nine different methods to
 112 compute a disc near z which either contains exactly or contains at least
 113 k roots of P. Many of the presented methods are known and of those some
 114 are new. We are especially interested in the behavior of methods when
 115 implemented in a rigorous way, that is, when taking into account all
 116 possible effects of rounding errors. In other words, every result shall
 117 be mathematically correct. We display extensive test sets comparing the
 118 methods under different circumstances. Based on the results, we present
 119 a tenth, hybrid method combining five of the previous methods which, for
 120 give z, (i) detects the number k of roots near z and (ii) computes an
 121 including disc with in most cases a radius of the order of the numerical
 122 sensitivity of the root cluster. Therefore, the resulting discs are
 123 numerically nearly optimal
 124
 125
 126
 127 _______________________________________________
 128 Help-gsl mailing list
 129 Help-gsl@gnu.org
 130 http://lists.gnu.org/mailman/listinfo/help-gsl