diff options
Diffstat (limited to 'src/algebra/qalgset.spad.pamphlet')
| -rw-r--r-- | src/algebra/qalgset.spad.pamphlet | 353 |
1 files changed, 353 insertions, 0 deletions
diff --git a/src/algebra/qalgset.spad.pamphlet b/src/algebra/qalgset.spad.pamphlet new file mode 100644 index 00000000..7f5a0371 --- /dev/null +++ b/src/algebra/qalgset.spad.pamphlet @@ -0,0 +1,353 @@ +\documentclass{article} +\usepackage{axiom} +\begin{document} +\title{\$SPAD/src/algebra qalgset.spad} +\author{William Sit} +\maketitle +\begin{abstract} +\end{abstract} +\eject +\tableofcontents +\eject +\section{domain QALGSET QuasiAlgebraicSet} +<<domain QALGSET QuasiAlgebraicSet>>= +)abbrev domain QALGSET QuasiAlgebraicSet +++ Author: William Sit +++ Date Created: March 13, 1992 +++ Date Last Updated: June 12, 1992 +++ Basic Operations: +++ Related Constructors:GroebnerPackage +++ See Also: QuasiAlgebraicSet2 +++ AMS Classifications: +++ Keywords: Zariski closed sets, quasi-algebraic sets +++ References:William Sit, "An Algorithm for Parametric Linear Systems" +++ J. Sym. Comp., April, 1992 +++ Description: +++ \spadtype{QuasiAlgebraicSet} constructs a domain representing +++ quasi-algebraic sets, which +++ is the intersection of a Zariski +++ closed set, defined as the common zeros of a given list of +++ polynomials (the defining polynomials for equations), and a principal +++ Zariski open set, defined as the complement of the common +++ zeros of a polynomial f (the defining polynomial for the inequation). +++ This domain provides simplification of a user-given representation +++ using groebner basis computations. +++ There are two simplification routines: the first function +++ \spadfun{idealSimplify} uses groebner +++ basis of ideals alone, while the second, \spadfun{simplify} uses both +++ groebner basis and factorization. The resulting defining equations L +++ always form a groebner basis, and the resulting defining +++ inequation f is always reduced. The function \spadfun{simplify} may +++ be applied several times if desired. A third simplification +++ routine \spadfun{radicalSimplify} is provided in +++ \spadtype{QuasiAlgebraicSet2} for comparison study only, +++ as it is inefficient compared to the other two, as well as is +++ restricted to only certain coefficient domains. For detail analysis +++ and a comparison of the three methods, please consult the reference +++ cited. +++ +++ A polynomial function q defined on the quasi-algebraic set +++ is equivalent to its reduced form with respect to L. While +++ this may be obtained using the usual normal form +++ algorithm, there is no canonical form for q. +++ +++ The ordering in groebner basis computation is determined by +++ the data type of the input polynomials. If it is possible +++ we suggest to use refinements of total degree orderings. +QuasiAlgebraicSet(R, Var,Expon,Dpoly) : C == T + where + R : GcdDomain + Expon : OrderedAbelianMonoidSup + Var : OrderedSet + Dpoly : PolynomialCategory(R,Expon,Var) + NNI ==> NonNegativeInteger + newExpon ==> Product(NNI,Expon) + newPoly ==> PolynomialRing(R,newExpon) + Ex ==> OutputForm + mrf ==> MultivariateFactorize(Var,Expon,R,Dpoly) + Status ==> Union(Boolean,"failed") -- empty or not, or don't know + + C == Join(SetCategory, CoercibleTo OutputForm) with + --- should be Object instead of SetCategory, bug in LIST Object --- + --- equality is not implemented --- + empty: () -> $ + ++ empty() returns the empty quasi-algebraic set + quasiAlgebraicSet: (List Dpoly, Dpoly) -> $ + ++ quasiAlgebraicSet(pl,q) returns the quasi-algebraic set + ++ with defining equations p = 0 for p belonging to the list pl, and + ++ defining inequation q ^= 0. + status: $ -> Status + ++ status(s) returns true if the quasi-algebraic set is empty, + ++ false if it is not, and "failed" if not yet known + setStatus: ($, Status) -> $ + ++ setStatus(s,t) returns the same representation for s, but + ++ asserts the following: if t is true, then s is empty, + ++ if t is false, then s is non-empty, and if t = "failed", + ++ then no assertion is made (that is, "don't know"). + ++ Note: for internal use only, with care. + empty? : $ -> Boolean + ++ empty?(s) returns + ++ true if the quasialgebraic set s has no points, + ++ and false otherwise. + definingEquations: $ -> List Dpoly + ++ definingEquations(s) returns a list of defining polynomials + ++ for equations, that is, for the Zariski closed part of s. + definingInequation: $ -> Dpoly + ++ definingInequation(s) returns a single defining polynomial for the + ++ inequation, that is, the Zariski open part of s. + idealSimplify:$ -> $ + ++ idealSimplify(s) returns a different and presumably simpler + ++ representation of s with the defining polynomials for the + ++ equations + ++ forming a groebner basis, and the defining polynomial for the + ++ inequation reduced with respect to the basis, using Buchberger's + ++ algorithm. + if (R has EuclideanDomain) and (R has CharacteristicZero) then + simplify:$ -> $ + ++ simplify(s) returns a different and presumably simpler + ++ representation of s with the defining polynomials for the + ++ equations + ++ forming a groebner basis, and the defining polynomial for the + ++ inequation reduced with respect to the basis, using a heuristic + ++ algorithm based on factoring. + T == add + Rep := Record(status:Status,zero:List Dpoly, nzero:Dpoly) + x:$ + + import GroebnerPackage(R,Expon,Var,Dpoly) + import GroebnerPackage(R,newExpon,Var,newPoly) + import GroebnerInternalPackage(R,Expon,Var,Dpoly) + + ---- Local Functions ---- + + minset : List List Dpoly -> List List Dpoly + overset? : (List Dpoly, List List Dpoly) -> Boolean + npoly : Dpoly -> newPoly + oldpoly : newPoly -> Union(Dpoly,"failed") + + + if (R has EuclideanDomain) and (R has CharacteristicZero) then + factorset (y:Dpoly):List Dpoly == + ground? y => [] + [j.factor for j in factors factor$mrf y] + + simplify x == + if x.status case "failed" then + x:=quasiAlgebraicSet(zro:=groebner x.zero, redPol(x.nzero,zro)) + (pnzero:=x.nzero)=0 => empty() + nzro:=factorset pnzero + mset:=minset [factorset p for p in x.zero] + mset:=[setDifference(s,nzro) for s in mset] + zro:=groebner [*/s for s in mset] + member? (1$Dpoly, zro) => empty() + [x.status, zro, primitivePart redPol(*/nzro, zro)] + + npoly(f:Dpoly) : newPoly == + zero? f => 0 + monomial(leadingCoefficient f,makeprod(0,degree f))$newPoly + + npoly(reductum f) + + oldpoly(q:newPoly) : Union(Dpoly,"failed") == + q=0$newPoly => 0$Dpoly + dq:newExpon:=degree q + n:NNI:=selectfirst (dq) + n^=0 => "failed" + ((g:=oldpoly reductum q) case "failed") => "failed" + monomial(leadingCoefficient q,selectsecond dq)$Dpoly + (g::Dpoly) + + coerce x == + x.status = true => "Empty"::Ex + bracket [[hconcat(f::Ex, " = 0"::Ex) for f in x.zero ]::Ex, + hconcat( x.nzero::Ex, " != 0"::Ex)] + + empty? x == + if x.status case "failed" then x:=idealSimplify x + x.status :: Boolean + + empty() == [true::Status, [1$Dpoly], 0$Dpoly] + status x == x.status + setStatus(x,t) == [t,x.zero,x.nzero] + definingEquations x == x.zero + definingInequation x == x.nzero + quasiAlgebraicSet(z0,n0) == ["failed", z0, n0] + + idealSimplify x == + x.status case Boolean => x + z0:= x.zero + n0:= x.nzero + empty? z0 => [false, z0, n0] + member? (1$Dpoly, z0) => empty() + tp:newPoly:=(monomial(1,makeprod(1,0$Expon))$newPoly * npoly n0)-1 + ngb:=groebner concat(tp, [npoly g for g in z0]) + member? (1$newPoly, ngb) => empty() + gb:List Dpoly:=nil + while not empty? ngb repeat + if ((f:=oldpoly ngb.first) case Dpoly) then gb:=concat(f, gb) + ngb:=ngb.rest + [false::Status, gb, primitivePart redPol(n0, gb)] + + + minset lset == + empty? lset => lset + [s for s in lset | ^(overset?(s,lset))] + + overset?(p,qlist) == + empty? qlist => false + or/[(brace$(Set Dpoly) q) <$(Set Dpoly) (brace$(Set Dpoly) p) for q in qlist] + +@ +\section{package QALGSET2 QuasiAlgebraicSet2} +<<package QALGSET2 QuasiAlgebraicSet2>>= +)abbrev package QALGSET2 QuasiAlgebraicSet2 +++ Author: William Sit +++ Date Created: March 13, 1992 +++ Date Last Updated: June 12, 1992 +++ Basic Operations: +++ Related Constructors:GroebnerPackage, IdealDecompositionPackage, +++ PolynomialIdeals +++ See Also: QuasiAlgebraicSet +++ AMS Classifications: +++ Keywords: Zariski closed sets, quasi-algebraic sets +++ References:William Sit, "An Algorithm for Parametric Linear Systems" +++ J. Sym. Comp., April, 1992 +++ Description: +++ \spadtype{QuasiAlgebraicSet2} adds a function \spadfun{radicalSimplify} +++ which uses \spadtype{IdealDecompositionPackage} to simplify +++ the representation of a quasi-algebraic set. A quasi-algebraic set +++ is the intersection of a Zariski +++ closed set, defined as the common zeros of a given list of +++ polynomials (the defining polynomials for equations), and a principal +++ Zariski open set, defined as the complement of the common +++ zeros of a polynomial f (the defining polynomial for the inequation). +++ Quasi-algebraic sets are implemented in the domain +++ \spadtype{QuasiAlgebraicSet}, where two simplification routines are +++ provided: +++ \spadfun{idealSimplify} and \spadfun{simplify}. +++ The function +++ \spadfun{radicalSimplify} is added +++ for comparison study only. Because the domain +++ \spadtype{IdealDecompositionPackage} provides facilities for +++ computing with radical ideals, it is necessary to restrict +++ the ground ring to the domain \spadtype{Fraction Integer}, +++ and the polynomial ring to be of type +++ \spadtype{DistributedMultivariatePolynomial}. +++ The routine \spadfun{radicalSimplify} uses these to compute groebner +++ basis of radical ideals and +++ is inefficient and restricted when compared to the +++ two in \spadtype{QuasiAlgebraicSet}. +QuasiAlgebraicSet2(vl,nv) : C == T where + vl : List Symbol + nv : NonNegativeInteger + R ==> Integer + F ==> Fraction R + Var ==> OrderedVariableList vl + NNI ==> NonNegativeInteger + Expon ==> DirectProduct(nv,NNI) + Dpoly ==> DistributedMultivariatePolynomial(vl,F) + QALG ==> QuasiAlgebraicSet(F, Var, Expon, Dpoly) + newExpon ==> DirectProduct(#newvl, NNI) + newPoly ==> DistributedMultivariatePolynomial(newvl,F) + newVar ==> OrderedVariableList newvl + Status ==> Union(Boolean,"failed") -- empty or not, or don't know + + C == with + radicalSimplify:QALG -> QALG + ++ radicalSimplify(s) returns a different and presumably simpler + ++ representation of s with the defining polynomials for the + ++ equations + ++ forming a groebner basis, and the defining polynomial for the + ++ inequation reduced with respect to the basis, using + ++ using groebner basis of radical ideals + T == add + ---- Local Functions ---- + ts:=new()$Symbol + newvl:=concat(ts, vl) + tv:newVar:=(variable ts)::newVar + npoly : Dpoly -> newPoly + oldpoly : newPoly -> Union(Dpoly,"failed") + f : Var -> newPoly + g : newVar -> Dpoly + + import PolynomialIdeals(F,newExpon,newVar,newPoly) + import GroebnerPackage(F,Expon,Var,Dpoly) + import GroebnerPackage(F,newExpon,newVar,newPoly) + import IdealDecompositionPackage(newvl,#newvl) + import QuasiAlgebraicSet(F, Var, Expon, Dpoly) + import PolynomialCategoryLifting(Expon,Var,F,Dpoly,newPoly) + import PolynomialCategoryLifting(newExpon,newVar,F,newPoly,Dpoly) + f(v:Var):newPoly == + variable((convert v)@Symbol)@Union(newVar,"failed")::newVar + ::newPoly + g(v:newVar):Dpoly == + v = tv => 0 + variable((convert v)@Symbol)@Union(Var,"failed")::Var::Dpoly + + npoly(p:Dpoly) : newPoly == map(f #1, #1::newPoly, p) + + oldpoly(q:newPoly) : Union(Dpoly,"failed") == + (x:=mainVariable q) case "failed" => (leadingCoefficient q)::Dpoly + (x::newVar = tv) => "failed" + map(g #1,#1::Dpoly, q) + + radicalSimplify x == + status(x)$QALG = true => x -- x is empty + z0:=definingEquations x + n0:=definingInequation x + t:newPoly:= coerce(tv)$newPoly + tp:newPoly:= t * (npoly n0) - 1$newPoly + gen:List newPoly:= concat(tp, [npoly g for g in z0]) + id:=ideal gen + ngb:=generators radical(id) + member? (1$newPoly, ngb) => empty()$QALG + gb:List Dpoly:=nil + while not empty? ngb repeat + if ((k:=oldpoly ngb.first) case Dpoly) then gb:=concat(k, gb) + ngb:=ngb.rest + y:=quasiAlgebraicSet(gb, primitivePart normalForm(n0, gb)) + setStatus(y,false::Status) + +@ +\section{License} +<<license>>= +--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd. +--All rights reserved. +-- +--Redistribution and use in source and binary forms, with or without +--modification, are permitted provided that the following conditions are +--met: +-- +-- - Redistributions of source code must retain the above copyright +-- notice, this list of conditions and the following disclaimer. +-- +-- - Redistributions in binary form must reproduce the above copyright +-- notice, this list of conditions and the following disclaimer in +-- the documentation and/or other materials provided with the +-- distribution. +-- +-- - Neither the name of The Numerical ALgorithms Group Ltd. nor the +-- names of its contributors may be used to endorse or promote products +-- derived from this software without specific prior written permission. +-- +--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +@ +<<*>>= +<<license>> + +<<domain QALGSET QuasiAlgebraicSet>> +<<package QALGSET2 QuasiAlgebraicSet2>> +@ +\eject +\begin{thebibliography}{99} +\bibitem{1} nothing +\end{thebibliography} +\end{document} |