[q-lang-users] Polynomial Module for Q

[Rob H. <hub...@gm...>]

Dear All,

Albert has very kindly uploaded my (draft) polynomial module "Q[i][X]"
version 0.2; it is available from the "Grab Bag" on the Q website at
<http://q-lang.sourceforge.net/examples.html#Miscellaneous>. Some
documentation is included, containing many examples.

[I'm not sure how Q[i][X] should be pronounced: "quick", "quiz",
"kick(s)", "keys" or "quiche" (!)]

The library is limited to univariate polynomials with numerical coefficient=
s.

This project started out of a desire to factorise the formula for sums
of powers, such as
    Sum (n =3D 1 .. m) : n ^ k

Albert has commented on his website that "this can be seen as the
beginnings of a [computer algebra system] written in Q". Ahem. There's
quite a way to go yet. :-) This module is essentially numeric rather
than symbolic.

The coefficients of the polynomials may be any complex floating point
numbers, but the module contains many routines specifically targeted
at polynomials with (exact) rational complex coefficients (i.e. in
Q[i]).

Q[i] is the algebraic extension of the rational number field Q with i=3Dsqr=
t(-1).

"Q[i][X]" represents (the ring of) polynomials over (the ring) Q[i].

Similarly, the ring of "Gaussian integers" Z[i] is the extension of
the ring Z of integers. Both Z and Z[i] are UFDs (unique factorisation
domains); this is the basis for many of the algorithms, hence the
subtitle of "Polynomial and Gaussian Module".

A polynomial such as "4+3X+X^3" is currently represented by
    poly_with_coeffs [4,3,0,1]
but I hope to have a more readable presentation in a future version.

The module, so far, includes functions for:

  * creating polynomials in terms of the coefficients or the roots;
  * polynomial curve fitting;
  * some common polynomial arithmetic and mathematics functions
      (including GCD, LCM);
  * formal calculus
      (thus: square-free part);
  * DFT polynomials;
  * transformations between "difference systems" and polynomials
      (thus: finite sums and differences);
  * functions to find *all* roots in Q[i] of any polynomial over Q[i];
  * functions to solve up to quartic polynomials "by radicals";
  * functions for finding and using patterns in the coefficients;
      (for example, polynomials of a power of the indeterminate;
palindromic polynomials);
  * functions for finding bounds of the roots;
  * transformations between B=E9zier representations and polynomials.

I hope to extend this further. For example, I need to:

  * add string conversion (using Q Lex Yacc);
  * add some B=E9zier functions;
  * add functions for summarising "features"
      (local extrema; points of inflection);
  * add root approximation functions.

I hope to include these in the next release.

Possibly, *much* later, I might

  * extend support to polynomials over a general ring/field
        (for example, square matrices, symbols)
  * add some support for rational functions

Please report any bugs or errors in the module or in its documentation
to me (either directly or via this mailing list) rather than Albert.
Questions concerning the use of Q[i][X] should probably come (to me)
via the mailing list. Thanks.

Enjoy.

Rob.