slp - a C++ classlib (a prototype for straight–line programs)

Klemens Hägele^{1}

Departamento de Matematicas, Estadistica y Computacion

         haegele@hilbert.matesco.unican.es

Facultad de Ciencias Universidad de Cantabria 39071 Santander, Espana

1: Research was partially supported by the following Spanish grants : DGCYT PB92–0498–C02–01 and PB93–0472–C02–02

Contents

1 Straight–line programs 1 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Design of the classlib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Improvements and things still missing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 User’s Guide 6 2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Quickstart: Sample programs using the classlib . . . . . . . . . . . . . . . . . . . . . . . 8

Thanks go to:

• the GNU project for their good software,

• the LEDA team for an excellent classlib and their TeX and awk macros,

• Bonifacio Castaño for fruitful discussions,

• Klaus-Peter Nischke for help with the parser,

• Daciana Bochis for the software support on our Sun Sparc,

• and last but not least: Emilio for the coffee.

Chapter 1

Straight–line programs

1.1 Introduction

An introduction to algebraic complexity theory and the history of addition chains, computation sequences and straight–line programs can be found in Chapter 11 of the ”Handbook of Theoretical Computer Sciences” [35] and the references cited there. There have been many publications investigating complexity issues in various topics using straight–line programs or related notions, see the survey articles [11], [32], [34], [35], and more specifically on elimination theory, [30]. Straight–line programs, initially being just a model for computational complexity, proved as well to be a valuable practical tool. For some practical results consider the following (of course uncomplete) list of topics and references (and the references given therein):

• Evaluation: [4], [19], [22], [24]

• Interpolation: [17], [39], [40]

• Identity test: [10], [12], [13], [33]

• Factoring, polynomial GCD: [15], [16], [36], [37]

• Derivation: [2], [4], [26], [18]

• Integration: [23]

• Determinant: [1], [3], [9]

• Matrix rank: [14]. [27] and the following implementations:

• DAGWOOD in Macsyma LISP, [5]

• Toolkit, in C, [31]

• TERA - in PASCAL, [28], presented at TERA’96, see [29]

• zerotest - in C++ , presented at TERA’96, see [38] The following papers represent a step by step framework of theoretical and algorithmical advances, [20], [8], [7], [6] (list of papers contributing to the algorithm) the one presented at MEGA’96 ([6]) being presently the last one.

The algorithm for geometric elimination described therein makes heavy use of straight–line program techniques developped and described in the anterior papers. The long-term aim is to implement this algorithm, starting with a prototype to collect the necessary experience with the practical issues of designing and implementing such a complex algorithm.

Encouraged by the promising implementation results obtained by M. Aldaz and B. Castaño as presented at TERA’96, which already improved on the admissible complexity of matrix computations compared with current computer algebra packages such as maple, the idea was to initiate an open discussion and cooperation for the development of more advanced algorithms based on straight–line program structures contributing step by step to the main framework of the elimination algorithm [6].

The present C++ classlib slp is thought as a first small step in this direction.

Main features

i) First of all, the classlib slp is based on LEDA for the efficient implementation of the basic abstract data types (lists, arrays, hash tables). LEDA is a C++ library for efficient datastructures and algorithms developped by the LEDA team at the Max-Planck-Institut für Informatik, Saarbrücken, Germany. It can be used with almost any C++ compiler that supports templates. LEDA is available by anonymous ftp from ftp.mpi-sb.mpg.de in directory /pub/LEDA. The distribution contains all sources, installation instructions, a technical report, and the user manual.

ii) System Requirements: to use the classlib slp for the development of your own algorithms based on straight–line program data structures, you will need a C++ programming environment with editor, GNU flex, bison, gawk and L^{A}TEX for the documentation. This is found on most current workstations and UNIX machines, for example, any computer system running linux will do just perfectly fine.

iii) The design of the classlib slp gives a reasonable set of operations for the new data type slp, providing both overloaded operator and procedural versions of the basic arithmetic operations and as such should be usable within a C++ program in a fairly intuitive way.

iv) The classlib slp is in such conditions that it is possible to start building algorithms for straight–line programs based upon it. The data encapsulation and implementation hiding methods applied should be strong enough to allow for flexible code which can be re-used (with just minor modifications) with any improved version of slp.

