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

3 Documentation 9 3.1 Nodes of a straight–line program (slpnode) . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2 Lists of slpnodes (slpnodelist) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.3 Nodes of a slp in vector format (vecnode) . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.4 Vector representation of a slp (vecnodearray) . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.5 Testpoints, primenumbers et al (testpoint) . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.6 Straight–line programs (slp) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

4 Additional notes and comments 22 4.1 General notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2 Nodes of a straight–line program (slpnode) . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.3 Lists of nodes (slpnodelist) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.4 Nodes of a slp in vector format (vecnode) . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.5 Overloading operators (slp op) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.6 Hashing Data (slp hash) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.7 Constructing a slp (slp parser) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.8 Joining straight–line programs (slp join) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.9 Evaluation (slp eval) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

5 Tables of classes and functions 27

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” [36] 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], [33], [35], [36], 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], [40], [41]

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

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

• 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, [32]

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

• zerotest - in C++ , presented at TERA’96, see [39] 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. 9ff) thus forming together with a few auxilliary classes, the main class slp, see p. 15ff.

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 4.5,

• the hash collision handling for monomials, see 4.6,

• the basic matrix arithmetics, see 4.8,

• the evaluation algorithm used, see 4.9,

• 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 4.5.

• 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.

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 9ff and further notes and comments are found in the implementation part, page 22ff.

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 9ff.

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

Documentation

This is the complete documentation for the classlib slp, describing all classes and all their functions with parameters and return values. This is intended more for programmers who want to extend the classlib, than for users developping new algorithms based on the classlib slp. For further comments on aspects of the current implementation, such as complexity issues, software maintance or extendability see the implementation part, 22ff.

3.1 Nodes of a straight–line program (slpnode)

1. Definition The design for the class slpnode is a simple container class. Within the context of the abstract data type straight–line program, every slpnode is defined by it’s type, it’s position and the positions of it’s operands (if any). We define the structure of a slpnode as a int vector along with readable field index names (tokens) for the higher-level classes in form of compile time define statements. The key field to distinguish the type of a slpnode will be the OPCODE field, which can take the values VAR, PAR, NUM, ADD, SUB or MULT. The position of the slpnode within the slp is given by (OWNR,OWNS) and the positions of the operands are given by (LEFTR,LEFTS) and (RIGHTR,RIGHTS), each tuple giving for the respective slpnode the corresponding depth level and the position within a list of slpnodes at that depth. With the following two conventions:

- if the slpnode represents a variable or parameter, the VARNUM field stores it’s ASCII code,

- if the slpnode represents a constant, the VARNUM field stores it’s value, a slpnode is completely defined by the eight fields

               (OPCODE, VARNUM, OWNR, OWNS, LEFTR, LEFTS, RIGHTR, RIGHTS).

These tokens will be available in all files including slpnode.h and will (hopefully) help writing more flexible code based on this class. For example: use GetData(OPCODE) instead of GetData(0). The same tokens will be re-used throughout the higher-level classes, and with the same interpretation. So do check slpnode.h for the names of the tokens.

2. Creation slpnode N;

creates an instance N of type slpnode. Memory allocation takes place through the LEDA memory manager. This memory has to be freed by the destructor.

slpnode N(slpnode M);

creates an copy of M.

slpnode N(int op, int varnum, int s); creates a constant, parameter or variable, assuming all other values to be zero.

slpnode N(int op, int varnum, int r, int s, int r1, int s1, int r2, int s2); creates a generic slpnode, passing all the information needed.

3. Operations

3.1 Access Operations

int  N.GetData(int which)  returns the datum specified by which.
void  N.SetData(int which, int value) sets the datum specified by which to value.
void  N.error(char ∗ s)  output an error message and exit(1).

3.2 Input and Output

void  N.read(istream &is)  reads the slpnode from the input stream is.
void  N.print(ostream &os)  prints the slpnode to the output stream os.

3.3 Operators

slpnode& N = &M  makes N a copy of M.

Overloaded versions of << and >> are available for reading/printing.

4. Implementation The data type slpnode is realized by an int vector and takes constant memory space, exactly DATANUM ∗ sizeof(int), which is free’d when the destructor is called. All operations take constant time O(1). Allocation through LEDA memory manager.

3.2 Lists of slpnodes (slpnodelist)

1. Definition The class slpnodelist is derived from the LEDA class list, and is used to maintain a list of pointers to slpnodes. As a derived class, slpnodelist inherits all public member functions of the LEDA class list, so check the corresponding LEDA man pages for more documentation. By design, the slpnodes in a particular slpnodelist are all of the same depth within the straight–line program. By listdepth or depth level we denote the depth r of the slpnodes in the list, this is reflected by the value of the field OWNR of the slpnodes in the list. The class member functions insertZ, findZ make only sense, if the nodelist is of depth level 0, as in the general case we will have to pass more parameters, so they are marked with a Z to distinguish them clearly. Remember: there is already a generic (inherited) insert function for the class slpnodelist, called append(), check the LEDA man pages.

2. Creation slpnodelist L;

creates an instance L, assigning it the empty list at depth 0.

slpnodelist L(int r); creates an empty list, assigning listdepth = r.

slpnodelist L(slpnodelist M); creates a copy of M.

3. Operations

3.1 Access Operations

void  L.SetDepth(int r)  sets the depth of the list to r
int  L.GetDepth()  returns the depth of the list

slpnode

L.GetNodeS(int s)

