Ralf Hemmecke <[EMAIL PROTECTED]> writes: > Maybe I should learn about the term "executive overview". I am not quiet sure > what "executive" stands for in this phrase. Isn't it a kind of "Introduction" > what Martin wants? So what could possibly be the difference between > "Introduction" and "Executive Overview"?
I'm not quite sure what I wanted some months ago, but I suggest the following: Many contributions consist of several packages, categories and domains, which are somehow related. We should have documentation for users (!!!) that consists of the following: * a short introduction to what the contribution does. An example can be found by clicking "examples" in HyperDoc after browsing "RECLOS". For my guessing package, it would be everything following the section "Using the package" at http://page.axiom-developer.org/zope/mathaction/GuessingFormulasForSequences However, this is a bit longish for my taste. * For every constructor (package, domain, category) a short description what it does. This is the ++ description of the package. * For every operation a short description what it does. Again, this is the ++ description of the package. * Maybe we also need an indroduction that *roughly* describes the mathematical background. This would be everything up to "Using the package" in my Guessing package example and would not contain details. The details should probably go along with the program. This would not contain code, only mathematics. Unfortunately, I do not yet have such a description in pamphlet format for my guessing package. I attach a draft at the end of this mail. Note however, that this is outdated material. I think that the way these bits of documentation are presented in HyperDoc is just perfect. I don't think that it would be too difficult to make ALPROSE do the same. In principle, HyperDoc is a collection of hyperlinked pages -- just as ALPROSE when viewed in a browser and not a dvi-viewer. I.e., we would need to devise a tex4ht interface for ALPROSE that suitable splits the input into a tree of subpages, which can then be accessed by selecting an item from the index... Finally I'd like to stress that I strongly believe that AxiomUI should use the same file format as the documentation. There is no semantic difference between a worksheet and a literate program, except that a worksheet will be interpreted, not compiled. Martin ------------------------------------------------------------------------------- \section{Guessing formulas with an Abelian term} In this section we explain in detail how \verb|guessExpRat| works. The basic idea is to reduce the problem to rational interpolation. Let $s=(s_1,s_2,\dots,s_m)$ be the given list of values, which are elements of a field $\mathbb K$. We then follow the following algorithm for each pair $(k, l)$ with $k+l=m-4$: \begin{itemize} \item Let $y_n=s_n (a+bn)^{-n}$, where $a$ and $b$ are indeterminates. \item Let $p$ be the result of interpolating $(y_1,y_2,\dots,y_{m-3})$ using rational interpolation, where the degree of the numerator is $k$, the degree of the denominator is $l$. \item Let $p_i=\numer\left(p(i+m-3)-y(i+m-3)\right)$ for $i\in\{1,2,3\}$. \end{itemize} It remains to solve the system of the three polynomial equations $p_i = 0$, $i\in\{1,2,3\}$ in the two variables $a$ and $b$. %, such that $a$ and $b$ do not both vanish. This can be done reasonably efficiently using resultants: \begin{itemize} \item Substitute $A-mb$ for $a$ in the three polynomials $p_1$, $p_2$ and $p_3$. \item Let $r_1=\resultant(p_1, p_3, A)$ and $r_2=\resultant(p_2, p_3, A)$. \item Compute $r_3=\gcd(r_1, r_2)$ and calculate the solutions $\tilde A$ of $r_3=0$. For simplicity, we consider only those that are elements of the field. \item For each $\tilde A$ calculate the solutions $\tilde a$ of $p_2(\tilde A, \tilde a)=0$ that satisfy $p_3(\tilde A, \tilde a)=0$, too. \item If such a solution can be found return $\left(\tilde A + \tilde b (n-m)\right)^n p(\tilde a,\tilde b)$ as a formula generating the sequence $s$. \end{itemize} Clearly, the method to solve three polynomial equations in two unknowns just outlined is feasible only when the degree of the polynomials is not too large. The substitution in the first step results in a much lower degree of the polynomial $p_3$, which speeds up the process significantly. Still, for sequences with more than about $7$ terms, it is too slow to be useful. However, numerical evidence supports the following conjecture: \begin{cnj} The order and the degree of the polynomials $r_1$ and $r_2$ is given by the following formulas, where $n=m-i$, $m$ is the number of terms in the given sequence $s$ and $i$ is the degree of the numerator in $p$: \begin{align*} \ord r_1 &= \frac{(n - 1)n(3n^2 - n + 2)}{12}\\ \deg r_1 &= \frac{(n - 1)(3n^3 + (12i + 5)n^2 + (12i^2 + 6i + 20)n - 12i^2 + 12i + 12)}{12}\\ \ord r_2 &= \ord r_1 + \begin{cases} \frac{n(n-1)}{2} &\text{if $i=0$}\\ 0 &\text{otherwise} \end{cases}\\ \deg r_2 &= \deg r_1 + \frac{n^2+(2i+1)n-2i+2}{2}. \end{align*} \end{cnj} Thus, since it appears that the two resultants have very large orders, it makes sense to calculate them by interpolation. For example, the values of $$\resultant(p_1(A=k),p_3(A=k)) k^{-\ord res_1}$$ at $k\in\{1,2,\dots,\deg r_1-\ord r_1+1\}$ determine $r_1$ uniquely. Although this yields a significant speedup for sequences longer than $7$ terms, more work needs to be done to be able to guess more complicated formulas with \verb|guessExpRat|. For example, \begin{verbatim} guessExpRat(n, [(2*n+3)^n*(4*n^3+3*n^2+2*n+1) for n in 1..7], n+->n)$GuessInteger \end{verbatim} takes roughly $13$ seconds, while \begin{verbatim} guessExpRat(n, [(2*n+3)^n*(5*n^4+4*n^3+3*n^2+2*n+1) for n in 1..8], n+->n)$GuessInteger \end{verbatim} takes already $55$ seconds on a {\tt Pentium III} with $900$ megahertz and $512$ Megabytes of memory. Note that care has to be taken if the original sequence contains zeros. In this case it might happen that $(a + bn)$ vanishes for some $n\in\{1,2,\dots,m\}$ and the formula would not be found. In this case we set $z(n)=\prod_{s_i=0} (n-i)$ and $s^\prime$ to the sequence $s$ with the zeros omitted. Then we apply \verb|guessExpRat| to the list $\left(s^\prime_1/z(1), s^\prime_2/z(2),\dots, s^\prime_m/z(m)\right)$ and multiply the results with $z(n)$. \section{Further work} To conclude, we would like to point out future directions: \begin{itemize} \item Obviously, it would be nice to be able to guess formulas of a more general type then those guessed by \verb|guessExpRat|. This would involve finding a fast algorithm that tests whether an overdetermined systems of equations has a solution. Much work has been done in this direction, for starting points see \cite{CoxLittle, EmirisPan2005, Khetan}, but strange enough, the naive elimination algorithm detailed above seems to be the fastest method available currently. \item We did not yet implement a guessing algorithm that covers algebraic differentially finite functions. \item Finally, maybe there are other interesting operators besides $\Delta_n$ and $Q_n$ that could be applied to the sequence. The list of transformations used in \emph{The online encyclopedia of integer sequences} is available, so it might be rewarding to check, which of those extend the class of functions already covered significantly. \end{itemize} _______________________________________________ Axiom-developer mailing list Axiom-developer@nongnu.org http://lists.nongnu.org/mailman/listinfo/axiom-developer