v) For online assistence, use tman <headerfile> to extract and typeset the corresponding man pages for the file, tdoc <sourcefile> for any additional notes that might be available.

vi) The source code has detailed comments in all parts and the full documentation is incorporated into the source files (special thanks go to the LEDA team for their smart TeX and awk macros).

vii) The present classlib slp does not pretend to be the final solution of the design and implementation problem for the abstract data type straight–line program. It is rather thought as a first experimental stage within a larger project and as such should help to find out about the critical points for a future extension to a more suitable design. To encourage this, the documentation section of this manual includes notes on the various problems faced and decisions taken during the initial design and implementation phases.

1.2 Design of the classlib

1. Definition of a straight–line program

Most literature defines the term ’straight–line program’ either in the following or a very similar way ([?] list of books and papers):

1. Definition

Let D be a domain and T_{1}, …, T_{n} indeterminates over D. A straight-line program Γ over D is a computation sequence of the form (x_{0}, …, x_{L}), where:

• x_{0} := 1, and

• x_{i} = x_{i_{1}} op x_{i_{2}}, for 1 ≤ i ≤ L, 0 ≤ i_{1}, i_{2} < i and op ∈ {+, −, ∗, /}, where

• some nodes x_{L_{1}}, …, x_{L_{m}} are specified as output nodes.

The integer L is called the length of the straight–line program Γ.

If we restrict the admissible operations to {+, −, ∗}, the x_{i} will be polynomials of the ring D[T_{1}, …, T_{n}]. Γ is then called a division free straight–line program over D. If divisions are permitted, the x_{i} are rational functions of D(T_{1}, …, T_{n}).

2. Representation forms for straight–line programs