returns a pointer to the slpnode with index s in the list, NULL if not found.

bool  L.insertZ(int op, int varnum, int &pos s)

inserts a variable, parameter or constant (op = VAR, PAR,NUM, varnum = ASCII code or value) in a slpnodelist which is at depth level 0. It will return true if the corresponding slpnode had to be created and inserted, false otherwise (so the slpnode has been present already and was re-used). The resulting position is returned by reference in pos s.

bool  L.findZ(int op, int varnum, int &pos s)

tries to locate an instance of a given variable, parameter or number in the list and returns its position pos s by reference if successful.

void  L.error(char ∗ s)  output an error message and exit(1).

3.2 Input and Output

void  L.read(istream &is)  reads L from the input stream is.
void  L.print(ostream &os)  prints L to the output stream os.

3.3 Operators

slpnodelist L & = &M  makes N a copy of M.

Overloaded versions of << and >> are available for reading/printing.

4. Implementation The class slpnodelist is derived from the LEDA class list, realized by doubly linked linear lists. All operations take constant time except for the copy constructor, destructor, insertZ, findZ, search, rank, GetNodeS, assigment = operator and I/O operations, which take linear time O(n), where n is always the current length of the list. The space requirement is O(n∗sizeof(slpnode)). Allocation through LEDA memory manager.

3.3 Nodes of a slp in vector format (vecnode)

1. Definition

A instance N of the data type vecnode is a simple container class for the data defining a node of a straight–line program in vector format. Each vector component, for short vecnode, will have to store all the information neccessary for a fast evaluation of the slp, once we have specialized all variables and parameters of the slp.

To define the vecnode structure, we distinguish between variables, parameters, constants and intermediate arithmetic operation nodes. We define readable names (tokens) for the data contained in a vecnode:

VECOPCODE,  storing a code for the type of operation performed
LEFT, RIGHT, indices of the left and right operand
LAST,  the index of the last vecnode using this node as an operand
VALUE,  the value of this node (only during evaluation)

The VECOPCODE field can take the values VAR, PAR, NUM, ADD, SUB, MULT, modified by LCONST/RCONST

to indicate that the left/right operand of the arithmetic operation is a constant.

When we store a variable, parameter or a numerical constant in a vecnode, we have to store both its name and value, so to save space we used the convention to store the name in the LEFT field (as this field would remain unused for VAR, PAR, NUM nodes) whereas its value goes, as it should, into the VALUE field. For memory management reasons we will store in a field LAST how long we have to keep the component’s VALUE field in memory before we can discard it.

To optimize access, whenever a vecnode representing a constant appears as an operand in another vecnode, we store its value in the LEFT or RIGHT field of that node instead of the corresponding vecnode index. This will be then indicated by using the LCONST, RCONST modifiers on the VECOPCODE field.

The ideas of information hiding and portability mentioned in the documentation for the class slpnode apply here as well. So check the vecnode.h file for the readable tokens and use them instead of numbers.

2. Creation

vecnode N;

creates an instance N of type vecnode.

vecnode N(vecnode M);

creates a copy of M.

vecnode N(int op, int varnum, int val);

creates a vecnode of type op with value val.

vecnode N(int op, int left, int right, int last);

creates a vecnode which performs the operation op on the two vecnodes given by their indices left and right.

3. Operations

3.1 Access Operations

int  N.GetData(int which)  returns the datum specified by which.
void  N.SetData(int which, int val) sets the datum specified by which to val.

integer  N.GetValue()  returns its value as a multiprecision integer.
void  N.SetValue(integer &val)  sets its value to the multiprecision integer val.
void  N.SetValue(int val)  sets its value to val.
void  N.error(char ∗ s)  output an error message and exit(1).

3.2 Input and Output

void  N.read(istream &is)  reads the vecnode from the input stream is.
void  N.print(ostream &os)  prints the vecnode to the output stream os.

3.3 Operators

vecnode& N = &M  makes N a copy of M.

Overloaded versions of << and >> are available for reading/printing.

4. Implementation The data type vecnode is realized by an int vector for the VECOPCODE, LEFT, RIGHT and LAST fields and a pointer to an instance of the class integer, representing a multiprecision (arbitrary length) integer. A vecnode takes memory 4∗sizeof(int) + one pointer + the space needed to store the integer VALUE (only during evaluation), all of which is free’d when the destructor is called. All operations take constant time O(1), except for SetValue, GetValue when they have to copy the multiprecision integer passed. Allocation through LEDA memory manager.

3.4 Vector representation of a slp (vecnodearray)

1. Definition The class vecnodearray is derived from LEDA class array, and is used to maintain an array of pointers to vecnodes. As a derived class, vecnodearray inherits all public member functions of the LEDA class array, so check the corresponding LEDA man pages for more documentation. Remark that, at the time of creation, we known the exact number of entries for the array, and that it will not change (it is determined by the length of the straight–line program).

2. Creation vecnodearray N;

creates an empty vecnodearray.

vecnodearray N(int size); creates a vecnodearray with val entries.

3. Operations

3.1 Access Operations

void  N.error(char ∗ s)  output an error message and exit(1).

3.2 Input and Output

void  N.print(ostream &os)  prints N to the output stream os.

Overloaded version of << is available for printing.

4. Implementation The vecnodearray class is derived from the LEDA class array, implemented by C++ vectors. The access operations take time O(1). The destructor and print operations take O(L), where L is the length of the corresponding straight–line program. The space requirement is O(L∗sizeof(vecnode)), see 3.3. Allocation through LEDA memory manager.

