Initial population.

1 files changed, 212 insertions, 0 deletions

diff --git a/src/algebra/npcoef.spad.pamphlet b/src/algebra/npcoef.spad.pamphlet
new file mode 100644
index 00000000..ef842223
--- /dev/null
+++ b/src/algebra/npcoef.spad.pamphlet
@@ -0,0 +1,212 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra npcoef.spad}
+\author{Patrizia Gianni}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\section{package NPCOEF NPCoef}
+<<package NPCOEF NPCoef>>=
+)abbrev package NPCOEF NPCoef
+++ Author : P.Gianni, revised May 1990
+++ Description: 
+++ Package for the determination of the coefficients in the lifting
+++ process. Used by \spadtype{MultivariateLifting}.
+++ This package will work for every euclidean domain R which has property
+++ F, i.e. there exists a factor operation in \spad{R[x]}.
+NPCoef(BP,E,OV,R,P) : C == T where
+ 
+ OV   :   OrderedSet
+ E    :   OrderedAbelianMonoidSup
+ R    :   EuclideanDomain  -- with property "F"
+ BP   :   UnivariatePolynomialCategory R
+ P    :   PolynomialCategory(R,E,OV)
+ 
+ Z       ==> Integer
+ NNI     ==> NonNegativeInteger
+ USP     ==> SparseUnivariatePolynomial(P)
+ Term    ==> Record(expt:NNI,pcoef:P)
+ Detc    ==> Record(valexp:NNI,valcoef:P,posit:NNI)
+ VTerm   ==> List(Term)
+ DetCoef ==> Record(deter:List(USP),dterm:List(VTerm),
+                    nfacts:List(BP),nlead:List(P))
+ TermC   ==> Record(coefu:P,detfacts:List(VTerm))
+ TCoef   ==> List(TermC)
+ 
+ C == with
+      npcoef   :    (USP,List(BP),List(P))      ->   DetCoef
+	++ npcoef \undocumented
+      listexp  :              BP                ->   List(NNI)
+	++ listexp \undocumented
+ T == add
+ 
+                 ----   Local  Functions  ----
+  check      : (TermC,Vector P) -> Union(Detc,"failed")
+  buildvect  : (List(VTerm),NNI) -> Vector(List(VTerm))
+  buildtable : (Vector(P),List(List NNI),List P) -> TCoef
+  modify : (TCoef,Detc) -> TCoef 
+  constructp : VTerm -> USP
+
+  npcoef(u:USP,factlist:List(BP),leadlist:List(P)) :DetCoef ==
+    detcoef:List(VTerm):=empty();detufact:List(USP):=empty()
+    lexp:List(List(NNI)):=[listexp(v) for v in factlist]
+    ulist :Vector(P):=vector [coefficient(u,i) for i in 0..degree u]
+    tablecoef:=buildtable(ulist,lexp,leadlist)
+    detcoef:=[[[ep.first,lcu]$Term]  for ep in lexp for lcu in leadlist]
+    ldtcf:=detcoef
+    lexp:=[ep.rest for ep in lexp]
+    ndet:NNI:=#factlist
+    changed:Boolean:=true
+    ltochange:List(NNI):=empty()
+    ltodel:List(NNI):=empty()
+    while changed and ndet^=1 repeat
+      changed :=false
+      dt:=#tablecoef
+      for i in 1..dt while ^changed repeat
+        (cf:=check(tablecoef.i,ulist)) case "failed" => "next i"
+        ltochange:=cons(i,ltochange)
+        celtf:Detc:=cf::Detc
+        tablecoef:=modify(tablecoef,celtf)
+        vpos:=celtf.posit
+        vexp:=celtf.valexp
+        nterm:=[vexp,celtf.valcoef]$Term
+        detcoef.vpos:=cons(nterm,detcoef.vpos)
+        lexp.vpos:=delete(lexp.vpos,position(vexp,lexp.vpos))
+        if lexp.vpos=[] then
+         ltodel:=cons(vpos,ltodel)
+         ndet:=(ndet-1):NNI
+         detufact:=cons(constructp(detcoef.vpos),detufact)
+        changed:=true
+      for i in ltochange repeat tablecoef:=delete(tablecoef,i)
+      ltochange:=[]
+    if ndet=1 then
+     uu:=u exquo */[pol for pol in detufact]
+     if uu case "failed" then return
+       [empty(),ldtcf,factlist,leadlist]$DetCoef
+     else  detufact:=cons(uu::USP,detufact)
+    else
+      ltodel:=sort(#1>#2,ltodel)
+      for i in ltodel repeat
+        detcoef:=delete(detcoef,i)
+        factlist:=delete(factlist,i)
+        leadlist:=delete(leadlist,i)
+    [detufact,detcoef,factlist,leadlist]$DetCoef
+ 
+ 
+  check(tterm:TermC,ulist:Vector(P)) : Union(Detc,"failed") ==
+    cfu:P:=1$P;doit:NNI:=0;poselt:NNI:=0;pp:Union(P,"failed")
+    termlist:List(VTerm):=tterm.detfacts
+    vterm:VTerm:=empty()
+    #termlist=1 =>
+      vterm:=termlist.first
+      for elterm in vterm while doit<2 repeat
+        (cu1:=elterm.pcoef)^=0 => cfu:=cu1*cfu
+        doit:=doit+1
+        poselt:=position(elterm,vterm):NNI
+      doit=2  or (pp:=tterm.coefu exquo cfu) case "failed" => "failed"
+      [vterm.poselt.expt,pp::P,poselt]$Detc
+    "failed"
+ 
+  buildvect(lvterm:List(VTerm),n:NNI) : Vector(List(VTerm)) ==
+    vtable:Vector(List(VTerm)):=new(n,empty())
+    (#lvterm)=1 =>
+      for term in lvterm.first repeat vtable.(term.expt+1):=[[term]]
+      vtable
+ 
+    vtable:=buildvect(lvterm.rest,n)
+    ntable:Vector(List(VTerm)):=new(n,empty())
+    for term in lvterm.first repeat
+      nexp:=term.expt
+      for i in 1..n while (nexp+i)<(n+1) repeat
+        ntable.(nexp+i):=append(
+                            [cons(term,lvterm) for lvterm in vtable.i],
+                               ntable.(nexp+i))
+    ntable
+ 
+  buildtable(vu:Vector(P),lvect:List(List(NNI)),leadlist:List(P)):TCoef==
+    nfact:NNI:=#leadlist
+    table:TCoef:=empty()
+    degu:=(#vu-1)::NNI
+    prelim:List(VTerm):=[[[e,0$P]$Term for e in lv] for lv in lvect]
+    for i in 1..nfact repeat prelim.i.first.pcoef:=leadlist.i
+    partialv:Vector(List(VTerm)):=new(nfact,empty())
+    partialv:=buildvect(prelim,degu)
+    for i in 1..degu repeat
+      empty? partialv.i => "next i"
+      table:=cons([vu.i,partialv.i]$TermC, table)
+    table
+ 
+  modify(tablecoef:TCoef,cfter:Detc) : TCoef ==
+    cfexp:=cfter.valexp;cfcoef:=cfter.valcoef;cfpos:=cfter.posit
+    lterase:List(NNI):=empty()
+    for cterm in tablecoef | ^empty?(ctdet:=cterm.detfacts) repeat
+      (+/[term.expt for term in ctdet.first])<cfexp => "next term"
+      for celt in ctdet repeat
+        if celt.cfpos.expt=cfexp then
+          celt.cfpos.pcoef:=cfcoef
+          if (and/[cc.pcoef ^=0 for cc in celt]) then
+            k:=position(celt,ctdet):NNI
+            lterase:=cons(k,lterase)
+            cterm.coefu:=(cterm.coefu - */[cc.pcoef for cc in celt])
+      if not empty? lterase then
+        lterase:=sort(#1>#2,lterase)
+        for i in lterase repeat ctdet:=delete(ctdet,i)
+        cterm.detfacts:=ctdet
+        lterase:=empty()
+    tablecoef
+ 
+  listexp(up:BP) :List(NNI) ==
+    degree up=0 => [0]
+    [degree up,:listexp(reductum up)]
+ 
+  constructp(lterm:VTerm):USP ==
+    +/[monomial(term.pcoef,term.expt) for term in lterm]
+
+@
+\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>>
+
+<<package NPCOEF NPCoef>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}