An important step for the design of the classlib is the identification of the possible divisions into self-contained structures of the a priori unstructured and rather formal concept of a straight–line program, thus deriving an abstract data type slp from the definition (1.2.

The divisions made here, namely those of the graph-oriented approach are quite natural and can be found in [?] (more papers), [20] and [28] for example. There are basically two ways of looking at a straight–line program and describing it: the ’straight–line’ or ’vector’ (short VEC) and the ’directed acyclic graph’ (short DAG) oriented approach. From the definition 1.2, the vector representation VEC is pretty obvious: The vector, indexed by the number i of the operation (this is a linear function) contains in each entry VEC[i] all the information neccessary to describe the operation.

The other representation form, DAG, even if not at first glimpse, is the more intuitive one (see [21], [25]): One can interpret the operations as nodes of a directed graph, defining the relation for the connection between the nodes as ’uses as operand’. Using the standard notion of depth of a node in a directed acyclic graph the nodes are grouped according to their depth r (i.e. the maximum length of any path from the particular node to any preceeding node without operands). Then a random order is fixed for all nodes of the same depth r. In this way, one can assign to each node (representing a operation) a rank s at a depth level r, thus yielding a unique position DAG(r, s).

The two representation forms VEC and DAG are related by a bijective correspondance between the vector index i and the graph node position (r, s). In the case of a DAG representation of the straight–line program, this means basically summing over the set of slpnodes of inferior depth plus adding the rank of the slpnode itself to obtain the slpnode’s vector index.

3. From representation form to data abstraction and class design

The main data structure for the abstract data type slp is the directed acyclic graph representation form of a straight–line program, introducing a separation of the data into nodes, sets of nodes at a fixed depth and the union of such sets. In the next step, suitable datastructures for the representation of each of these had to be chosen. Considering the inherent time-space trade-off of the various possible forms of implementing the necessary structures, the choices were made among the basic abstract data types provided by the C++ classlib LEDA and new classes derived (slpnode, slpnodelist, vecnode, vecnodearray, see p. ??ff) thus forming together with a few auxilliary classes, the main class slp, see p. ??ff.

4. The user interface

A primary goal for the development of the classlib was the idea of data encapsulation and structure hiding, to obtain a user interface (i.e. the way, the classlib can be used by external C++ code) which should be:

• as simple as possible, hiding all the internal details from the user, but not impeding or complicating any operations,

• close to the usual handling of standard data structures such as integers,

• flexible for expansion (as it is already clear at the time of writing that the classlib will have to be extended to cover the requirements for some (still missing) basic algorithms such as Berkowitz [3]).

In this sense, the possibilities provided by the C++ language were used to build a classlib which should be rather intuitive to use.

1.3 Improvements and things still missing

The following parts are meant to be improved soon:

• the zero-equivalence test is zero, see ??,

• the hash collision handling for monomials, see ??,

• the basic matrix arithmetics, see ??,

• the evaluation algorithm used, see ??,

• a function to compute the result of a slp, given a bound on its binary size, using multimodular arithmetic and the chinese remainder theorem. This overcomes the problem of exploding binary size of intermediate expressions in a standard representation model.

And here a (of course uncomplete) list of things being considered for extension:

• advanced matrix functions, linear algebra, determinant (Berkowitz), see [3]

• support of coordinate changes in a generic way in the slp structure,

• support of composition of slps (slps taking slps as input structures),

• support of meta-slp’s (slps generated by formulae or other slps)

• support of indexed variables

• partial specialization and symbolic evaluation yielding a slp as result

• destructive versions of the arithmetic operations, see ??.

• operations that recover a standard monomial representation of polynomials in straight–line program representation, see [17] on sparse monomial interpolation techniques, to obtain

• an import/export function for code readable by a computer algebra package (maple).

Note, that the classlib slp is not meant to be extended to a fully-grown computer algebra package, but rather kept as a small, but complete set of basic functionality for straight–line programs. Any further algorithms based on slp (such as possible implementations of the algorithms mentioned in the literature index) should be kept separately.

Chapter 2

User’s Guide

This is the User’s Guide for the classlib slp. This part is not a complete reference for all functions available within the classlib, but just a condensed presentation of some of the possibilities you will have writing C++ code using the classlib. A complete reference is given in the documentation part, page ??ff and further notes and comments are found in the implementation part, page ??ff.

2.1 Overview

1. Using the classlib inside your programs

Just put a #include "slp.h" line in your main program, and link it with -lslp. See the sample programs main.cc, demo1.cc, demo2.cc and the small test programs in the src/demo/ directory.

2. Declaration

To declare a variable of type slp in your program, use:

slp A;  for a generic slp A,
slp V(n);  for a vector V of n elements,
slp M(n,m);  for a matrix M of size n × m,
slp F("X^{2} + X + 3"); for a polynomial F = X^{2} + X + 3 and
slp B(A);  to declare and assign B to be a a copy of A.

3. Assigning values

In the next step, you will want to assign values or polynomials to the structures just created, try writing:

A = 17;
B = "2*X*Y + 3*X*Z"; or equivalently
B.assign(0,0,"2*X*Y + 3*X*Z");
for (int i=0;i<n;n++) V.assign(i,0,1990+i);
for (int i=0;i<n;n++)  for (int j=0;j<m;m++) M.assign(i,j,i*10+j*100);

which can be used as well to assign polynomials to the entries of a matrix slp. By convention, lower case letters are used for parameters, upper case letters for variables. Multivariate polynomials with parameters are possible, too:

slp G = "3*X*Y+a*X+b+19*c*Z+7";

4. Arithmetic expressions

The arithmetic operations +, -, *, +=, -=, *=, ++, --, assignment based operators +=, -=, *= and exponentation ^together with the ==, != comparators are available for writing arithmetic expressions involving all combinations of straight–line programs and int variables in the standard way.

A = A + 4; // A = 17 + 4

F *= 9; // F = (X^{2} + X + 3) ∗ 9

A = A^100; // A = 21^{100}

5. Evaluation of the results

To perform evaluation on the slp F, do: F.Specialize('X',3); (specialize all variables) then F.Evaluate(); and then print the result:

cout << (integer) F << endl;

Note, that, if you don’t cast F to (long) or integer, the internal structure of the slp will be printed. You can specialize the parameters (’a’..’z’) in the same way as the variables (’A’..’Z’). If the represented results become very big, one should use modular evaluation: F.Evaluate(7); evaluated the slp mod 7, and cout << (long) F << endl; returns the result as a long value.

6. Printing information

Use A.Info(int info); to print out statistics on the slp A. The following tokens for info will give information on:

INFOSLP  the number of slpnodes, variables, parameters, constants,
INFOVEC  the vector format of the slp,
INFOVAL  the current values of the result nodes,
INFOMEM  the current overall LEDA memory manager status,
INFOVARPAR the names and positions of the VAR, PAR, NUM nodes,
INFORESULT the positions of the result nodes,
INFOCOMPLEX the length and depth of the slp, the nonscalar complexity of the result nodes,
INFODEFAULT a default value for a combination of the above options.

7. I/O

You can use A.read(instream) or A.print(outstream) as well as

cout << A << endl; to read or write from files or other streams.

8. Advanced programming

There is a set of boolean operations to inquire about the nature of a given slp:

is empty(), is var(), is univar(), is multivar(), is single(), is vector(),
is matrix(), is const(), is poly(), is univarpoly(), is multivarpoly()

which do just what you would expect them to do. For more details on the more intricate functions taking parameters refer to the documentation part, page ??ff.

2.2 Quickstart: Sample programs using the classlib

1. Using numbers

#include "slp.h"
int main(void) {
print_statistics();
slp A;
A = 2;
A = A^100000;
A = A^100000;
A -= A;
if (A==0) { cout << "A is zero" << endl; }
else { cout << "A is not zero" << endl; }
print_statistics();
return 0;
}  // end main

2. Using polynomials

#include "slp.h"
int main(void) {
print_statistics();
slp F = "a*X+b*Y+c*Z";
slp G = "2*X-3*Y+5*Z";
slp H = F*G;
H  = H^1000000;
H  = H^1000000;
H -= H;
H.Specialize('a',2);
H.Specialize('b',-3);
H.Specialize('c',5);
H.Specialize('X',7);
H.Specialize('Y',11);
H.Specialize('Z',13);
if (H == 0) { cout << "H is zero" << endl; }
else     { cout << "H is not zero" << endl; }
print_statistics();
return 0;
}  // end main

Bibliography

[1] J. Abdeljoued. Sur l’algorithm de berkowitz pour le calcul du determinant dans un anneau conmutatif arbitraire. preprint, Universite de Franche Compte, Besancon, 1995.

[2] W. Baur and V. Strassen. The complexity of partial derivatives. Theo. Comp. Sci., 22:317–330, 1983.

[3] S. J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Information Processing Letters, 18:147–150, 1984.

[4] J. Carnicer and M. Gasca. Evaluation of multivariate polynomials and their derivatives. Math. Comp., 54(189):231–243, 1990.

[5] T. S. Freeman, G. M. Imirzian, E. Kaltofen, and L. Yagati. Dagwood - a system for manipulating polynomials given by straight-line programs. ACM Transactions on Mathematical Software, 14(3):218– 240, September 1988.

[6] M. Giusti, K. Hägele, J. Heintz, J. E. Morais, J. L. Monta na, and L. M. Pardo. Lower bounds for diophantine approximation. In Proceedings of MEGA’96, 1996.

[7] M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, and L. M. Pardo. Straight-line programs in geometric elimination theory. In Journal of Pure and Applied Algebra, 1995.

[8] M. Giusti, J. Heintz, J. E. Morais, and L. M. Pardo. When polynomial equation systems can be solved fast ? In AAECC-11, LNCS 948, pages 205–231. Springer, 1995.

[9] A. Grosso, N. Herrera, G. Matera, M. E. Stefanoni, and J. M. Turull. Un algoritmo para el calculo del rango de matrices enteras en espacio polilogaritmico. In Proc. 25th JAIIO, 1996.

[10] K. Hägele and J. L. Monta na. Polynomial random test for the equivalence problem of integers given by arithmetic circuits. May 1995.

[11] J. Heintz. On the computational complexity of polynomials and bilinear mappings. a survey. In Proc. AAECC-5, LNCS 356, pages 269–300. Springer, 1989.

[12] O. H. Ibarra and B. S. Leininger. On the simplification and equivalence problems for straight-line programs. Journal of the ACM, 30(3):641–656, July 1983.

[13] O. H. Ibarra and S. Moran. Equivalence of straight-line programs. Journal of the ACM, 30:217–228, 1983.

[14] O. H. Ibarra, S. Moran, and L. E. Rosier. Probabilistic algorithms and straight-line programs for some rank decision problems. Information Processing Letters, 12(5):227–232, 1981.

[15] E. Kaltofen. Computing with polynomials given by straight-line programs I: Greatest common divisors. In Proceedings of the 17th Ann. ACM Symposium on Theory of Computing (Providence, RI), pages 131–142, New York, 1985. ACM, ACM Press.

[16] E. Kaltofen and B. Trager. Computing with polynomials given by black boxes for their evaluations: Greatest common divisor, factorization, separation of numerators and denominators. In Proceedings of the 29th Ann. IEEE Symposium on Foundations of Computer Science (White Plains, NY, October 24-26, 1988), pages 296–305. IEEE, IEEE, 1988.

[17] E. Kaltofen and L. Yagati. Improved sparse multivariate polynomial interpolation algorithm. In P. Gianni, editor, Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC ’88) (Rome, Italy, July 1988), LNCS 358, pages 467–474, Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong, 1989. Springer-Verlag.