3.5 Testpoints, primenumbers et al (testpoint)

1. Definition The class testpoint is a quick way of providing the main program with an extendable testpoint generator. It will be used in conjuntion with a preliminary version of is zero(), implementing a zero-equivalence test for straight–line programs representing numbers (as described in [10]). Right now, we use only one test set, namely, the sequence of primes in ZZ. But it should be easy (and an interesting possibility) to extend the class by writing a new constructor type, for example, by passing a pointer to a generating function and initializing the set of testpoints with the function values... Using the testpoint::read() function, you can reload a different set of testpoints from a file.

2. Creation testpoint P;

creates a list of the first few primenumbers read from the file prime.list, permitting for a dynamically increasing list, if neccessary.

testpoint P (int n); creates a list of the first n primenumbers. Requests with index ≥ n are illegal and will cause an error message.

3. Operations

3.1 Access Operations

int

P.GetData(int i)

returns the i’th testpoint. For primenumbers GetData(0) yields 2 by convention.

3.2 Input and Output

void  P.read(istream &is, int n)  reads a list of n testpoints from the input stream is.
void  P.print(ostream &os)  prints the current list to the output stream os.

3.3 Operators

int  P [int i]  P [i] returns the i’th testpoint.

4. Implementation The class testpoint is realized by an int vector and takes either constant memory space when using the testpoint(n) constructor, exactly n * sizeof(int), or dynamically adopts to the requests of the calling functions. Access takes constant time O(1), once the list is initialized. Initialization will read a file storing the first few testpoints and if any further are requested, it will start to construct the missing testpoints by using the generating function (for primenumbers, this results in sieving, not very efficient, but you asked for it). Allocation through system memory manager.

3.6 Straight–line programs (slp)

1. Definition

The class slp is a prototype implementation of the abstract data type straight–line program as described in 1.2. It is realized as a union of different LEDA derived classes, providing the basic aspects of functionality for straight–line programs.

It does not achieve the theoretical complexity bounds of the abstract data type straight–line program, though. There are some minor improvements left to be made (see 1.3) as well as difficulties with the present design, which should be re-considered for a more efficient design and implementation, see the comments in 4.8.

2. Creation

slp A;

creates an instance A of type slp and initializes it to the empty slp.

slp A(int X);

creates an empty slp representing a vector of length X.

slp A(int X, int Y);

creates an empty slp representing a matrix of size X × Y.

slp A(char ∗ s);

creates a slp for the polynomial given by the string s.

slp A(slp B);

creates a copy of the slp B.

3. Operations

3.1 Access Operations

3.1 Boolean tests

bool  A.is empty()  returns true if the slp is empty.
bool  A.is var()  returns true if the slp uses variables.
bool  A.is univar()  returns true if the slp uses exactly one variable.
bool  A.is multivar()  returns true if the slp uses more than one variable.
bool  A.is single()  returns true if the slp is a single result.
bool  A.is vector()  returns true if the slp is a vector of results.
bool  A.is matrix()  returns true if the slp is a matrix of results.
bool  A.is const()  returns true if the slp is a numerical constant.

bool  A.is poly()  returns true if the slp is a polynomial.
bool  A.is univarpoly()  returns true if the slp is a univariate polynomial.
bool  A.is multivarpoly()  returns true if the slp is a multivariate polynomial.
bool  A.is valid position(int r, int s) returns true if (r, s) is a valid slpnode position.

bool

A.is const(int r, int s, int &val)

returns true if the slpnode at position (r, s) represents a constant.

bool  A.is zero()  returns true if the slp represents 0. See 4.5.

3.2 Obtaining more information

int  A.GetData(int which)  returns the datum specified by which.

Use the following tokens for GetData() to obtain information on the slp’s internal data:

MyId  an identifier for the particular slp,
MyVar  a counter for the number of variables appearing in the slp,
MyNum  dito, for numerical constants,
MyPar  dito, for parameters,
MyDepth a counter for the depth of the slp,
MyLength a counter for the total number of slpnodes in the slp,

 MyDim  takes the values SINGLE, VECTOR or MATRIX,

MyDimX  the first dimension size for vectors and matrices,
MyDimY  the second dimension size for matrices.
void  A.SetData(int which, int val) sets the datum specified by which to val.
void  A.IncData(int which)  increments the datum specified by which.
void  A.DecData(int which)  decrements the datum specified by which.
void  A.Info(int info = INF ODEF AULT)

print out statistics on the slp.

Use the following tokens for Info() to obtain 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.
void  A.ShowNodes(int type)  lists all nodes of type VAR, PAR, NUM.

void

A.Show(int info)

lists all result nodes and their positions (INFORESULT), prints the numerical values of the slp’s result nodes (INFOVAL), or prints the scalar/non-scalar complexity of the result nodes (INFOCOMPLEX).

int  A.non scalar complexity(int X, int Y)

returns the non scalar complexity of the slp’s result node (X, Y).

void  A.error(char ∗ s)  output an error message and exit(1).

3.3 Evaluation

void

A.Specialize(char var, int val)

assigns to the variable (or parameter) given by char var

                                         the value val. Example: A.Specialize('X',3);

void  A.Specialize(int which, int ∗ values)

assigns the values given by the int vector values to the nodes of type which (VAR, PAR) appearing in the slp, assuming a lexicographical order on these nodes. You should pass exactly GetData(which) values.

