Download scope - REDUCE Computer Algebra System

2 PRELIMINARIES
5
summarized as follows:
R
Tβ
F
R−1
:
Ein = E0
: (Di , profiti )
: (Dλ , profitλ )
:
Dλ
→
→
→
→
(D0 , profit0 )
(Di+1 , profiti+1 ) , i = 0, ..., λ − 1.
Dλ
Eλ = Eout
D0 is created as a result of an R-application performed on input E0 . The
termination condition depends on some profit criterion related to the arithmetic complexity of the latest version of the input, Di . Hence we assume
profiti = true for i = 0, · · · , λ − 1 and profitλ = f alse. The function T is
defined by T = F ◦ Tλβ , where Tβ defines one iteration step, i.e. one application of the extended version of Breuer’s algorithm, and where F defines a
finishing touch, resulting in the final version Dλ of D0 , used to produce the
output Eλ . It is stated in [?] that the computing time for Tβλ is O(n.m),
where n is the size of Ein and m the number of cse’s found during this process. Practical experience showed that the finishing touch can take about
10 % of the actual cpu-time and that its real profit is limited. Therefore its
use is made optional.
The wish to optimize source code, defining arithmetic, usually leads an
attempt to minimize the arithmetic complexity. This can be accomplished
by replacing cse’s by placeholders, assuming a new assignment statement
”placeholder := cse” is correctly inserted in the code. So most of the csesearches are done in right hand sides of arithmetic assignment statements.
The search strategy depends on the permissible structure of the arithmetic
expressions. We assume these expressions to be multivariate polynomials or
rational functions in a finite set of kernels, and presented in some normal
form. Let us further assume that scalar placeholders are substituted for the
non-scalar kernels, such that back-substitution remains possible, using an
adequate information storage mechanism. Then we are left with the interesting question how to define a minimal set of constituents of multivariate
polynomials in some normal form norm. Let us take as an example of such
a polynomial or rational function p = 3a + 2b + 3b2 c(3a + 2b)(c + d)2 . We
easily recognize linear forms, i.e. 3a + 2b (twice) and c + d, possibly raised
to some power ((c + d)2 ), power products, such as b2 c, or monomial parts
of products, i.e. 3b2 c. Hence with some imagination, one realizes that every
polynomial can be decomposed in a set of linear forms and a set of power
products. When assuming the validity of the commutative and the associative law, one can also realize that we can associate a coefficient matrix