(* ---------------------------------------------------------------------------- * $Id: RRADOM.md,v 1.1 1994/03/11 15:21:49 pesch Exp $ * ---------------------------------------------------------------------------- * This file is part of MAS. * ---------------------------------------------------------------------------- * Copyright (c) 1993 Universitaet Passau * ---------------------------------------------------------------------------- * $Log: RRADOM.md,v $ * Revision 1.1 1994/03/11 15:21:49 pesch * Counting real roots of multivariate polynomials, Diplomarbeit F. Lippold * * ---------------------------------------------------------------------------- *) DEFINITION MODULE RRADOM; (* Real Root Arbitrary Domain Definition Module *) (* Import lists and declarations. *) FROM MASSTOR IMPORT LIST;CONSTrcsid = "$Id: RRADOM.md,v 1.1 1994/03/11 15:21:49 pesch Exp $";CONSTcopyright = "Copyright (c) 1993 Universitaet Passau";PROCEDURE EVUMSORT(L: LIST): LIST; (* Exponent vector unique merge sort. The list of exponent vectors L ist sorted with respect to the actual termorder. Multiple entries are deleted. *)PROCEDURE EVSSPROD(T: LIST): LIST; (* Exponent vektor set sorted product. T is a list of terms. U = {a*b: a,b from T} is sorted with respect to the actual termorder. *)PROCEDURE RRVTEXT(A,L: LIST): LIST; (* Real root vector of tupels extension. A is a set of s-tupels, L is a set of objects. B is a set of (s+1)-tupels constructed by appending each object of L to the tupels of A. The ordering of B is increasing lexicographical wrt the ordering of L and A. *)PROCEDURE RRZDIM(G: LIST): LIST; (* Real root zero-dimensional test. G non-trivial reduced groebner basis. s = 1 iff Id(G) is zero-dimensional, s = 0 otherwise. *)PROCEDURE RRREDTEST(G,t: LIST;VARg,s: LIST); (* Real root reducibility test. G reduced groebner basis, t term. s = 0, if t is reducible with an Element g of G with HT(g) = t, s = -1, if t is not reducible and s = 1 otherwise *)PROCEDURE RRREDTERMS(G: LIST): LIST; (* Real root reduced terms. G reduced groebner basis of a nontrival zerodimensional ideal. R ist the set of reduced terms sorted with respect to the actual termorder. *)PROCEDURE RRADNFORM(D,G,R: LIST): LIST; (* Real root arbitrary domain normal form. G monic reduced groebner basis of a nontrivial zerodimensional ideal of domain D, R is the set of reduced terms. NF is a list of entries (u,ut,up) with: u is an element of R * R, RRREDTEST(G,u,_,ut) and up is the normal form of u wrt G. The elements of NF are sorted with respect to the actual termorder in decreasing order of the first entry. *)PROCEDURE RRADSTRCONST(D,G,R: LIST;VARU, beta: LIST); (* Real root arbitrary domain structure constants. G monic reduced groebner basis of a nontrivial zerodimensional ideal of domain D, R is the set of reduced terms. beta is a matrix of structure- constants beta[u,v] wrt the basis R with u from U = R * R and v from R. U and the rows of the matrix beta are sorted with respect to the actual termorder in increasing order. *)PROCEDURE RRMMULT(w,R,U,beta: LIST): LIST; (* Real root matrix of multiplication. R is the set of reduced terms in increasing order, w from R, U = R * R and beta is the set of combined structure constants wrt R. The columnwise represented matrix of multiplication with w is returned. *)PROCEDURE RRADVARMATRICES(G,R,U,beta: LIST): LIST; (* Real root arbitrary domain multiplication matrices of variables. G monic reduced groebner basis of a nontrivial zerodimensional ideal. R is the set of reduced terms in increasing order, U = R * R and beta is the set of combined structure constants wrt R. L is a list of entries of the form (1,M(i)) and M(i) is the matrix of multiplication with X(i) wrt R. *)PROCEDURE RRADPOLMATRIX(D,R,h: LIST;VARMh,L: LIST); (* Real root arbitrary domain polynomial matrix. R is the set of reduced terms in increasing order, h is a polynomial of domain D, L contains nonempty lists L(i) of the form j(1),M(1),j(2),M(2),...,j(k),M(k) with 1=j(1)<j(2)<...<j(k) and M(l) ist the matrix of multiplikation with X(i)**j(l) for the variable X(i). L is extended with new calculated matrices. Mh is the matrix of multiplication with h. *)PROCEDURE RRADQUADFORM(D,R,U,beta,Mh: LIST): LIST; (* Real root arbitrary domain quadratic form. D is a domain, R is the set of reduced terms in increasing order, U = R * R and beta is the set of combined structure constants wrt R. Mh is the matrix of multiplication with h represented columnwise. The matrix Q=(q(i,j)) with q(i,j) = tr(M(h)*M(v(i))*M(v(j)) and v(i),v(j) from R is computed. *)PROCEDURE RRCSR(i,v,tf: LIST;VARA,N,S,L: LIST): LIST; (* Real root count solve and reduce. Subroutine of the RR*COUNT procedures. i is an integer, v is a sign vector, tf is the trace-flag. A is an integral k x k- matrix, N is a subset of {-1,0,+1}**i of length k sorted in increasing lexicographical order, S is an integral vector of length k and L is a list of length k. The system A*Z=S is solved and reduced by deleting the zero entries of Z and the corresponding columns of A. Then the system is reduced to a regular one by deleting linear dependend rows of A and the corresponding elements of S and L. ZNL is a list of pairs (z,n) with z > 0 is an element of Z and n is the corresponding element of N. If there does not exist an element n in N satisfiing the sign condition v then the empty list is returned. *)PROCEDURE RRADCOUNT(D,G,H,v,tf: LIST): LIST; (* Real root arbirary domain count. G is a monic reduced groebner basis of a zerodimensional ideal of domain D, H is a list of polynomials of length s. v is a vektor of signs with length not greater than s. tf is the trace-flag. ZNL is a list of pairs (z,n) with n is an element of {-1,0,+1}**s and z > 0 is the number of real zeroes of G wrt the sign condition n for the elements of H. ZNL is sorted wrt the invers lexicographical order of the n. If there does not exist any real zero or a zero satisfiing the sign condition v, then the empty list is returned. *)ENDRRADOM. (* -EOF- *)