[18] Erich Kaltofen and Michael F. Singer. Size efficient parallel algebraic circuits for partial derivatives. Technical Report No. 90-32, Department of Computer Science, Rensselaer Polytechnic Institute, Troy, N.Y., October 1990.

[19] D. E. Knuth. The Art of Computer Programming: Semi-numerical Algorithms, volume 2. Addison-Wesley, 1981.

[20] T. Krick and L. M. Pardo. Une approche informatique pour l’ approximation diophantienne. C. R. Acad. Sci. Paris, 318(1):407–412, 1994.

[21] T. Krick and L. M. Pardo. A computational method for diophantine approximation, 1996.

[22] R. Lipton and L. Stockmeyer. Evaluation of polynomials with superpreconditioning. In Proc. 8. ACM STOC, pages 174–180, 1976.

[23] G. Matera. Integration of multivariate rational functions given by straight-line programs. preprint 17 pages, AAECC-11, 1995.

[24] Gary L. Miller, Vijaya Ramachandran, and Erich Kaltofen. Efficient parallel evaluation of straight-line code and arithmetic circuits. SIAM J. Comput., 17:687–695, 1988.

[25] J. L. Montana and Luis M. Pardo. Lower bounds for arithmetic networks. In AAECC-4, AAECC, pages 1–24. Springer, 1993.

