SC-88-02
Contents
1. H Melenk H M M ller W Neun On Grobner Bases Computation on a Supercomputer Using REDUCE FB Mathematik und Informatik der Fernuniversitat Hagen D 5800 Hagen Federal Republic of Germany Preprint SC 88 2 January 1988 Konrad Zuse Zentrum f r Informationstechnik _ Heilbronner Stra e 10 D 1000 Berlin 31 Herausgegeben vom Konrad Zuse Zentrum f r Informationstechnik Berlin Heilbronner Strasse 10 1000 Berlin 31 Verantwortlich Dr Klaus Andre Umschlagsatz und Druck Verwaltungsdruckerei Berlin ISSN 0933 7911 Contents 1 Gr bner bases in REDUCE 3 3 1 1 Gr bner bases and Buchberger s algorithm 9 y 1 2 Buchberger s algorithm in REDUCE 3 3 1 3 Cray computer usage for Gr bner calculations c 0 o 9 f 1 4 Introduction of new facilities Refinement of Buchberger s algorithm and of its environment 24 The coefficient domains e 8 9 9 gt 8 o o o e o p 9 2 2 Polynomial reductions t 2 S g Be G Be 9 9 k g k G k 4 9 2 3 Extraction of power product factors dw 0 9 V 2 4 An additional criterion for detecting redundant pairs 2 5 Grobner factorization 9 d Three a 9 9 Tu o S hr o a G 2 5 1 Factorization tree 9 e 0 8 0 9 e 9 2 5 2 Cance2. the main algorithm A similar prereduction takes place immediately before a Gr bner basis calculation for a subproblem as described in 2 5 is started 2 3 Extraction of power product factors When Gr bner bases are needed only for the solving of a set of algebraic equa tions multiplicities of zeros may be ignored Therefore multiple factors of a polynomial may be reduced to simple ones by polynomial division We installed for the situation when such multiple factor is a power product a procedure following a proposal of Davenport 1987 If f has a power product factor f t img then f is replaced by f rir mg with l 1 if k gt 1 and 0 if k 0 1 1 m The new f has the same zeros as the old one but the multiplicity is reduced at all hyperplanes r 0 where the old f vanishes with multiplicity greater than 1 This causes that the algorithm calculates no longer a Gr bner basis of the ideal generated by the input polynomials but of an ideal between this ideal and the radical ideal which consists 6 of all polynomials vanishing at the common zeros of the input polynomials Such power product factor can be detected easily in the distributive representation its exponent vector is the vector of the componentwise minima over all exponent vectors This vector is computed during the normalization of each polynomial and held in its data structure 24 An additional criterion for detecting redundant pairs
3. 5 sec 14 Another example in B ge et al 1986 originating from M Rose was mentioned as a case where a computation with lexicographical order was impossible With our Cray installation we computed the Gr bner basis over Z But here the modular version is much more efficient because the Gr bner basis has some very long coefficients 300decimal digits ROSE 3 polynomials in 3 variables ITD see 5 3 INVLEX over Z 2288 sec Cray X MP in a job with 2 5 million 64 bit words of memory INVLEX over M 536870909 92 seconds Cray X MP INVLEX over M pi pi20 148 sec Cray X MP for Buchberger s algorithm plus 112 sec Cray X MP for the coefficient reconstruction Of course the single modular computation indicates as result only the monomial layout It has the aspect of a pioneer computation The calculation with coeffi cient vectors of length 120 modulo primes of moderate size less than 21 bits each allows the reconstruction of the true basis coefficients when normalized by RE DUCE common denominator technique these are identical with the coefficients calculated over Z Eight of the 120 primes were unlucky they could not take part in the reconstruction It turned out that 100 primes of this moderate size are the minimum for the reconstruction of the coefficients It should be noted here that because of the vector hardware the time of Buchberger s algorithm with 120 modular coefficients is not much slower than that
4. If two polynomials p and p are known to have a common factor g p gfi pP gh and if gea t f1 4 29 1 then we know in analogy to criterion 1 of Buchberger 1985 that the S polynomial from p and p will reduce to 0 This criterion will be used for power products divisors g see 2 3 This gives a new criterion for omitting superfluous reductions cf Buchberger 1985 or Gebauer and Moller 1988 It can lead in cases where many polynomials with common factors occur to a better performance of the algorithm 2 5 Grobner factorization For solving a system of algebraic equations fila 0 f z this means for finding Z f fr the set of common zeros of all polynomials in Ideal f fr Gebauer and M ller tested in a preliminary version of REDUCE 3 3 the following procedure If in the algorithm a polynomial h Ideal f f is found which can be factorized into h p secta then Z fi fr is the union of the sets Z fyi f he k l m l Thus when the algorithm did actually compute Ah it branches For each h in place of h it is continued resulting in the Gr bner bases for Ideal f fr hi k 1 m This factorization of the Gr bner basis calculations is also investigated by Davenport 1987 2 5 1 Factorization tree In the present package we have elaborated this approach by consequently testing all polynomials input intermediate and result for
5. a resp 2 2 Polynomial reductions A single reduction step modulo a finite set G of non zero polynomials reduces a polynomial f to a polynomial h f tg with ge G t a monomial such that the monomial m in f with li m lt t lt g is canceled by t g but h contains in addition some more monomials of lower order A pseudo reduction step modulo G reduces f to c f t g with g G t a monomial and c a constant coefficient such that again the monomial m with lt m lt t lt g in f is canceled This pseudo reduction is installed in addition to the COSME reduction and used for polynomials over Z and Z a a For testing the efficiency of reduction procedures we installed also the so called lt reduction This is also a reduction in the sense explained before but the monomial m in f which is canceled must be maximal lt m lt f This reduction is already sufficient in Buchberger s algorithrn for obtaining a Gr bner basis see for instance Moller 1988 However as our tests in 5 3 indicate the t reduction is in general slower s an optional feature we can start the algorithm by first reducing cyclically the input polynomials with themselves ie reduce each f F modulo g F lt g lt lt f beginning with an f with maximal lt f and resulting in a reduced polynomial set F which can be reduced again in the same manner etc Such a specific reduction phase can eliminate redundancies more efficiently than
6. e jour different choices the second component y is then determined by 82080y2 4131y y3 8775y2y2 179055y2y3 914565g 306993 79695y2 1192215y 2952125 0 i e two choices for fixed y3 and the first component y is determined for given y2 and y3 by 27360y 27360y2 1377y3 2925y2 59685y3 304855 0 The common zeros of the last six bases can be read off immediately The overall time for computing the eight G bner bases is 3 5 sec using a Cray X MP 2400 104 sec using a SUN 3 260 In this example long integer coefficients occured in the intermediate computa tions 5 2 Modular Gr bner computations As example for the efficiency of vector hardware usage a test calculation may serve An example in B ge et al 1986 originating from W Trinks produces moderate long integer coefficients and so we have calculated it with 63 compo nent modular vectors with different technical supports sequential processing of vectors compatible version of this arithmetic and processing by Cray vector in structions Of course this is no real application the problem and the coefficients are too small and so the computation of the reduced normalized Gr bner basis w r t the INVLEX ordering is totally dominated by the reconstruction effort TRINKS1 6 polynomials in 6 variables over M p pe3 sequential processing 5 8 sec usake of vector hardware 0 7 sec Reconstruction of coeflicients 8
7. fo fz is the union of the sets Z G 2 1 8 where the Gr bner bases G Ga are Gi ya 3y ya 22yi 3yaya 22y2 22y 121 27yiy3 198yiys 75y 27ysy3 198yays T5y2 198y 1164y3 250 81y2y 594y2ys 225y2 594y y2 3492ysys 750y 225y2 750y3 14575 Go 27360y 27360y 1377y3 2925y2 59685y3 304855 82080y2 4131y y3 87 15ysy2 179055y2y3 914565y 306993 79695y2 119221543 2952125 243y 54043 963043 25500ys 26125 Gs 3y 11 9y2 25 3y3 11 G 3y 11 3y 11 3y3 11 Gs 9y ais 25 3y2 11 3Y3 11 Ge 3Y T 5 3y2 19 3y3 5 Gr 3y1 5 3y2 5 3y3 5 Gg 354 e 19 3 5 3Y3 5 Denoting the three polynomials of Gi by g1 92 93 we find 768009 81y2y4 369y2 594y2y3 1842y 225y3 1375 g2 13 123y 123y 27yiys 27y2y3 198y3 614 g3 i e g vanishes at the common zeros of g and g3 Using ys for a free parameter the common zeros of g1 92 93 are hence yi ys ya with _ 99y2 582y3 1254 VA 99y2 582y 125 F YA V7 7 b i98y 475 C777 303 198 4756 where A 7776y4 107136y3 4890242 835200y 380000 The polynomials of G have exactly eight zeros y1 y2 y3 in common The third component ys is a zero of the irreducible polynomial 24343 540y3 9630y2 25500y3 26125 i
8. with one modulus in fact the additional time needed for the vector version has its origin mainly in the fact that more dynamic memory is wasted additional garbage collections 5 3 Some comparisons For comparisons we have done some calculations with examples listed in B ge et al 1986 We stress that our Gr bner package is designed for real life applications requiring the power of a super computer Therefore we omitted the tests of too simple examples But for economical reasons we also did not try all hard problems of B ge et al We present six medium range problems as candidates for testing the various features of an implementation The following statistics demonstrate the influence of the options on the computing time All these examples are no cases where there is an urgent need for the Cray power All computing times are given in seconds of Cray X MP the time needed for garbage collections during the computations is included the memory was limited to 1 million words 15 Bas D Q Lorg Prered ltred Fact Orig TRINKSI 03 63 03 04 02 21 170 GERDT 13 6 311 125 135 231 98 321 HAIRER3 129 148 117 126 136 0 999 381 KATSURA4 08 26 08 08 30 17 60 ROSEitdg 21 89 16 21 42 269 209 GONNET 14 14 09 10 23 08 11 Meaning of the columns Bas A basic package of options Domain ZZ polynomials compressed no prereduction of input full reduction no factorization The subsequent columns except the last one dif
9. CE 3 was implemented for Cray 1 and Cray X MP computers Me lenk and Neun 1987 based on Portable Standard LISP PSL 3 4 see Anderson et al 1987 and Melenk and Neun 1986 and with Version 3 3 of REDUCE the Grobner package became available for these computers too The objective was to use the combination of REDUCE and the supercomputer for the enlargement of the application range of Grobner bases calculations towards larger problems especially for the solution of systems of algebraic equations 1 4 Introduction of new facilities It soon became clear that the increased computing power alone was not sufficient to reach our goal So we started a four level approach refinement of the Buchberger algorithm improvement of the implementation special tuning of basic package parts for the target machine and optimization of the underlying LISP The first two groups will be discussed in the following sections They are machine independent in fact we developed the software using Sun and IBM computers as workstations The Cray specific parts will be mentioned only briefly 2 Refinement of Buchberger s algorithm and of its environnient 2 1 The coefficient domains We enlarged the range of applicable coefficient domains and fixed for any specific coefficient domain an adequate normalization In the field case all polynomials are normalized internally to have a leading coeffient 1 in the ring case no gen eral division avai
10. Dynamic selection of coefficient domains The interface for the coefficient manipulation of the distributive polynomials was redesigned completely So it now has one separate package for each coefficient domain one of them is the interface to the REDUCE standard quotients SQ Others are those for Z H p f M pi p Additional packages can be plugged in easily s default the algorithm expects coefficients in the most general domain SQ In its starting phase it does a general data type analysis and selects automatically the simplest arithmetic for the given problem 10 This is an efficient mixture of static and dynamic typing the type analysis is done dynamically once in the starting phase In the main working phase there is no more type checking because then all switches are already set This procedure is justified by the fact that the type analysis is very small compared with Buchberger s algorithm itself 3 3 Data Representation In the original version polynomials were represented as standard lists This or ganization is efficient for the manipulation but it consumes too much storage if large problems with thousands of intermediate polynomials are handled and it does not allow to link additional information to the individual polynomials So the polynomials now are embedded in an object oriented structure which al lows several different memory organizations with compatible generic access meth ods at the same time Eac
11. als are extracted from the ODE system without further preprocessing Their maximal degree is 3 The original coefficients are floating point numbers Most polynomials cite only a few number of variables sparse system Using the original algorithm the bigger 16 problems consume all available resources in an exploding manner without pro ducing any result Therefore we used the following configuration of Buchberger s algorithm reducing the input polynomials with themselves as long as It parts can be cancelled actually 5 cycles cf 2 2 cancellation of multiple power product factors cf 2 3 factorization on the base of power product factors cf 2 5 inverse total degree ordering 2 hybrid coefficients cf 2 6 2 Using this configuration we find a set of partial Gr bner bases Some of these bases have amp very simple structure e g only linear polynomials such that the solution can be read off immediately The following example HAVC4 was given to us by F P Deufthard 1986 It consists of 50 polynomials in 37 variables The longest polynomial has 31 terms Some of the polynomials have only 1 term We found hundreds of partial G bner bases which were all of the same simple structure such that their common zeros could be detected without additional computations The rate on the Cray X MP was one base per 4 CPU seconds An inspection gave that most of these bases have only solutions with at leas
12. ed weak Gr bner basis F over ZZ by dividing it by its Ic we get such uniquely determined Gr bner basis but now for the ideal generated by F over instead over Z Given a finite polynomial set F generating an ideal J Buchberger s algorithm con sists essentially in calculating the S polynomials pseudo reducing them mod ulo F to irreducible so called H polynomials enlarging F by the nonzero H polynomials removing from F such polynomials whose lt is a multiple of an lt of an other polynomial in F and then continuing by calculating new S polynomials until no more S polynomials exist leading to non zero H polynomials At termi nation F is a Gr bner basis of J Buchberger 1985 gave criteria for predicting that some H polynomials are 0 This allows to skip some S polynomial calcula tions 1 2 Buchberger s algorithm in REDUCE 3 3 Buchberger s algorithm was implemented in the Computer Algebra System SAC 2 see B ge Gebauer and Kredel 1986 It is based on the description of the algorithm given by B chberger 1985 The implementation of the algorithm in REDUCE 3 3 by Gebauer Hearn and Kredel is based on a variant which differs from the original Buchberger algorithm by a more efficient testing of the criteria for omitting S polynomial calculations and reductions This variant is described by Gebauer and M ller 1988 and also implemented in the meantime in SCRATCHPAD II The REDUCE 3 3 implementation includes an
13. fer from this column by only one modifi cation each D Q Usage of rational numbers instead of integers Lorg Switching off ternal compression cf 3 4 Prered Prereducing of the input polynomials Itred Only lt reduction Fact Factorizing enabled Orig usage of the original Gr bner package of REDUCE 3 3 The statistics give the following result Domain Z is faster than Q in almost all cases except the last one where it is equal The internal compression causes in generala neglegiable overhead for these medium range problems only the last case suffers explicitly from this option it causes an almost uniform overhead with the larger problems and one should take into account that avoiding a memory overflow is a question of computability at all The prereduction makes sense in all cases if it produces no time saving it costs not much Only one case was found where restricting the reduction to the lt parts gives a tiny speedup The benefit of factorization varies from problem to problem very much if a factorization is found it can shorten the calculation and it gives much better usable results if not it requires an important additional computing time 5 4 Calculations for large chemical reaction systems These examples have their origin in a system of ODE s describing chemical reac tion systems Up to 60 polynomials in up to 60 variables number of variables and number of equations not necessarily equal The polynomi
14. for the comparison term ordering The list structure is very adequate for this type of operation two vectors are compared from left to right breaking when the first non equal position is found Total degree requires additionally a horizontal sum over the vectors We have improved this type of processing by exploiting the pipelined memory access of the vector computer while processing two exponent vectors four items are loaded in parallel in each cycle the two elements to be processed and the two pointers to the rest of the structures 5 Examples 5 1 A molecular structure We received a set of algebraic equations fii Y2 ys 0 2 ip from A Dress 1987 It describes the molecular structure of a cyclic carbon hydrogen molecule with six nodes The polynomials fo fi fa fg are given by 12 w dq dx d 0 1 8 3 8 3 1 AEG S 0 1 8 3 P 3M ee Su S es 0 1 8 3 y fo 8 3 1 0 1 8 3 8 3 yo 8 3 1 0 8 3 1 0 1 8 3 y fh y 8 3 1 0 1 8 3 8 3 y 8 3 1 0 1 1 8 3 y 8 3 1 0 FR e emenn oO H e e OQ Ja v Yo y3 ur f y2 Y3 41 Fs y Ya ya filys Y Y2 In order to find the common zeros Z fo fi fa fa of Ideal fo fi fe f3 we pro ceed as described in 2 5 Buchberger s algorithm is performed with the following features inverse lexicographical ordering integer coefficients Gr bner factorization The factorization produces eight Gr bner bases Z fo fi
15. h polynomial posesses a property list for descriptive slots e g a name of the polynomial for trace purposes its known factors the subspace of its variables Because of the object oriented approach different mem ory organizations can be used at the same time By default two organizations are active one simple in fact the traditional list in an encapsulated version for temporary intermediate results and a compressed representation for those polynomials which will survive local calculations e g the H polynomials So calculations with many intermediate H polynomials are possible in memory If the memory limit is exceeded an additional organization is available which places polynomials on secondary storage The only inference between the algorithm and the memory organization is the explicit marking of a polynomial to be of the sur vival type 3 4 Polynomial reduction sets It turned out that Grobner bases calculations are more efficient when we dis tinguish between the set G of all polynomials from input and H polynomial calculation and the set F obtained from G by cancelling redundant elements F is finally the reduced Gr bner basis whereas G is used in place of F for reducing the polynomials during the algorithm as sketched in 1 1 If G contains a great number of polynomials the search for a candidate for the reduction may require some time Therefore G is stored as a tree which reflects the structure of the It part such that the op
16. internal package for the manip ulation of polynomials in a distributive representation In this data structure a polynomial is represented as linear sorted sequence of monomials One advantage of this kind of representation is the possibility to select an ordering of the mono mials by ordering the terms i e the power products of the variables z1 74 in dependence of the desired application In REDUCE 3 3 the following two orderings are available The C LEX icographical ordering gam uer pn DP lt n Vj lt i a bj a gt bj The I nverse T otal D e G ree ordering ei porn gt itdg q rbn PEN Da gt X2 V Dar X b A alt gt i ziehe The INVLEX ordering is usefull for the solution of algebraic equations see ex ample 5 5 These two orderings are the same as in SAC 2 cf B ge Gebauer Kredel 1986 but different e g from those in Scratchpad II cf Jenks et al 1986 such that reduced Gr bner bases in different systems even if they are normalized in the same way can not be compared directly The REDUCE standard quotients are used as coefficients for the polynomials Standard quotients can be rational numbers or rational functions over variables or formal functions more general kernels So the algorithm in REDUCE 3 3 can be applied to polynomials over 9 the field of rational numbers and to polynomials over fields of rational functions 1 3 Cray computer usage for Grobner calculations In 1986 REDU
17. lable the normalization reduces in general the contents of the polynomials to 1 Normalization of the leading coefficients to 1 Q rational numbers Q ai a rational functions in a a over Q Zy integers modulo a prime number p Content of polynomial coefficients normalized to 1 Z integer numbers of arbitrary length Z ai a polynomials in a a over Z Other normalizations M p p Cartesian product of the prime fields Z 1 e M pi p in X X Z Here the leading coefficient is an s tuple It is normalized to 1 mod p 1 mod p see 2 6 3 H p f hybrid numbers i e pairs of an integer modulo a given prime p and a floating point number The leading coefficient is here nor malized to a hybrid number of type 1 mod p z z a floating point number see 2 6 2 Experiments have shown that for Gr bner basis calculations with non modular coefficients the ring version of the algorithm is faster than the field version Of course the calculations based on Z tend to produce bigger coefficients compared to the applications but this fact is not so important if a fast arithmetic is available see the statistics in 5 3 So the ring version is the default and input polynomials are converted from and l a a to Z and Zla a by multiplying every coefficient of a polynomial with the lcm of all coefficient denominators and using the identity a 1 a E alla Z ora Zl a
18. lling of redundant branches 2 5 3 Restrictions imposed by the application 2 6 Modular coefficients Bes en Grey Sh Sh Pee 2 6 1 The direct method edged eee E 2 6 2 The hybrid method P T T 2 6 3 The parallel method EEE aie ae ete See Technical improvements 3 1 Deferred branching for Grobner factorization 3 2 Dynamic selection of coefficient domains oe 3 3 Data Representation ET ZEE ae ee aaa 3 4 Polynomial reduction BOGS Sea a deus P Cray specific optimizations 4 1 Coefficient arithmetic llle FIM 4 2 Exponent vector processing eee Examples 5 1 A molecular structure nr oie te wh IE gt s 9 5 s Oo tO o OO 1 nn 0 Oo Ov om Dm PRP 00 U n e 10 10 10 11 11 12 12 12 12 12 5 2 Modular Gr bner computations 2 2 2 222er 14 9 8 DOME COMPAnSsonE sa 4 254 2 wine 15 5 4 Calculations for large chemical reaction systems ee 16 Abstract Gr bner bases are the main tool for solving systems of algebraic equations and some other problems in connection with polynomial ideals using Computer Alge bra Systems The procedure for the computation of Gr bner bases in REDUCE 3 3 has been modified in order to solve more complicated algebraic systems of equations by some general improve
19. ments and by some tools based on the specific resources of the CRAY X MP We present this modification and illustrate it by examples 1 Gr bner bases in REDUCE 3 3 1 1 Gr bner bases and Buchberger s algorithm The concept of Gr bner bases a special kind of bases for polynomial ideals was introduced by Buchberger in his thesis 1965 and developed in forthcoming papers Using Gr bner bases many problems dealing with multivariate polyno mials especially algebraic equations can be solved For a survey see Buchberger 1985 We assume familiarity with the basic notions of Gr bner bases namely term ordering leading term 1t leading coefficient lc reduction modulo a finite polynomial set irreducibility modulo such a set and S polynomial For polynomi als over a field we employ the same definition for Gr bner bases as Buchberger ie G is called a Gr bner basis if for any two f g G the S polynomial S f g reduces modulo G to 0 For polynomials over Z we define Gr bner bases in the same way but using pseudo reduction for the S polynomials as explained in 2 2 This leads to a Gr bner basis notion which is called in M ller 1988 a weak Grobner basis A Gr bner basis G is reduced if every f G is irreducible modulo GV f In case of polynomials over fields every ideal possesses exactly one reduced Gr bner basis F where le f 1 for every f F cf Buchberger 1985 Normalizing every element of a reduc
20. power product factors and by calling the REDUCE factorizer If a factorization is detected the state of the algorithm is encapsulated and for each of the factors a subproblem is generated and stacked into a list of open problems Of course the set of all such problems constitutes a tree with the initial problem of computing Z f fr as root 2 5 2 Cancelling of redundant branches Consider the subproblem for calculating Z gi gs and let h Ideal g g possess a factorization l h hisa ee yielding the subsequent subproblems for calculating the sets Z g1 gs hk k 1 m It may turn out that Z g1 95 hi is void i e 1 Ideal gi g hr or that Z gi gs hy is contained in a previously computed set of zeros such that its computation is superfluous In order to avoid such superfluous sets of zeros we associate to every problem a set of polynomials starting with the empty set for the initial problem If the set P is associated to the prob lem of calculating Z g1 gs then P is associated also to the problem of calculating Z gi gs hi1 If P is associated to the problem of calculating Z gi gs hx 1 k lt m then P U hy is associated to Z gi gs ha This gives the following criterion C If we start calculating the Groebner basis of Ideal gi1 9 and detect a polynomial in it which belongs also to the polynomial set associated to Z gu 9 then we s
21. ses over Z The arithmetic operations for these tuples are defined componentwise a1 a5 e b 5 ar b1 as e b with e c mod male When one component of a nonzero tuple is 0 then the corresponding p is unlucky and henceforth ignored for the reconstruction of the integer a by the Chinese remainder theorem In that case the reconstructed a by the Chinese remainder theorem is at most exact modulo pi p pi 3 Technical improvements 3 1 Deferred branching for Gr bner factorization When doing Gr bner factorizations as described in 2 5 for a problem with many variables and a sparse coefficient pattern we detected that different branches starting from one h hi hm had to do the same calculations for those polynomials depending only on variables different from those in hy hm So we implemented a delay if a branching point is encoutered the algorithm sets aside the factors and continues the calculations for those pairs with leading terms in variables disjoint to those of h hm Here new factorizations can be found which are handled in the same way Finally we have several levels of factorization at the same time giving a rich information for the configuration of subproblems In most cases factors themselves are of very low degree and so we do an additional reduction of all polynomials in one branch with its creating factors which gives a further reduction of problem size 3 2
22. t one negative component Therefore the restriction for nonnegative values cf 2 5 3 is imposed This reduces the amount of solutions and of calculation branches dramatically The algorithm now terminates in 358 seconds overall computing Aime incl garbage collections on the Cray giving 330 partial Gr bner bases A postprocessing analyse detects that most of these solutions are still redundant in the sense that they describe a subspace of other solutions The final number of independent solution spaces is eleven 17 ec udn anal REAR ec e AZ LITT mmn HET rcm Rem qq EY RR T Neh a 2 SPR rye re NET HINT A wn emm e DNE CH TE e EPRI E etnia ptem vein Hr eres FAR SNORT NED amr eo pum o pe a ar pen nS nm er a rl We IO PR mtn VENUS crime DS LE NL PAPIER TT AEU RINE i mpm m yes gue ty riz ug 0S TENIS MTR PEN SY Plon inm e IMS PECES ip rmt one n References J W Anderson W F Galway R R Kessler H Melenk W Neun Imple menting and Optimizing Lisp for the Cray IEEE Software July 1987 W Boge R Gebauer H Kredel Some Ezamples for Solving Systems of Al gebraic Equations by Calculating Groebner Bases J Symb Comp 1986 vol 2 pp 86 98 B Buchberger Ein Algorithmus zum Auffinden der Basiselemente des Restk lassenrings nach einem ERAN rao ater Polynomideal Ph D thesis Inns bruck 1965 B Buchberger Gr bner bases An algorithmic method in polynomial ideal the ory In Multidimensional Systems Theor
23. timal polynomial for a given reduction step can be found by addressing it 11 4 Cray specific optimizations 4 1 Coefficient arithmetic By analyzing the run time behaviour of the original package it soon became clear that the heavy usage of arbitrary precision integer arithmetic was one main bottleneck So we rewrote the PSL big package now using the Cray vector hardware This gave a significant run time reduction and stressed the superiority of Z based computations compared to based computations An obviously native area for a vector computer are the Zp X x Zp coeffi cients where the transformation from the algorithmic level to the machine level is almost obvious The operations can be mapped to one vector in struction cycle each doing the basic integer operation and adjusting components with overflow masking out non overflow components The pseudo division is a little bit more complicated because the number of loops needed by the extended Euclidean algorithm depends of the magnitude of the input values here the loop is performed until all values are finished the components which are ready earlier are ruled out by masking instructions 4 2 Exponent vector processing The processing of exponent vectors is the second bottleneck of distributive poly nomial processing Exponent vectors traditionally are stored as lists of small integers Most of the processing time spent with exponent vectors is needed
24. top the Gr bner basis calculation and remove the problem of computing Z gi 9 from the set of open problems The usage of this criterion is justified by the following reason If f belongs to the polynomial set associated to Z g1 9 and f Ideal g g then a j lt s exists by construction such that f and g j are both factors of g f the lower indexed factor Since f Ideal gi 9 we have Ideal gi 95 f Ideal g 9s Therefore Z g1 95 C Z gu gj f holds i e the prob lem of computing Z g 9s is superfluous 2 5 3 Restrictions imposed by the application In some applications only solutions are of interest which fullfill certain algebraic restrictions In some examples we are only interested in nonnegative real solutions For instance negative mass makes no sense So we implemented a hook for the used to decide via a procedure whether a polynomial violates these restrictions As a standard procedure the testing for nonnegative solutions is present and can be activated on request A polynomial 5 ar i ag with all a and ag positive has no zero z1 4 with all z nonnegative and real So the calculation branch can be cancelled A polynomial Da z zi without an absolute term ag and with all a positive can vanish only if all of its summands vanish This is possible only if in any summand at least one variable is zero In most cases there are se
25. veral possible combinations The list of combinations play the same role as a factorization and is handled in the same manner Although this approach is independent from factorization it plays its most impor tant role in this context the main problem of factorization is the fight against the great number of branches The earlier a polynomial without component wise nonnegative zeros is detected in a branch the earlier the computation in this branch may be interrupted at the expense of an additional branching or a complete cancellation of the branch 2 6 Modular coefficients Modular techniques are helpful when the coefficients of the output polynomials are expected to be of the same moderate size as the input coefficients but intermediate polynomials with big coefficients occur We have three methods for computing a Gr bner basis over the rationals by means of modular techniques 2 6 1 The direct method Take a sufficiently big prime p Transform each input polynomial to a polyno mial over Z by substituting its coefficient c d by a such that c a d mod p 0 lt a p Compute a reduced Gr bner basis over Z with each leading coefficient normalized to 1 Reconstruct each Gr bner basis coefficient a mod p to a rational number by means of the algorithm of Wang 1981 The resulting polynomials constitute the reduced normalized Grobner basis over Q if p is a sufficiently big lucky prime 2 6 2 The hybrid method Many pol
26. y ed N K Bose D Reidel Publ Comp 1985 pp 184 232 J H Davenport Private communication 1987 P Deuflhard Private eprint on 1987 A Dress Private communication 1987 R Gebauer H M M ller On an installation of Buchberger s algorithm To appear in J Symb Comp 1988 A C Hearn REDUCE User s Manual Version j 3 The Rand Corporation 1987 R Jenks et al Scratchpad II an experimental computer algebra system ab breviated primer and ezamples IBM Thomas Watson Research Venen Yorktown Heights N Y 10598 1986 D E Knuth The Art of core ee Vol 2 Seminumerical Algo rithms 2nd edition 1981 H M M ller On the construction of Gr bner bases MT syzygies to appear in J Symb Comp 1988 H Melenk W Neun REDUCE Users Guide for Cray 1 X MP Series Run ning COS Konrad Zuse Zentrum Berlin Technical Report TR 87 4 1987 H Melenk W Neun Usage of Vector Hardware for oS Processing Konrad Zuse Zentrum Berlin 1986 P Wang A p adic algorithm for univariate partial fractions Proc SYMSAC 81 ACM pp 212 216 1981 18 i2 WA cocus Cura emn be aka 2 go eae
27. ynomials come from scientific applications where the coefficients are only approximations to some real life quantities So the coefficients are typ ically floating point numbers On the other hand Buchberger s algorithm re quires exact coefficients Therefore we compute via REDUCE rational numbers approximating the floating point values and from that we produce a modular number The modular number and the floating point value then are paired for Buchberger s algorithm to a hybrid number The arithmetic is defined compo nentwise The modular number now controls Buchberger s algorithm allowing exact calculations while the floating point values are calculated as side effects t termination of the algorithm the polynomials with the modular part of the hybrid numbers as coefficients constitute a Gr bner basis The polynomials with the float number parts as coefficients are then expected to be approximations to the Grobner basis polynomials of the initial real life problem Because we do not reconstruct the true values from the modular number the prime number can be of moderate size 2 6 3 The parallel method As proposed by Knuth 1981 each integer a mod p p with pairwise different primes pj 1 s can be represented uniquely by an s tuple a a with a z a mod p and given the a s the integer a can be reconstructed by the Chinese remainder theorem Therefore we proceed as in 2 6 1 in order to find Grobner ba
Download Pdf Manuals
Related Search
SC 88 02 sc8802 pdf sc8802a sc8802 datasheet sc8802 demo sc8802qder pdf sc8802 buck boost