void

A.Evaluate(int module = 0)

performs the evaluation of the slp (mod modulo, default none), use Specialize() to assign values to the VAR, PAR slpnodes beforehand.

int

A.vectorindex(int r, int s)

calculates the index of the vecnode corresponding to the slpnode (r, s).

void A.ToVector() transforms the internal slp structure into a vector structure for subsequent evaluation.

void  A.Bubblesort(int n, int ∗ val) sorts the vector of n integers given by val.
void  A.GetCodelist(int which, int ∗ Codelist)

builds up a vector containing the ASCII codes of the slpnodes of type which (VAR/PAR) appearing in the slpnodelist at depth level 0. This is needed for correct assignment in Specialize(), where we assume that the values should be assigned in alphabetical order. The vector’s size is available via GetData(which).

3.4 I/O

void  A.read(istream &is)  reads the slp from the input stream is.
void  A.print(ostream &os)  prints the slp to the output stream os.

3.5 Arithmetic expressions The arithmetic operations +, -, *, +=, -=, *=, ++, -- and exponentation are available for writing arithmetic expressions involving straight–line programs and int variables in the standard way. However, overloading these operators results sometimes in additional (avoidable, see 4.5) copy operations, so all arithmetic operations are provided in a procedural version, too.

slp&  A = &B  makes A a copy of B.
slp&  A = int B  makes A a slp representing B.

slp&

A = char ∗ s

makes A a slp representing the polynomial given by the string s.

Assignment-based operators for straight–line programs. +=, -=, *= are available for all combinations of slp and int variables. The procedural versions of the arithmetic functions for combinations of slp and int variables are: add, sub, mul, negate. Note that these are standard names which follow the C++ run-time operator resolution scheme.

3.6 Access to the results

long

A.Value(int X = 0, int Y = 0)

returns the numerical value of the slp’s result node (X, Y) as a long int value (if it fits, that is). We should have Specialize()d all VAR, PAR slpnodes and Evaluate()d the vector constructed by ToVector() beforehand.

INT EGER A.IntegerValue(int X = 0, int Y = 0)

returns the numerical value of the slp’s result node (X, Y) as a multiprecision integer, see remark 4.4.

Automatic type conversion allows you to access the value of a single result slp even easier:

slp A = 17;
long B = A;
integer C = A;