[26] J. Morgenstern. How to compute fast a function an all its derivatives. Prepublication No. 49, Universite de Nice, 1984.

[27] Ketan Mulmuley. A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. Combinatorica, 7(1):101–104, 1987.

[28] B. Casta no, J. LLovet, and R. Martinez. An evaluation algorithm for univariate polynomials given by straight–line programs. preprint, Universidad de Alcala de Henares, Spain, 1995.

[29] B. Casta no, J. LLovet, and R. Martinez. Polynomials, matrices and algorithms with straight–line programs. In L.M. Pardo, editor, Proceedings of TERA’96, pages 12–14, Santander, Spain, April 1996. Universidad de Cantabria, Facultad de Ciencias.

[30] Luis M. Pardo. How lower and upper complexity bounds meet in elimination theory. AAECC-11, 1995.

[31] A. Rege and J. Canny. A toolkit for algebra and geometry. preprint 12 pages, submitted to ISAAC 95, 1995.

[32] Arnold Schönhage. Equation solving in terms of computational complexity. ICM 86, 3:40, 1986.

[33] J. T. Schwartz. Fast probabilistic algorithms for the verification of polynomial identities. J. of the ACM, 27:701–717, 1980.

[34] V. Strassen. Algebraische berechnungskomplexität. In Perspectives in Mathematics, pages 509–550. Birkhäuser, 1984.

[35] V. Strassen. Algebraic complexity theory. In Handbook of Theoretical Computer Science, chapter 11, pages 634–671. Elsevier, 1990.

[36] J. von zur Gathen and E. Kaltofen. Factoring sparse multivariate polynomials. J. Comput. Syst. Sci., 31(2):265–287, October 1985.

[37] J. von zur Gathen and V. Shoup. Computing frobenius maps and factoring polynomials. Computational Complexity, 2:187–224, 1992.

[38] M. Aldaz Zaragüeta. Implementacion de numeros racionales mediante la estructura de datos straight–line program. In L. M. Pardo, editor, Proceedings of TERA’96, page 10, Santander, Spain, April 1996. Universidad de Cantabria, Facultad de Ciencias.

[39] R. Zippel. Probabilistic algorithms for sparse polynomials. In Proc. EUROSAM’ 79, volume 72 of LNCS, pages 216–226, 1979.

[40] R. Zippel. Interpolating polynomials from their values. J. Symbol. Comput., 9:375–403, 1990.