-----------------------------------------------------------------------------
| List of user-visible changes for the q-Zeilberger package since version 1.4 |
-----------------------------------------------------------------------------
Version 2.3x
************
- New function MakeHomRec[]. Calling
MakeHomRec[rec]
where rec is a recurrence or a list of recurrences returned by qZeil,
transforms inhomogeneous recurrences into homogeneous ones.
Version 2.2x (finished 04-11-02)
************
- If the order is of the form {ord1, ord2}, qZeil tries to find a recurrence
whose order is between ord1 and ord2. Omitting the order is equivalent to
specifying {0, Infinity}.
- New option NumericCheck for qZeil and qTelescope. With NumericCehck -> True,
qZeil and qTelescope check numerically (and therefore fast) whether the
underlying system of equations might have a solution.
Version 2.1x (finished 12-31-01)
************
- New option qParameterized for qTelescope. With qParameterized -> {rat0, rat1, ... },
qTelescope computes coefficients a0, a1, ..., and a closed form for the sum of
a0 f0 + a1 f1 + ... , where fi equals rati multiplied with the input summand.
Here the rati are rational functions in q^k and the ai are constants. Note that
qParameterized cannot be combined with PolyMult.
- If Output is set to True, then intermediate results are written to a notebook
and no longer to the file 'GoOut'.
- qfac has been renamed to qPochhammer. The old name still works for backward
compatibility.
Version 2.0 (finished 05-03-01)
***********
- No user-visible changes.
Version 1.9 (finished 10-05-00)
***********
- The source code is now distributed as one single file "qZeil.m".
Note that this file is encoded. This means it is not readable but
can be treated like any normal Mathematica file.
- The default value for Output has been changed to False.
- The option EquationSolver now allows to specify any nullspace algorithm
that takes as argument a matrix and returns a basis for its nullspace.
- To compute the certificate of the last computation, the user has to
call Cert[] instead of Cert.
- The function Check1[] has been superseded by CheckRec[]. Calling
CheckRec[rec, f]
where rec is a recurrence or a list of recurrences returned by qZeil,
checks whether f satisfies rec.
Version 1.8 (finished 12-13-99)
***********
- The whole package has been adapted for Mathematica 3.0. The collection
of examples (qZeilExamples.txt) is now distributed as a MMA notebook
(called qZeilExamples.nb).
- The pivot search in Erhard Aichinger's ENullSpace has been completely
rewritten resulting in an overall speedup factor between 1 and 20.
Several out-of-memory examples can be done now.
- Pulling out constant factors in the coefficients of the Sigma[.] results
in a VERY dramatic speedup for many applications. With this improvement
the collection of examples could be extended significantly.
- The boolean variable Simp for turning on/off simplification is no longer
supported.
- SameRec[rec1, rec2] checks whether the recurrences rec1 and rec2 are equal.
This is useful for transformation formulas with several pages of output,
since SameQ does not necessarily give True for equal recurrences and
Together[ rec1[[2]] - rec2[[2]] ] can be very time-consuming.
- Option FindAlpha has been superseded by FindAlphaBeta. For a description
see changes in version 1.5 below.
- New option EquationSolver for qZeil and qTelescope. With EquationSolver ->
NullSpace, qZeil and qTelescope use the built in function NullSpace for
computing the null space of the corresponding matrix in LinSolve. Default
value for EquationSolver is Automatic, which invokes the null space
algorithm provided with the qZeil package.
Note that for users at RISC, EquationSolver -> CNullSpace invokes an
improved version of Erhard Aichinger's CNullSpace, a null space algorithm
implemented in C requiring SACLIB. For this, one has to read in < {int1, int2}, qZeil computes extended *homogeneous*
recurrences of the form
Sigma[0] SUMX[n,P] + Sigma[1] SUMX[n-1,P] + ... +
Sigma[ord] SUMX[n-ord,P] = 0,
where
SUMX[n-j,P] := Sum[F(n-j,k) * P(k), k]
for a polynomial P(k) of maximal degree int1 and not depending on q^n.
int2 is an upper bound for the degree of the Sigma[j] w.r.t. q^n.
Note that this option implicitly changes the summation range to the set
of all integers (you will get a warning about this), so no inhomogeneous
recurrences can be dealt with.
Remark: This is a non-linear problem which seems to be rather impossible
for Mathematica even for small examples. Thus, the system of
equations is solved very efficiently with Maple. For this, the
global variable MapleCall has to be assigned a string specifying
the command to invoke Maple (the command line version) redirecting
the input from the file "MapleIn", for instance, under Windows 95
MapleCall = "cmaple -q < True, qZeil only
computes
Sum[Sigma[i] F(n-i,k), {i, 0, order}]
in the form
F(n,k) Sum[Sigma[i] F(n-i,k) / F(n,k), {i, 0, order}]
as a rational function multiple of F(n,k) with undetermined Sigma[i]. This
feature, for instance, allows to perform and check all steps of the qWZ-
method "by hand": Call qZeil with order 1 and OnlySummand -> True, replace
Sigma[0] and Sigma[1] by 1 and -1, resp., and finally run qTelescope on
the output (note that this might cause problems if the rational function
is "large", because factorization in qTelescope fails then).
- New option MagicFactor applying Paule's method of creative symmetrizing
for decreasing the order of the recurrence in qZeil. Let f = f(k) denote
a non-constant linear integer function of k with the property that
Sum[F(n,k), {k, low, upp}] = Sum[F(n,f(k)), {k, low, upp}].
Typical examples for f are -k, -k-1, -k+1, n-k, 2n-k, etc. Then we have
Sum[F(n,k), k] = (Sum[F(n,k), k] + Sum[F(n,f(k)), k]) / 2
= Sum[F(n,k) (1 + F(n,f(k)) / F(n,k)) / 2, k]
=: Sum[F(n,k) MF(n,k), k]
for some function MF(n,k) in q^n and q^k. Now, if MF(n,k) satisfies the
input restrictions for qZeil or qTelescope, option MagicFactor -> f
automatically multiplies the summand with this magic factor MF. See
the example notebook for various applications.
- In qTelescope all parameters of the form q^par[i], for integer parameters
par[i] appearing only linearly, are (temporarily) replaced by subs[i].
This results in dramatic speedup for examples involving parameters of
this type, as for instance Rahman, Verma [1993, (3.*)].
- Dualization now also works correctly if, for instance, qfac[q, q, k] is
given as (1 - q) * qfac[q^2, q, k-1], etc., thanks to a new rewrite rule
for such terms.
- The pole checking feature now also works with qZeil if the summation
bounds are explicitly given. Thus, the output of qZeil has changed in
the same way as described for qTelescope 1.5 below.
Version 1.6 (finished 11-18-96)
***********
- After a dual pair {F'(n,k), G'(n,k)} has been computed by the program,
calling
DualId[{k, low, upp}, n]
evaluates SUM' := Sum[F', {k, low, upp}] provided that SUM' is constant,
i.e., not depending on n. DualId uses the value of the (global) variable
DualPair. Note that all elements c_i of intconst (beside n) are now
automatically replaced by -c_i - 1 to preserve their non-negativity under
shadowing.
- The computation of companion identities has been improved. In particular,
the computation of Limit[F(n,k), n->Infinity] no longer fails in so many
instances where the limit actually exists and is finite. As with dual
identities, this improvement is due to the application of several
transformation rules to the summand.
Moreover, the notation (k >= 0) has been changed to the corresponding
Mathematica expression If[k >= 0, 1, 0]. Plugging in concrete values for
k in CompId now makes sense giving 1 or 0 instead of True or False.
- Simplification of q-hypergeometric expressions has been corrected and
improved. In particular, poles found by qTelescope may influence certain
non-negativity conditions of integer parameters, which is of fundamental
importance for 0-recognition.
Example: Assume that n is an element of intconst, i.e., n is a non-
negative integer. If there is a pole for n = 0, we may conclude
that n >= 1. Thus, for instance, qfac[q^(1-n),q,n] = 0 for all n.
A very nice application of this feature is a special case of Gasper and
Rahman [1990b, (II.27)], which no longer needs the transformation n->n+4.
Note that in case of more than ONE solution, the new conditions are
applied to all solutions which might be incorrect.
Furthermore, simplification now also works for terms of the form a + b,
a == b, and Sum[a, ...]. Thus, special cases of dual identities etc.
can be simplified easily by applying qSimplify. By adding some additional
rules for cancelling qfac's, simplification has become slightly slower
but much more powerful.
Version 1.5 (finished 08-10-96)
***********
- ToqHyper[rec] converts the recurrence rec into valid input for
Petkovsek's qHyper in terms of SUM[N] := SUM[q^n] where n is the
recurrence variable.
- Options are now supported for qZeil and qTelescope. New syntax:
qZeil[F, {k, low, upp}, n, ord, , , ..., ]
qTelescope[F, {k, low, upp}, , , ..., ]
where the opt_i are options from the following list:
FindAlphaBeta with FindAlphaBeta -> True, qZeil and qTelescope make
suggestions for all possible choices of alpha and beta
such that there possibly exists a solution for
F * q^(alpha Binomial[k,2] + beta k).
The result should be interpreted in the following way:
For all integers NOT being alpha-beta-candidates there
actually does not exist a solution. However, not all
candidates necessarily yield a solution. Note that there
are always only finitely many alpha-candidates, but
sometimes it is not possible to find any restriction on
beta (actually many --- I conjecture ALL --- identities
find a solution for either no beta or infinitely many
beta's).
Remark: In qZeil version 1.5 this option was originally
called FindAlpha only working for alpha-candidates.
The change to FindAlphaBeta was actually done in
version 1.8.
PolyMult with PolyMult -> int (int a non-negative integer),
qTelescope computes all polynomial multipliers of maximal
degree int which make the input *Gosper* summable.
Default value for int is 0.
Shadow with Shadow -> rat (rat a rational number), the default
shadowing strategy for computing dual identities in qZeil
is changed as following:
The shadowing rule is applied to all qfac-terms except
qfac[q, q, a n + b k + c] for which a + rat b = 0 but
not a = 0 = b.
Default value for rat is 1 (as suggested by Wilf and
Zeilberger).
Example: If the summand contains the factor qfac[q^(-2n),q,k],
it turns out that qZeil should be called with
Shadow -> 2 (otherwise the dual qWZ-pair is not
well-defined).
More details about the theoretic background behind this
strategy can be found in my PhD Thesis.
- The computation of dual identities has been corrected and improved. The
shadowing rule for qfac[A, q, a n + b k + c] only holds if A is free of
n and k. Thus, transformation rules are applied to achieve this form.
- Finding poles of the solution function(s) in qTelescope now works
correctly if there is more than one solution (cf. option PolyMult).
As a consequence, the output of qTelescope has changed to
{ {Sum[F_1, {k, low, upp}] == cf_1, polelist_1},
{Sum[F_2, {k, low, upp}] == cf_2, polelist_2},
... ,
{Sum[F_m, {k, low, upp}] == cf_m, polelist_m} }.
If m = 1 or polelist_i = {} for some 1 <= i <= m, then some of the nested
lists are flattened out.
------------
| Known bugs |
------------
- If the summand F(n,k) for qZeil is not well-defined for all non-negative
integers n and all integers k from the summation range, or actually needs
some sophisticated limit considerations, evaluation might fail. The same
holds true for the summand F(k) for qTelescope.
- The q-binomial coefficient qBinomial[a, b, q] might cause problems if
a is negative.
------------------
| qZeil on the Web |
------------------
The qZeil homepage is located at
http://www.risc.uni-linz.ac.at/research/combinat/risc/software/qZeil/
To get the password send an email to me. The password will be given for
free to all researchers and non-commercial users.
=======================================================================
Axel Riese
Research Institute for Symbolic Computation
J. Kepler University Linz Tel: +43 (0)732 2468 9966
Altenbergerstrasse 69 Fax: +43 (0)732 2468 9930
A-4040 Linz mailto:Axel.Riese@risc.uni-linz.ac.at
Austria http://www.risc.uni-linz.ac.at/people/ariese/home/
=======================================================================