Note, though, that this is not exactly in the lines of the ’low complexity’ philosophy of straight–line programs, as this might cause the slp to be evaluated, using multi-precision integer arithmetics without any bounds on the size of the intermediate results. In fact, using non-modular evaluation on a slp will make you loose any possible advantages over a more standard representation of your calculations. Therefore it is strongly recommended to use modular evaluation techniques or the overloaded compare operators ==, != (which will use is zero()) to obtain information on the result. A reasonable approach is to use Evaluate(p) modulo some prime p and then Value(X,Y) or long B = A or long B = A(X,Y) respectively to access the long value (bounded by the bit-size of the type long. The overloaded version of the () operator allows you to access the values of a multiple result slp by writing for example long val = slp(2,3); to obtain the value of the matrix entry (2, 3). Note that this returns rather Value(X,Y) than IntegerValue(X,Y following the above mentioned ideas.

3.7 Join and Copy

void  A.init(int type = SINGLE, int X = 1, int Y = 1)

allocates all data structures, creating an empty slp. By default creates an empty single result slp.

void  A.zap()  deallocates all data structures.
void  A.Copy(slp &B)  makes A a copy of B.

void

A.Join(int op, int val, int side)

assigns A =val op A or A =A op val depending on side

                                         = LEFT or RIGHT.

void

A.Join(int op, slp &B, int side)

joins the current slp A with the one given by B using the given arithmetic operation op.

void A.MatProdSum(...) constructs a slpnode representing the sum of slpnodes given by a vector. This function is only used by Join() for the multiplication of slps representing matrices.

3.8 Parsing a string

void  A.ParseString(char ∗ s, int &R, int &S)

reads a polynomial given by the string s, builds up the corresponding straight–line program and returns the result node position (R, S). int A.LexInputBuffer() converts the string given by char *InputBuffer into a tokenized stream applying the lexicographical rules specified in the file parser.l using lex.

int A.YaccInputBuffer() performs a semantical interpretation of the tokenized stream (using yacc, implemented in parser.y) to construct a straight–line program.

The following operations are used by YaccInputBuffer() to carry the interpretation from the token stream over to the slp structure. The key rôle plays the LEDA class stack of node positions, NodePos, where the current operand and/or operator positions are stored.

void  A.AddOperator(int op)  adds an arithmetic node of type op.
void  A.AddOperand(int op, int value) adds a operand node VAR, PAR, NUM.

void A.AddExpOperator(int exp) adds a node representing (current node)^{exp}. This function in turn uses the BPWR(), PWR() functions.

void  A.BPWR(int varcode, int exp, int &tmpR, int &tmpS)

adds a node representing varcode^{exp}, trying to minimize the number of new nodes by re-using existing monomial powers in the slp.

void  A.PWR(int varcode, int exp, int &tmpR, int &tmpS)

dito, trying to do a right shift on the exponent.

void A.power(int &R, int &S, long exp) will be called with the position of a slpnode given in (R, S) and an exponent exp. It then constructs the nodes neccessary to calculate (R, S)^{exp} and returns the result position in (R, S).

int  A.mylog(int n)  returns log_{2}n.

3.9 Inserting a slpnode into the straight–line program

void  A.insertZ(int op, int varnum, int &s)

inserts a slpnode representing a variable, parameter oder constant into the list of slpnodes at depth 0 and returns the position s by reference. This function makes only sense for the slpnodelist of depth 0 as in the general case we will have to pass more parameters so it is marked with a Z to distinguish it clearly.

void  A.insert(int op, int &r, int &s, int r1, int s1, int r2, int s2)

inserts a generic slpnode into the slp, all information is predetermined, returns the resulting position in (r, s).

3.10 Manage Result nodes of the slp

By design, the positions of the slp’s result nodes are stored in the LEDA class array2 ResultTab using

struct Position.

void  A.GetResult(int X, int Y, int &R, int &S)

returns the position (R, S) of the result (X, Y).

void  A.SetResult(int X, int Y, int R, int S)

sets the result (X, Y) to position (R, S).

void  A.PowerResult(int X, int Y, long exp)

will replace the result node (X, Y) by (X, Y)^{exp} using

                                         power().

void  A.assign(int X, int Y, int val) assigns the value val to the slp’s result node (X, Y).

void

A.assign(int X, int Y, char ∗ s)

assigns the polynomial given by the string s to the slp’s result node (X, Y).

3.11 Administration of the slpnodelists of depth r

By design, the lists of slpnodes of the same depth are hashed (stored) in the LEDA class h array ListTab

using struct RList.

void

A.SetDepthList(slpnodelist ∗ L)

is used by read() to assign a complete slpnodelist read from a file.

void  A.SetDepthListCopy(slpnodelist ∗ L)

is used by Copy() to copy a complete slpnodelist from a given slp.

void  A.SetDepthListCopy(slpnodelist ∗ L)

returns a pointer to the slpnodelist at depth r.

void  A.HashDepthList(int r, slpnodelist ∗ L)

stores the pointer L in the internal ListTab.

bool  A.FindDepthList(int r, slpnodelist ∗ &L)

returns true and the list pointer by reference, if there exists a slpnodelist at depth r in the internal ListTab.

3.12 Administration of monomials

By design, the positions of the monomial powers of the variables appearing during the construction of the slp are stored in the LEDA class h array HashTab using struct VarPower. Clarification: this does not mean that we keep track of any monomials resulting from further arithmetic operations with the slp. This is just done to (try to) minimize the depth of the slp derived from the string describing the polynomial, and is not related anyhow with the concept of a monomial basis (of some ideal).

void  A.HashMonomial(int varcode, int exp, int R, int S)

stores the position in the internal HashTab.

bool  A.FindMonomial(int varcode, int exp, int &R, int &S)

returns true and the position (R, S) by reference if the monomial varcode^{exp} exists in the slp.

3.13 More operators

Overloaded << and >> operators are available for printing/reading of slp’s.

Overloaded versions of the ==, != operators

Overloaded versions of +, -, * operations

Overloaded version of the exponentiation operator 3.14 Internal Datastructures

ID, a unique internal identifier for every instance of the class slp (for debugging purposes).

MyData, a vector of MyDataNum many int fields for the internal counters. This includes a field MyId, which you can use to mark any particular slp for easy recognition. This is independent of the ID field.

ResultTab, a pointer to a LEDA class array2 of node positions, which is used to store the positions of the result nodes of the straight–line program.

ListTab, a pointer to a LEDA class h array of pointers to slpnodelist, used to maintain the lists of slpnodes of the the same depth. In this way, access to the list of nodes at depth r is expected O(1).

HashTab, a pointer to a LEDA class h array of slpnode positions, used to store the (r, s) coordinates of slpnodes calculating monomial powers of the variables appearing (at construction time) in the straight–line program. In this way, access is expected O(1).

NodePos, a pointer to a LEDA class stack of slpnode positions, used only temporarily by the parser part of the class slp when building up a slp from a string.

VNA, a static pointer to a vectornodearray, derived from the initial slp DAG structure by ToVector() and used only during the evaluation of the straight–line program.

TestPoint, a pointer to a testpoint generator (used by is zero() and the ==, != compare operators), see 3.5, 4.5. Note that there is only one such generator for all instances of the class slp.

3.14 Hashing Data

In the class slp, the following data is stored in LEDA class h array hash arrays: the positions of monomial powers of the variables appearing (at construction time) in the slp (in HashTab) and the pointers to the slpnodelists (in ListTab). Read the LEDA manual pages on Hashing for an explanation of what has to be provided to use the LEDA class h array.

struct VarPower: Store the information: slpnode (r, s) computes <variable>^{exp}.

int

A.Hash(int R, int S)

returns the hashkey used to store the slpnode (r, s) in the HashTab array of monomial powers.

struct RList: Store for each depth level r a pointer to the list of slpnodes. We use a hash array instead of a standard array to allow for dynamic growth of the slp without limitations on the depth.

struct Position stores the position (r, s) of a slpnode. This will be used only to maintain the LEDA class array2 ResultTab of all result nodes of the slp.

Additional notes and comments

Here all additional information, remarks on particular features or design aspects of the classlib are collected. Some of them are more in the lines of memo notes for later discussion, so that these notes here should be considered for a second design phase. This includes such considerations as complexity issues, software maintance or extendability.

Even more details on specific points/parts/functionality of the source code can be found in the form of comment lines in the source.

4.1 General notes

• find good trade-off between access time, hashing and memory usage.

• verify all member functions for scope and const’ness.

• reconsider the public/private’ness of all member functions.

• change small member functions to inline code to avoid stack overhead.

• functions with ugly or soon-to-be-made-nicer code which deserve improvement are marked as such, grep for IMPROVE.

• reduce the amount of stored information which is calculated on the way i.e. the OWNR, OWNS fields, see the notes on slpnode 4.2, slpnodelist 4.3.

• consider unifying the various ways of passing (r, s) positions, and more generally, think about ways of reducing the stack overhead by passing the arguments in a more decent way.

4.2 Nodes of a straight–line program (slpnode)

EXTEND: At design time, the alternatives were either to use int variables for all data appearing and thus accept the restriction to ZZ as a ground domain for the coefficients appearing in the straight–line program, or to write a flexible class performing the corresponding arithmetic operations on the coefficients in an arbitrary domain.

As ZZ seems to be suffiently generic for the moment, the current implementation does not allow for arbitrary coefficient domains, but, also in the lines of data encapsulation, all classlib functions are written to use access functions to handle the coefficients and thus the extension to a more complex design for the domain should not be too difficult.

IMPROVE: One first optimizing step would be to encode the constant operands of a slpnode directly in the corresponding index fields LEFTS, RIGHTS (slpnode) or LEFT, RIGHT (vecnode). For the moment, this is done in the vecnode class only, as I wanted to maintain the direct correspondance between the intuitive concept of a straight–line program and the class slp structure as it appears at print-out for debugging purposes. IMPROVE: Having OWNR as a field in every slpnode basically means that all nodes appearing in a particular list of nodes (class slpnodelist) will carry too much information, as this OWNR field will be always the same. It depends on at what level we want to make available the information about a node’s depth. At class slp level, we can derive it from the index of the list of nodes it is in. But then we can’t double-check the coherence of the data at slpnodelist level. EXTEND: The ground domain for the coefficients of the straight–line program: the constructor slpnode(int op, int varnum, int s) creates a constant, parameter or variable, assuming all other values to be zero. Here we make use of the design convention, to number all things starting from 0. This constructor is used to generate nodes which will be constants and as such belong by design to the nodes of depth level 0 in the straight–line program. So, if one would want to expand the class slp to work a more flexible domain for the coefficients of the straight–line programs, the coefficients would have to be passed through here. EXTEND: Consider rewriting the class slpnode using C++ Templates for the coefficients as a base class, thus creating a domain-independent version of the classlib.

4.3 Lists of nodes (slpnodelist)

IMPROVE: The listdepth r of a particular slpnodelist could also be derived without storing a local variable (by using the depth index of the list stored in slp::ListTab). But again, as in the case of the class slpnode, the question is, at what level we want to make this information available. Keeping it here within the class slpnodelist, we have additional possibilities to check the consistency of the operations in our algorithms. Implementation detail: the difference between iterated push and append: The physical order of the slpnodes in a copy of the slpnodelist is reversed, if we copy the nodes using list::push(), so we cannot just derive OWNS from the node’s position in the list using list::rank(), as it is possible when copying the list using list::append(). This is a starting point for the investigation of the time-space trade-off between keeping OWNS as a field in each slpnode and recomputing its rank everytime we access the slpnode. At present the OWNS field of the slpnode is used to double check whether it coinceeds with its rank() or not. Consider also the influence of the slpnodelist representation form on the slp::Join() operation, see 4.8.

4.4 Nodes of a slp in vector format (vecnode)

A very important aspect for the bit complexity of our algorithms is the correct handling of all occurring instances of multiprecision integers. Of course, the best approach is using modular arithmetic with a bound of 32 bit, but sometimes it is desirable to perform the evaluations without any restrictions. By default, the LEDA class integer is used for the long integer arithmetics, as this will allow to use the LEDA memory manager statistics to trace memory usage for all parts of the slp classlib, including the LEDA class integer. So recheck in detail, make tests, and double check that you do not copy or pass by value any integer if not really neccessary. As some people probably will prefer to use the GCC class Integer for the multiprecision arithmetic, but on the other hand debugging will be a lot easier using the LEDA class integer, there exists a macro USE LEDA INT in vecnode.h, undefine it to make the whole classlib slp to use GCC Integers instead.

4.5 Overloading operators (slp op)

Writing your algorithms using overloaded operator versions of the arithmetic operations for straight–line programs is surely the clearest way to advance the development of new algorithms. However, in a second step, when it comes to optimization, overloaded operators tend to cause additional calls to constructors and copy operations for temporary variables by the way the C++ run-time system works.

You can use the LEDA memory manager status report print statistics() to keep track of memory usage and in some situations it is really indicated to make use of the procedural versions of the arithmetic operations, which are available to exactly the same extend as the operator versions.

As the LEDA memory manager tracks the allocated memory blocks sorted by size, it is rather easy to find the memory abusive functions or even worse, memory leaks in your code. For that purpose, the following table will be quite useful:

Structure  allocation method blocks of size (bytes)
RList  dynamic  8
Position  dynamic  8
VarPower  dynamic  16
integer (empty) standard  20
integer (empty) dynamic  4+20
vecnode  standard  4+20
vecnode  dynamic  4+20+24
vecnodearray  dynamic  32
slpnode  dynamic  32
slpnodelist  dynamic  40
slp (empty)  dynamic  8+60

EXTEND: Once the slp::Join() member function (see 4.8) has been improved in such a way that merging of slps is as fast as copying them, it becomes attractive to consider the design of a destructive variant of the arithmetic operations, as most of the time, our right hand side values in the equations are not used again, once the left hand side assignment is made, and so could be merged and deleted directly in the course of the arithmetik operation.

IMPROVE: is zero() is a preliminary version of the zero-equivalence test for straight–line programs representing integers (as described in [10]) and does not yet:

• accept a time bound parameter, which then would return the achieved error probability ε,

• fix the correct number of primes using the complexity of the slp,

• accepts a ε parameter for the error probability it should garantuee.

EXTEND: The exponentiation operator supports only single result straight–line programs for the moment. When implementing/improving matrix arithmetics, extend this operation to matrices as well.

4.6 Hashing Data (slp hash)

We have to define a hash function for the use of the LEDA class h array to store the positions of slpnodes representing monomial powers. There are at least two alternative solutions:

i) a separate hash table per variable or

ii) a common hash table for all variables.

