acs@csri.toronto.edu (Alvin Chia-Hua Shih) (05/22/91)
I'm currently playing around with some polynomials that appear in a doubly-recursive relation (I may post details about it if I get too frustrated). I have been using Maple, but it is running out of swap space. Is there a package out there that will allow me to operate on polynomials with rational coefficients without exceeding system limits? I need some degree of programmability (a simple language or an interface to C, Lisp, Prolog, etc.) to compute the recursive relation, and ideally, something that collects terms in a sensible manner (but I can make Maple do that if necessary). Thanks. (Or if someone is running a symbolic math package on a *huge* system with cycles to burn, I can give you more details and you can run it! :-)
spit@fys.ruu.nl (Werenfried Spit) (05/23/91)
> In sci.math.symbolic you write: > > I'm currently playing around with some polynomials that appear in a > doubly-recursive relation (I may post details about it if I get too > frustrated). I have been using Maple, but it is running out of swap > space. > > Is there a package out there that will allow me to operate on polynomials > with rational coefficients without exceeding system limits? I need some > degree of programmability (a simple language or an interface to C, Lisp, > Prolog, etc.) to compute the recursive relation, and ideally, something > that collects terms in a sensible manner (but I can make Maple do that > if necessary). > Thanks. > (Or if someone is running a symbolic math package on a *huge* system > with cycles to burn, I can give you more details and you can run it! :-) > How about good old REDUCE? Seriously; I have spent some time in integrating Gaussian like functions symbolically; this turns out to be manipulation of polynomials wiith arbitrary coefficients. I tried it with Reduce, with Maple and with Form. Although I got working algorithms inall 3 languages, in Form things broke down when I used polynomials in more than 3 or 4 variables (I then had to put in thousands of simplifying relations by hand....); Maple was not able to handle large expressions. Reduce was. It's available for all kinds of machines (Atari ST, DEC stations, SUN stations, VAXes, ..) It's written in LISP (so you might use plain LISP commands) It's programmable (Pascal style);and can be used interactively. It takes some experience to get everything out of it. There are interfaces to Fortran and TeX. You can get problems with memory if you are careless, but most of this can be avoided by making use of files for temporarily storing expressions. Following is part of a report I wrote:(in LaTeX) \section{Symbolic Manipulation Programmes}\label{app:reduce} Much of the actual calculations described in ths thesis were performed with help of algebraic manipulation programmes. Most of the problems were straightforwardly programmed in \reduce\. (See \cite{Hear68} and \cite{Hear84}). From a technical point of view the implementation of eq.~(\ref{eq:ffspatdef}) and (\ref{eq:defrhop}) \begin{eqnarray} {\cal F}(\vek{q}) & = & \bra{\Psi(\vek{k}_1,\dots,\vek{k}_{3A})}\sum_i\int \df{\vek{k}_{i}}\df{\vek{k}_{i}'} b_{i}^{\dagger}(\vek{k}_{i} + \vek{q}) b_{i}(\vek{k}_{i}') \ket{\Psi(\vek{k}_1',\dots,\vek{k}_{3A}')}, \\ \rho(\vek{p}) & = & \bra{\Psi_A} \sum_{i=1}^{3A} \delta^{(3)}(\vek{k}_i - \vek{p})\ket{\Psi_A}. \end{eqnarray} demanded most care. In a two-nucleon system this is an 18-dimensional integral. Due to the quark exchange operator the integral can not be seperated. This causes the actual computation to be quite substantial. The main routine involved, integrating products of polynomials and Gaussians in arbitrary dimensions, is set up as follows: \begin{itemize} \item Let $P(\vek{x})$ be a polynomial of arbitrary order $p$ in $\vek{x} = (x_1,x_2,\dots,x_n)$. \\ Let $G(\vek{x}) = \exp\left[ - \sum_{ij} \alpha_{ij}x_i x_j \right]$ be a generalized Gaussian function. The integrand is the product of $P$ and $G$. \item Define a coordinate transformation such that $G$ is diagonalized: \begin{multieqn} \tilde{G}(\vek{\tilde{x}}) & = & \exp\left[ - \sum_i \tilde{x}_i^2 \right] = G(\vek{x})\\ \vek{\tilde{x}} & = & S \vek{x} \\ S \cdot S^T & = & \left( \alpha \right) \end{multieqn} S can be found recursively. \item Apply this transformation to the polynomial $P$: \begin{equation} P(\vek{x}) = P(S^{-1}\vek{\tilde{x}}) = \tilde{P}(\vek{\tilde{x}}) \end{equation} \item Now integrate over $(\tilde{x}_1,\dots,\tilde{x}_n)$ by splitting the polynomial in terms; for each term the integral can be factorized. The integration is performed by pattern recognition: for each factor in each term of the integrand the corresponding factor in the solution is calculated. \end{itemize} We implemented variations of this algoritm in \reduce, {\sc maple} and {\sc form}. Though {\sc form} is especially suited to handle large expressions, in this case its weak abilities in polynomial manipulation were a large disadvantage. It was not possible within reasonable limits of computing time and programming effort to let {\sc form} perform the necessary reductions of the integrand. {\sc Maple} has a number of sophisticated integration routines, but lacks brute force and polynomial manipulation abilities. In the end \reduce\ turned out to be best suited for the problem. To compare the performance of different machines, and get an indication of the necessary computing time, we performed an benchmark calculation. For this purpose we used the basic routines to compute: \begin{equation} \int\dv{x} \left( \sum_{i=1}^n \beta_i x_i^p \right) \exp\left[\sum_{j \leq i}^{n} \alpha_{ij} x_i x_j \right] \end{equation} for various values of $n$ and $p$. The results of this test are listed in table~\ref{tab:performance}. (It should be noted that for te very small jobs relatively much time is spent on {\sc io}-operations). On the {\sc vax}-es \reduce~3.0 was used with an internal memory space of 4~Mbyte, on the Atari~ST (2~Mbyte {\sc ram}) \reduce~0.9; on the other machines \reduce~3.3. The recorded times were those provided by the \reduce\ internal time keeping mechanism. The comparison between the two {\sc sun}s shows that a fair amount of time is spent in swapping and comparable memory operations. \begin{table}[hb]\begin{centering} \begin{tabular}{|l||rrr|rrr|rrr||}\hline $n$ & \multicolumn{3}{|c|}{1} & \multicolumn{3}{|c|}{2} & \multicolumn{3}{|c||}{4} \\ \hline $p$ & 0 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & 2 \\ \hline\hline Atari ST & 5.35 & 8.07 & 14.28 & 5.70 &11.87 &75.26 & 8.73 & 26.00 & 527.29 \\ VAX 11/785 & 0.83 & 1.46 & 3.36 & 0.97 & 3.08 &23.78 & 1.72 & 8.21 & 176.52 \\ VAX 3500 & 0.57 & 1.00 & 2.17 & 0.60 & 1.91 &15.79 & 1.17 & 5.16 & 107.45 \\ SUN 4/280 (32 Mb)& 0.20 & 0.29 & 0.49 & 0.54 & 0.85 & 3.35 & 17.07 & 12.87 & 571.20 \\ SUN 4/280 (64 Mb)& 0.12 & 0.19 & 0.29 & 0.36 & 0.46 & 6.68 & 8.99 & 6.68 & 250.31 \\ DEC 2100 & 0.18 & 0.18 & 0.34 & 0.40 & 0.64 & 2.22 & 9.94 & 7.72 & 293.84 \\ DEC 3100 & 0.14 & 0.14 & 0.24 & 0.26 & 0.42 & 1.60 & 7.18 & 5.38 & 208.20 \\ DEC 5000 & 0.06 & 0.08 & 0.16 & 0.18 & 0.26 & 0.98 & 4.62 & 3.40 & 125.40 \\ DEC 5500 & 0.02 & 0.06 & 0.10 & 0.12 & 0.20 & 0.80 & 3.80 & 2.78 & 104.38 \\ \hline \end{tabular} \caption{Performance of the \reduce-routine {\tt gaussint} in {\sc cpu}-seconds on various machines, as function of the integration-dimension $n$ and the degree of the polynomial $p$.}\end{centering} \label{tab:performance}.\end{table} -------------------------------------------------------------------- Werenfried Spit R.J. v.d. Graafflaboratorium +31-(0)30-53-2330 Postbus 80.000 3508 TA Utrecht spit@fys.ruu.nl The Netherlands spit@hutruu51.bitnet --------------------------------------------------------------------
gjc@mitech.com (05/23/91)
In article <1991May23.142627.5912@fys.ruu.nl>, spit@fys.ruu.nl (Werenfried Spit) writes: >> In sci.math.symbolic you write: >> >> I'm currently playing around with some polynomials that appear in a >> doubly-recursive relation (I may post details about it if I get too >> frustrated). I have been using Maple, but it is running out of swap >> space. >> > How about good old REDUCE? > Seriously; I have spent some time in integrating Gaussian like > functions symbolically; this turns out to be manipulation of > polynomials with arbitrary coefficients. I tried it with > Reduce, with Maple and with Form... One reason Maple might be having problems here is that Maple uses a technique that trades off SPACE for TIME by keeping a table of previous computation results. (Maybe there are ways of turning this off?) Another "good old" system that might work here is Macsyma, which has a representation called CRE that makes some polynomial operations quite a bit faster. Also, with Macsyma it is possible to take a user-written procedure and compile it into MACHINE LANGUAGE. *Sometimes* this helps a lot. -gjc