With the first approach it is not neccessary to store the variable name, whereas in the second case we will have to handle collisions, whenever they occurr. Then, for multivariate polynomials, the central problem seems to find a suitable definition which avoids hash collisions as far as possible.

The second approach is tried here, but there is no scientific reason for this, the the trade-off is searching for the right variable at the position given by Hash(exponent) including the collision detection and handling against size and readability of the code to maintain an array ”A”..”Z” of pointers to the different hash arrays.

Reconsider this, especially if the number of variables is small!

The current Hash function tries to reduce the probability of a hash collision of different monomials with the same exponent by shifting, see the definition of the Hash function in slp hash.cc.

Right now, both the univariate as well as the multivariate case are supported, just in the multivariate case when encountering hash collisions, the new monomial is not stored (instead of handling the collision). This can lead to a slightly increased depth for the constructed polynomial.

IMPROVE: As we will have to construct the hashkey from (varcode,exp) we have to do collision detection and handling. This is not yet implemented (grep for HASHCOLLISION), as it is worth thinking a bit about it. Linear displacement or quadratic seeking or ... ? Once a good solution is found, it should go in the two member functions slp::FindMonomial, slp::HashMonomial, where at the moment we just ignore the new monomial, whenever we detect a hash collision. The collision handling strategy will have an impact on the expected access time for the monomials at construction time.

4.7 Constructing a slp (slp parser)

When parsing the polynomial given in the InputBuffer string and building up the reverse polish notation of the polynomial, we need the LEDA class stack NodePos for the positions of the nodes of the intermediate results as inserted into the slp. This is temporary and after parsing the InputBuffer the stack NodePos is empty and will not be used again, so both allocation and deallocation takes place in slp::ParseString(). The algorithm used here is based upon the design of the unp algorithm presented in [28].

IMPROVE: To improve readability, rewriting of this part could be considered, changing from stack<int> to stack<Position> and adapting the various functions passing positions as two int values.

IMPROVE: In AddOperand() is a hardcoded discrimination between variables and parameters, defining VAR = A..Z, PAR = a..z. We could pass two sets of letters on the commandline instead (we would have to improve the parser then, as well) specifying the letters to be used for variables and parameters. This is the only place though, where this is fixed, and changing this here is sufficient for all the rest of the code.

4.8 Joining straight–line programs (slp join)

This is a first trial implementation of the slp::Join() member function, but it seems to be the crucial point in the implementation. If the representation design of the abstract data type ’straight–line program’ does not permit a more efficient way of joining two slp’s, we are going to spend more time on this operation than really neccessary.

The influence of the design concept and the chosen datastructure for the representation of the set of all slpnodes of the same depth on the overall complexity of our algorithms is very strong: Right now, we can NOT simply concatenate two lists of slpnodes when joining two slps.

The reason is the way, the slpnodes refer to their operands by a simple int value to the position of their operands in a different list. These positions coinceed with the ranks of the slpnodes in their lists, and so joining these lists with other ones changes the slpnode’s rank, thus destroying the correct interpretation of the reference fields.

So in the current design, Join() has to ’adjust’ the rank fields OWNS for most slpnodes in the second slp being joined, and thus works in O(L), using extra time O(L) and temporary space O(L) for these adjustments.

Implementation detail: slp::Join(): we will have to check for type compatibility of the slps we are going to join, as a slp can represent 0, 1 or 2 dimensional objects (MyDim) as well as different semantical aspects: scalars (numbers) or polynomials, and not all operations are well-defined.

IMPROVE: We already recycle all VAR, PAR, NUM nodes at depth level 0 to maintain unicity of these, and we hash the (adjusted) monomial power positions into A. Discuss this point again, for it is not very clear, if we will ever make use of the hashed monomial powers again apart from construction time.

IMPROVE: MatProdSum() is an implementation of a Divide and Conquer algorithm to construct a slpnode representing the following sum: Given a n × m matrix A = (a_{i,j}) and a m × o matrix B = (b_{j,k}) the product n × o matrix C is C = A ∗ B = ((∑_{j=1}^{m} a_{i,j} · b_{j,k})_{i,k}).

Here it is neccessary to sum over the index j of products of the initial a_{i,j} and b_{j,k}. Therefore we build up a set of m arrays containing the positions of the intermediate nodes representing a_{i,j} · b_{j,k} (for fixed j) and then sum over j, trying to minimize the increasing depth of the straight–line program by using Divide and Conquer. The positions of the nodes to be summed are passed by a vector of pointers to array2<Position>(n, o), the position of the result node of the call is returned by reference in (R, S).

IMPROVE: implement a complete set of efficient straight–line program suitable matrix arithmetic operations and call them from Join(). But as this is the first prototype, it is left for the future.

4.9 Evaluation (slp eval)

slp::Evaluate() is a direct implementation of the mt evaluation algorithm for straight–line programs representing univariate polynomials as described in the paper [28].

IMPROVE: Here is plenty of space/time left for improving things, re-consider the pebble-game ms described in [28], the multivariate evaluation strategies (Paterson, Stockmeyer et al) [31].

EXTEND: It would be nice to implement ’partial or lazy evaluation’, keeping track of evaluated parts of a slp, or even more sophisticated things.

EXTEND: At present there is no way to extract the slp associated to a particular result node into a separate slp.

IMPROVE: Automize the way slp::ToVector() has to be called before slp::Evaluate(). It is possible to specialize the variables several times without having to call slp::ToVector() again.

Tables of classes and functions

All member functions for the classes slpnode, slpnodelist, vecnode, vecnodearray and testpoint are, if not inherited from LEDA base classes, declared and implemented the corresponding .h and .cc files. For the description of the LEDA classes see the LEDA manual which comes with the LEDA distribution. The member functions for the class slp are all declared in slp.h.

Class name Header file  Source file  Page Notes
slpnode  slpnode.h  slpnode.cc  9  22
slpnodelist  slpnodelist.h  slpnodelist.cc  10  23
vecnode  vecnode.h  vecnode.cc  12  23
vecnodearray vecnodearray.h vecnodearray.cc 13  -
testpoint  testpoint.h  testpoint.cc  14  -
slp  slp.h  slp int.cc  15  -
slp  slp.h  slp op.cc  15  24
slp  slp.h  slp hash.cc  15  24
slp  slp.h  slp join.cc  15  25
slp  slp.h  slp parser.cc  15  25
slp  slp.h  slp eval.cc  15  26

source file Access Function name  Page
slp parser.cc private AddExpOperator() 19
slp parser.cc private AddOperand()  19
slp parser.cc private AddOperator()  19
slp int.cc  public assign(char*)  20
slp int.cc  public assign(int)  20
slp parser.cc private BPWR()  19
slp eval.cc  private Bubblesort()  17
slp join.cc  private Copy(slp)  18
slp int.cc  public error()  17
slp eval.cc  public Evaluate()  17
slp hash.cc private FindDepthList()  20
slp hash.cc private FindMonomial()  20
slp eval.cc private GetCodelist() 17
slp hash.cc private GetDepthList()  20
slp hash.cc private GetResult(int)  19
slp hash.cc private HashDepthList()  20
slp hash.cc private HashMonomial()  20
slp int.cc  public Info()  16
slp op.cc  private init()  18
slp int.cc  public insert()  19
slp int.cc  public insertZ()  19
slp eval.cc  public IntegerValue()  18
slp.h  public is const()  15
slp.h  public is empty()  15
slp.h  public is matrix()  15
slp.h  public is multivarpoly()  16
slp.h  public is poly()  16
slp.h  public is single()  15
slp.h  public is univar()  15
slp.h  public is univarpoly()  16
slp.h  public is var()  15
slp.h  public is vector()  15
slp eval.cc  private is const(int)  16
slp eval.cc  private is valid position() 16
slp op.cc  public is zero()  16
slp join.cc  private Join(int)  18
slp join.cc  private Join(slp)  18

source file Access Function name  Page
slp join.cc private MatProdSum() 18
slp parser.cc private mylog()  19
slp op.cc public negate() 17
slp int.cc  public non scalar complexity() 16
slp op.cc  public operator *= (int)  17
slp op.cc  public operator *= (slp)  17
slp op.cc  public operator ++ ()  17
slp op.cc  public operator += (int)  17
slp op.cc  public operator += (slp)  17
slp op.cc  public operator – ()  17
slp op.cc  public operator -= (int)  17
slp op.cc  public operator -= (slp)  17
slp op.cc  public operator = (char*)  17
slp op.cc  public operator = (int)  17
slp op.cc  public operator = (slp)  17
slp op.cc  public operator ˆ(long)  17
slp parser.cc private ParseString()  18
slp op.cc  private power()  19
slp op.cc  public PowerResult()  20
slp op.cc  public print(ostream os)  17
slp parser.cc private PWR()  19
slp op.cc public read(istream is) 17
slp hash.cc private SetDepthList(int)  20
slp hash.cc private SetResult(int)  20
slp int.cc  public Show()  16
slp int.cc  public ShowNodes()  16
slp op.cc  public slp()  15
slp op.cc  public slp(char*)  15
slp op.cc  public slp(int)  15
slp op.cc  public slp(int, int)  15
slp op.cc  public slp(slp)  15
slp eval.cc  public Specialize(int)  17
slp eval.cc  public Specialize()  17
slp eval.cc  public ToVector()  17
slp eval.cc  public Value()  18
slp eval.cc  private vectorindex()  17
slp op.cc  private zap()  18
slp op.cc  public ˜ slp()  -

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] M. S. Paterson and L. J. Stockmeyer. On the number of nonscalar multiplications necessary to evalutate polynomials. SIAM J. Comput., 2:60–66, 1973.

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

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

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

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

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

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

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

[39] 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.

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

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